Search

Progress in science and technology is punctuated by disruptive innovation and breakthroughs. Researchers have characterized these disruptions to explore the factors that spark such innovations and to assess their long-term trends. However, although understanding disruptive breakthroughs and their drivers hinges upon accurately quantifying disruptiveness, the core metric used in previous studies -- the disruption index -- remains insufficiently understood and tested. Here, after demonstrating the critical shortcomings of the disruption index, including its conflicting evaluations for simultaneous discoveries, we propose a new, continuous measure of disruptiveness based on a neural embedding framework that addresses these limitations. Our measure not only better distinguishes disruptive works, such as Nobel Prize-winning papers, from others, but also reveals simultaneous disruptions by allowing us to identify the "twins" that have the most similar future context. By offering a more robust and precise lens for identifying disruptive innovations and simultaneous discoveries, our study provides a foundation for deepening insights into the mechanisms driving scientific breakthroughs while establishing a more equitable basis for evaluating transformative contributions. more...

Many human knowledge systems, such as science, law, and invention, are built on documents and the citations that link them. Citations, while serving multiple purposes, primarily function as a way to explicitly document the use of prior work and thus have become central to the study of knowledge systems. Analyzing citation dynamics has revealed statistical patterns that shed light on knowledge production, recognition, and formalization, and has helped identify key mechanisms driving these patterns. However, most quantitative findings are confined to scientific citations, raising the question of universality of these findings. Moreover, existing models of individual citation trajectories fail to explain phenomena such as delayed recognition, calling for a unifying framework. Here, we analyze a newly available corpus of U.S. case law, in addition to scientific and patent citation networks, to show that they share remarkably similar citation patterns, including a heavy-tailed distribution of sleeping beauties. We propose a holistic model that captures the three core mechanisms driving collective dynamics and replicates the elusive phenomenon of delayed recognition. We demonstrate that the model not only replicates observed citation patterns, but also better predicts future successes by considering the whole system. Our work offers insights into key mechanisms that govern large-scale patterns of collective human knowledge systems and may provide generalizable perspectives on discovery and innovation across domains. more...

Networks are powerful tools for modeling interactions in complex systems. While traditional networks use scalar edge weights, many real-world systems involve multidimensional interactions. For example, in social networks, individuals often have multiple interconnected opinions that can affect different opinions of other individuals, which can be better characterized by matrices. We propose a novel, general framework for modeling such multidimensional interacting dynamics: matrix-weighted networks (MWNs). We present the mathematical foundations of MWNs and examine consensus dynamics and random walks within this context. Our results reveal that the coherence of MWNs gives rise to non-trivial steady states that generalize the notions of communities and structural balance in traditional networks., Comment: 14 pages, 8 figures more...

We propose a method to measure the similarity of papers and authors by simulating a literature search procedure on citation networks, which is an information retrieval inspired conceptualization of similarity. This transition probability (TP) based approach does not require a curated classification system, avoids clustering complications, and provides a continuous measure of similarity. We perform testing scenarios to explore several versions of the general TP concept and the Node2vec machine-learning technique. We found that TP measures outperform Node2vec in mapping the macroscopic structure of fields. The paper provides a general discussion of how to implement TP similarity measurement, with a particular focus on how to utilize publication-level information to approximate the research interest similarity of individual scientists. This paper is accompanied by a Python package capable of calculating all the tested metrics. more...

Link prediction -- a task of distinguishing actual hidden edges from random unconnected node pairs -- is one of the quintessential tasks in graph machine learning. Despite being widely accepted as a universal benchmark and a downstream task for representation learning, the validity of the link prediction benchmark itself has been rarely questioned. Here, we show that the common edge sampling procedure in the link prediction task has an implicit bias toward high-degree nodes and produces a highly skewed evaluation that favors methods overly dependent on node degree, to the extent that a ``null'' link prediction method based solely on node degree can yield nearly optimal performance. We propose a degree-corrected link prediction task that offers a more reasonable assessment that aligns better with the performance in the recommendation task. Finally, we demonstrate that the degree-corrected benchmark can more effectively train graph machine-learning models by reducing overfitting to node degrees and facilitating the learning of relevant structures in graphs., Comment: 13 pages, 3 figures more...

Recent advances in machine learning offer new ways to represent and study scholarly works and the space of knowledge. Graph and text embeddings provide a convenient vector representation of scholarly works based on citations and text. Yet, it is unclear whether their representations are consistent or provide different views of the structure of science. Here, we compare graph and text embedding by testing their ability to capture the hierarchical structure of the Physics and Astronomy Classification Scheme (PACS) of papers published by the American Physical Society (APS). We also provide a qualitative comparison of the overall structure of the graph and text embeddings for reference. We find that neural network-based methods outperform traditional methods and graph embedding methods such as node2vec are better than other methods at capturing the PACS structure. Our results call for further investigations into how different contexts of scientific papers are captured by different methods, and how we can combine and leverage such information in an interpretable manner. more...

Recent advances in machine learning research have produced powerful neural graph embedding methods, which learn useful, low-dimensional vector representations of network data. These neural methods for graph embedding excel in graph machine learning tasks and are now widely adopted. However, how and why these methods work -- particularly how network structure gets encoded in the embedding -- remain largely unexplained. Here, we show that node2vec -- shallow, linear neural network -- encodes communities into separable clusters better than random partitioning down to the information-theoretic detectability limit for the stochastic block models. We show that this is due to the equivalence between the embedding learned by node2vec and the spectral embedding via the eigenvectors of the symmetric normalized Laplacian matrix. Numerical simulations demonstrate that node2vec is capable of learning communities on sparse graphs generated by the stochastic blockmodel, as well as on sparse degree-heterogeneous networks. Our results highlight the features of graph neural networks that enable them to separate communities in embedding space., Comment: 46 pages, 12 figures more...

Graph embedding maps a graph into a convenient vector-space representation for graph analysis and machine learning applications. Many graph embedding methods hinge on a sampling of context nodes based on random walks. However, random walks can be a biased sampler due to the structural properties of graphs. Most notably, random walks are biased by the degree of each node, where a node is sampled proportionally to its degree. The implication of such biases has not been clear, particularly in the context of graph representation learning. Here, we investigate the impact of the random walks' bias on graph embedding and propose residual2vec, a general graph embedding method that can debias various structural biases in graphs by using random graphs. We demonstrate that this debiasing not only improves link prediction and clustering performance but also allows us to explicitly model salient structural properties in graph embedding., Comment: 28 pages, 8 figures, 3 tables more...

Correlation matrices are a major type of multivariate data. To examine properties of a given correlation matrix, a common practice is to compare the same quantity between the original correlation matrix and reference correlation matrices, such as those derived from random matrix theory, that partially preserve properties of the original matrix. We propose a model to generate such reference correlation and covariance matrices for the given matrix. Correlation matrices are often analysed as networks, which are heterogeneous across nodes in terms of the total connectivity to other nodes for each node. Given this background, the present algorithm generates random networks that preserve the expectation of total connectivity of each node to other nodes, akin to configuration models for conventional networks. Our algorithm is derived from the maximum entropy principle. We will apply the proposed algorithm to measurement of clustering coefficients and community detection, both of which require a null model to assess the statistical significance of the obtained results., Comment: 8 figures, 4 tables more...

Many empirical networks have community structure, in which nodes are densely interconnected within each community (i.e., a group of nodes) and sparsely across different communities. Like other local and meso-scale structure of networks, communities are generally heterogeneous in various aspects such as the size, density of edges, connectivity to other communities and significance. In the present study, we propose a method to statistically test the significance of individual communities in a given network. Compared to the previous methods, the present algorithm is unique in that it accepts different community-detection algorithms and the corresponding quality function for single communities. The present method requires that a quality of each community can be quantified and that community detection is performed as optimisation of such a quality function summed over the communities. Various community detection algorithms including modularity maximisation and graph partitioning meet this criterion. Our method estimates a distribution of the quality function for randomised networks to calculate a likelihood of each community in the given network. We illustrate our algorithm by synthetic and empirical networks., Comment: 20 pages, 4 figures and 4 tables more...

A network with core-periphery structure consists of core nodes that are densely interconnected. In contrast to community structure, which is a different meso-scale structure of networks, core nodes can be connected to peripheral nodes and peripheral nodes are not densely interconnected. Although core-periphery structure sounds reasonable, we argue that it is merely accounted for by heterogeneous degree distributions, if one partitions a network into a single core block and a single periphery block, which the famous Borgatti-Everett algorithm and many succeeding algorithms assume. In other words, there is a strong tendency that high-degree and low-degree nodes are judged to be core and peripheral nodes, respectively. To discuss core-periphery structure beyond the expectation of the node's degree (as described by the configuration model), we propose that one needs to assume at least one block of nodes apart from the focal core-periphery structure, such as a different core-periphery pair, community or nodes not belonging to any meso-scale structure. We propose a scalable algorithm to detect pairs of core and periphery in networks, controlling for the effect of the node's degree. We illustrate our algorithm using various empirical networks., Comment: 56 pages, 25 figures and 4 tables. C++ and MATLAB codes are available at https://github.com/skojaku/km_config/ more...

With a core-periphery structure of networks, core nodes are densely interconnected, peripheral nodes are connected to core nodes to different extents, and peripheral nodes are sparsely interconnected. Core-periphery structure composed of a single core and periphery has been identified for various networks. However, analogous to the observation that many empirical networks are composed of densely interconnected groups of nodes, i.e., communities, a network may be better regarded as a collection of multiple cores and peripheries. We propose a scalable algorithm to detect multiple non-overlapping groups of core-periphery structure in a network. We illustrate our algorithm using synthesised and empirical networks. For example, we find distinct core-periphery pairs with different political leanings in a network of political blogs and separation between international and domestic subnetworks of airports in some single countries in a world-wide airport network., Comment: 11 figures and 9 tables. MATLAB codes are available at www.naokimasuda.net/cp_codes.zip more...