Hierarchical structure and the prediction of missing links in networks
Open accessThe DOI matches its Crossref record; 34 of the 35 references it cites were found in a registry or an index.
Abstract
Networks have in recent years emerged as an invaluable tool for describing and quantifying complex systems in many branches of science. Recent studies suggest that networks often exhibit hierarchical organization, in which vertices divide into groups that further subdivide into groups of groups, and so forth over multiple scales. In many cases the groups are found to correspond to known functional units, such as ecological niches in food webs, modules in biochemical networks (protein interaction networks, metabolic networks or genetic regulatory networks) or communities in social networks. Here we present a general technique for inferring hierarchical structure from network data and show that the existence of hierarchy can simultaneously explain and quantitatively reproduce many commonly observed topological properties of networks, such as right-skewed degree distributions, high clustering coefficients and short path lengths. We further show that knowledge of hierarchical structure can be used to predict missing connections in partly known networks with high accuracy, and for more general network structures than competing techniques. Taken together, our results suggest that hierarchy is a central organizing principle of complex networks, capable of offering insight into many network phenomena.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“Although previous work using complex networks theory has quantitatively tackled the problem [3, 4, 22-25, 27-31], some questions remain:”
From On the origins of hierarchy in complex networks (2013) · cites this paper as [27]
The cited source says what the claim attributes to it.
In the citing paper
“Since edges in complex networks can often be explained via latent hierarchies over their nodes [8], we are interested in the benefits of Poincaré embeddings both in terms representation size and generalization performance.”
From Poincaré Embeddings for Learning Hierarchical Representations (2017) · cites this paper as [8]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Elements of Statistical Learning
Hastie, T., Friedman, J., & Tibshirani, R. (2001) · Springer Series in Statistics · doi:10.1007/978-0-387-21606-5 · Cited by 24,162
The meaning and use of the area under a receiver operating characteristic (ROC) curve.
Hanley, J. A., & McNeil, B. J. (1982) · Radiology · doi:10.1148/radiology.143.1.7063747 · Cited by 21,856
Statistical mechanics of complex networks
Albert, R., & Barabási, A.-L. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.47 · Cited by 20,471
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Self-citationSocial Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557
Community structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502
Self-citationFinding community structure in very large networks
Clauset, A., Newman, M. E. J., & Moore, C. (2004) · Physical Review E · doi:10.1103/physreve.70.066111 · Cited by 7,390
Self-citation(2017) · The SAGE Encyclopedia of Communication Research Methods · doi:10.4135/9781483381411.n575 · Cited by 6,008
Casella, G., & Berger, R. (2024) · Chapman & Hall/CRC eBooks · doi:10.1201/9781003456285 · Cited by 5,711
Uncovering the overlapping community structure of complex networks in nature and society
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005) · Nature · doi:10.1038/nature03607 · Cited by 5,373
Research works printed but not linked: 2
- Kleinberg, J. in Proc. 2001 Neural Inform. Processing Systems Conf. (eds Dietterich, T. G., Becker, S. & Ghahramani, Z.) 431–438 (MIT Press, Cambridge, MA, 2002)
- A. Lakhina, J. W. Byers, M. Crovella, P. Xie, Proc. INFOCOM (2003).
Cited by
Items 101–200 of 1,000
Link prediction in complex networks: A local naïve Bayes model
Liu, Z., Zhang, Q.-M., Lü, L., & Zhou, T. (2011) · EPL (Europhysics Letters) · doi:10.1209/0295-5075/96/48007 · Cited by 203
Reconstructing propagation networks with natural diversity and identifying hidden sources
Shen, Z., Wang, W.-X., Fan, Y., Di, Z., & Lai, Y.-C. (2014) · Nature Communications · doi:10.1038/ncomms5323 · Cited by 216
“The averaging process is with respect to the nodal states Sj, j,ai(t) on the right-hand side of the modified dynamical equation (5).”
BackgroundInfluentialIdentification of core-periphery structure in networks
Zhang, X., Martin, T., & Newman, M. E. J. (2015) · Physical Review E · doi:10.1103/physreve.91.032803 · Cited by 206
Self-citationCommunity detection, link prediction, and layer interdependence in multilayer networks
De Bacco, C., Power, E. A., Larremore, D. B., & Moore, C. (2017) · Physical Review E · doi:10.1103/physreve.95.042317 · Cited by 203
“[38] Aaron Clauset, Cristopher Moore, and M.”
MethodSelf-citationJoint Link Prediction and Attribute Inference Using a Social-Attribute Network
Gong, N. Z., Talwalkar, A., Mackey, L., Huang, L., Shin, E. C. R., Stefanov, E., Shi, E. (., & Song, D. (2014) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/2594455 · Cited by 200
“on the original social networks and on the corresponding social-attribute networks (recall that the SAN-based unsupervised algorithms reduce to standard unsupervised link-prediction algorithms when working solely with the original social networks).”
BackgroundMethodFast and accurate link prediction in social networking systems
Papadimitriou, A., Symeonidis, P., & Manolopoulos, Y. (2012) · Journal of Systems and Software · doi:10.1016/j.jss.2012.04.019 · Cited by 196
“Furthermore, we use the AUC statistic to quantify the accuracy of prediction algorithms and test how much better they are than pure chance, similarly to the experimental protocol followed by Clauset hierarchical structure [19].”
MethodInfluentialTolerating the community detection resolution limit with edge weighting
Berry, J. W., Hendrickson, B., LaViolette, R. A., & Phillips, C. A. (2011) · Physical Review E · doi:10.1103/physreve.83.056119 · Cited by 188
Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces
Papadopoulos, F., Krioukov, D., Boguna, M., & Vahdat, A. (2010) · 2010 Proceedings IEEE INFOCOM · doi:10.1109/infcom.2010.5462131 · Cited by 179
Combining complex networks and data mining: Why and how
Zanin, M., Papo, D., Sousa, P. A., Menasalvas, E., Nicchi, A., Kubik, E., & Boccaletti, S. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.04.005 · Cited by 165
Towards knowledge graph reasoning for supply chain risk management using graph neural networks
Kosasih, E. E., Margaroli, F., Gelli, S., Aziz, A., Wildgoose, N., & Brintrup, A. (2024) · International Journal of Production Research · doi:10.1080/00207543.2022.2100841 · Cited by 158
“An example of such algorithm is hierarchical random graph model proposed by Clauset, Moore, and Newman (2008).”
Method20 years of network community detection
Fortunato, S., & Newman, M. E. J. (2022) · Nature Physics · doi:10.1038/s41567-022-01716-7 · Cited by 184
Self-citationSupervised Random Walks: Predicting and Recommending Links in Social NetworksPreprint
Bäckström, L., & Leskovec, J. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1011.4071 · Cited by 195
“Similarly, link prediction can also be used for prediction of missing or unobserved links in networks [9] or to suggest which individuals may be working together even though their interaction has yet been directly observed.”
BackgroundRandom graphs containing arbitrary distributions of subgraphs
Karrer, B., & Newman, M. E. J. (2010) · Physical Review E · doi:10.1103/physreve.82.066118 · Cited by 198
Self-citationZhang, P., & Moore, C. (2014) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1409770111 · Cited by 187
Self-citationA gene ontology inferred from molecular networks
Dutkowski, J., Kramer, M., Surma, M. A., Balakrishnan, R., Cherry, J. M., Krogan, N. J., & Ideker, T. (2013) · Nature Biotechnology · doi:10.1038/nbt.2463 · Cited by 184
Efficiently inferring community structure in bipartite networks
Larremore, D. B., Clauset, A., & Jacobs, A. Z. (2014) · Physical Review E · doi:10.1103/physreve.90.012805 · Cited by 182
Self-citationConnectivity and complex systems: learning from a multi-disciplinary perspective
Turnbull, L., Hütt, M.-T., Ioannides, A. A., Kininmonth, S., Poeppl, R., Tockner, K., Bracken, L. J., Keesstra, S., Liu, L., Masselink, R., et al. (2018) · Applied Network Science · doi:10.1007/s41109-018-0067-2 · Cited by 171
“In recent years networks have emerged as an invaluable tool for describing and quantifying complex systems, especially due to the ease with which networks can be used to represent hierarchical organization over multiple scales (Clauset et al., 2008).”
BackgroundDisentangling direct from indirect relationships in association networks
Xiao, N., Zhou, A., Kempher, M. L., Zhou, B. Y., Shi, Z. J., Yuan, M., Guo, X., Wu, L., Ning, D., Van Nostrand, J., et al. (2022) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2109995119 · Cited by 180
Inferring the mesoscale structure of layered, edge-valued, and time-varying networks
Peixoto, T. P. (2015) · Physical Review E · doi:10.1103/physreve.92.042807 · Cited by 164
“de descriptions of the same network, and in particular separate actual structure from stochastic fluctuations? In this work, we tackle both of these questions by formulating generative models of layered networks, obtained by generalizing several variants of the stochastic block model [29–32], incorporating features su…”
Defining invasiveness and invasibility in ecological networks
Hui, C., Richardson, D. M., Landi, P., Minoarivelo, H. O., Garnas, J., & Roy, H. E. (2016) · Biological Invasions · doi:10.1007/s10530-016-1076-7 · Cited by 164
“Finally, the level of modularity was measured using a new algorithm QuanBimo (Dormann and Straub 2014; adapted from Claused and Newman 2008).”
MethodMutualistic networks: moving closer to a predictive theory
Valdovinos, F. S. (2019) · Ecology Letters · doi:10.1111/ele.13279 · Cited by 161
Link Prediction in Criminal Networks: A Tool for Criminal Intelligence Analysis
Berlusconi, G., Calderoni, F., Parolini, N., Verani, M., & Piccardi, C. (2016) · PLoS ONE · doi:10.1371/journal.pone.0154244 · Cited by 169
Temporal link prediction by integrating content and structure information
Gao, S., Denoyer, L., & Gallinari, P. (2011) · Proceedings of the 20th ACM international conference on Information and knowledge management · doi:10.1145/2063576.2063744 · Cited by 158
A Scalable Generative Graph Model with Community Structure
Kolda, T. G., Pınar, A., Plantenga, T. D., & Seshadhri, C. (2014) · SIAM Journal on Scientific Computing · doi:10.1137/130914218 · Cited by 186
“We also ignore complex community structure, such as bipartite or near-bipartite community structure as well as hierarchical structure, which has been observed in real-world applications [38, 12].”
BackgroundCommunity Detection in Multi-Layer Networks Using Joint Nonnegative Matrix Factorization
Ma, X., Dong, D., & Wang, Q. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2018.2832205 · Cited by 167
“logical networks [2], and biological networks [3].”
Bayesian stochastic blockmodeling
Peixoto, T. P. (2017) · The University of Bath Online Publications Store (The University of Bath) · Cited by 168
Systemic Risk Analysis on Reconstructed Economic and Financial Networks
Cimini, G., Squartini, T., Garlaschelli, D., & Gabrielli, A. (2015) · Scientific Reports · doi:10.1038/srep15758 · Cited by 200
“The role of {xi,yi}i∈V in controlling the topology is better clarified by writing ex plicitly the ensemble probability for a directed connection between any two nodesi and j:12 pi→ j ≡ 〈ai→ j〉Ω = x jyi 1+ x jyi , (1)”
BackgroundNetwork Reconstruction Based on Evolutionary-Game Data via Compressive Sensing
Wang, W.-X., Lai, Y.-C., Grebogi, C., & Ye, J. (2011) · Physical Review X · doi:10.1103/physrevx.1.021021 · Cited by 159
“In the past few years, the problem of network reconstruction has received growing attention [9–16].”
BackgroundGoñi, J., Arrondo, G., Sepulcre, J., Martincorena, I., de Mendizábal, N. V., Corominas‐Murtra, B., Bejarano, B., Ardanza-Trevijano, S., Peraita, H., Wall, D. P., et al. (2010) · Cognitive Processing · doi:10.1007/s10339-010-0372-x · Cited by 190
“, predicting real missed links based on those already observed (Yip and Horvath 2007; Clauset et al. 2008) and detecting both missing and spurious links (Guimera and Sales-Pardo 2009).”
BackgroundLeroy, V., Cambazoglu, B. B., & Bonchi, F. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835855 · Cited by 160
A Maximal Clique Based Multiobjective Evolutionary Algorithm for Overlapping Community Detection
Wen, X., Chen, W.-N., Lin, Y., Gu, T., Zhang, H., Li, Y., Yin, Y., & Zhang, J. (2016) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2016.2605501 · Cited by 162
Recent advances in clustering methods for protein interaction networks
Wang, J., Li, M., Deng, Y., & Pan, Y. (2010) · BMC Genomics · doi:10.1186/1471-2164-11-s3-s10 · Cited by 160
“For merging vertices or separating the graph, various heuristic rules have been used, such as betweenness centrality [26-36], clustering coefficient [29,37-41], minimum cut [42], and etc.”
MethodThe temporal dynamics of resource use by frugivorous birds: a network approach
Carnicer, J., Jordano, P., & Melián, C. J. (2009) · Ecology · doi:10.1890/07-1939.1 · Cited by 163
“…have provided an appealing way to visualize and synthesize the structure of ecological interactions ( Guimerà and Amaral 2005, Olesen et al. 2007 , Clauset et al. 2008, Rooney et al. 2008) , to study their emergent properties ( Bascompte et al. 2003 , Jordano et al. 2003) , and to analyze the…”
Community extraction for social networks
Zhao, Y., Levina, E., & Zhu, J. (2011) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1006642108 · Cited by 171
Tag-Aware Recommender Systems: A State-of-the-Art Survey
Zhang, Z.-K., Zhou, T., & Zhang, Y.-C. (2011) · Journal of Computer Science and Technology · doi:10.1007/s11390-011-0176-1 · Cited by 159
Bayesian Stochastic Blockmodeling
Peixoto, T. P. (2019) · Wiley eBooks · doi:10.1002/9781119483298.ch11 · Cited by 300
“This has been most explored for the prediction of missing and spurious links [21, 63].”
BackgroundEvaluating Overfit and Underfit in Models of Network Community Structure
Ghasemian, A., Hosseinmardi, H., & Clauset, A. J. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2911585 · Cited by 202
Self-citationOn the origins of hierarchy in complex networks
Corominas-Murtra, B., Goñi, J., Solé, R. V., & Rodríguez-Caso, C. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1300832110 · Cited by 160
Link Prediction on Evolving Data Using Matrix and Tensor Factorizations
Acar, E., Dunlavy, D., & Kolda, T. G. (2009) · IEEE ... International Conference on Data Mining workshops · doi:10.1109/icdmw.2009.54 · Cited by 184
“The temporal link prediction problem is different from missing link prediction, which has no temporal aspect and where the goal is to predict missing connections in order to describe a more complete picture of the overall link structure in the data [7].”
BackgroundOverlapping Communities Explain Core–Periphery Organization of Networks
Yang, J., & Leskovec, J. (2014) · Proceedings of the IEEE · doi:10.1109/jproc.2014.2364018 · Cited by 159
Predicting missing links and identifying spurious links via likelihood analysis
Pan, L., Zhou, T., Lü, L., & Hu, C.-K. (2016) · Scientific Reports · doi:10.1038/srep22955 · Cited by 160
“Representative examples include the hierarchical structure model 22 , the stochastic block model 9 and the Kronecker graphs model 23 .”
InfluentialNetwork Mapping by Replaying Hyperbolic Growth
Papadopoulos, F., Psomas, C., & Krioukov, D. (2015) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2013.2294052 · Cited by 158
“To provide a deeper insight on the HyperMap performance in predicting missing links, we also consider a set of classi cal link prediction methods that have been found to perform well in practice in different studies [7], [8], and compare their performance to HyperMap’s.”
BackgroundMethodResultInfluentialDifferentially private network data release via structural inference
Xiao, Q., Chen, R., & Tan, K. (2014) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2623330.2623642 · Cited by 190
Random graph models for dynamic networks
Zhang, X., Moore, C., & Newman, M. E. J. (2017) · The European Physical Journal B · doi:10.1140/epjb/e2017-80122-8 · Cited by 180
Self-citationThe role of information diffusion in the evolution of social networks
Weng, L., Ratkiewicz, J., Perra, N., Gonçalves, B., Castillo, C., Bonchi, F., Schifanella, R., Menczer, F., & Flammini, A. (2013) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2487575.2487607 · Cited by 178
“Common approaches consider link prediction as a classification task or ranking problem, using node similarity [40, 32], the hierarchical structure of the network [16], random walks [3], graphical models [41], and user profile features [56].”
BackgroundMethodLink Prediction in Time-Evolving Criminal Network With Deep Reinforcement Learning Technique
Lim, M., Abdullah, A. B., Jhanjhi, N. Z., Khan, M. K., & Supramaniam, M. (2019) · IEEE Access · doi:10.1109/access.2019.2958873 · Cited by 151
“In [13], Clauset et al. developed a link prediction model based on the hierarchical random graph.”
MethodProtein–protein interactions: detection, reliability assessment and applications
Peng, X., Wang, J., Peng, W., Wu, F.-X., & Pan, Y. (2016) · Briefings in Bioinformatics · doi:10.1093/bib/bbw066 · Cited by 145
Stacking models for nearly optimal link prediction in complex networks
Ghasemian, A., Hosseinmardi, H., Galstyan, A., Airoldi, E. M., & Clauset, A. J. (2020) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1914950117 · Cited by 181
Self-citationTopological data analysis of contagion maps for examining spreading processes on networks
Taylor, D., Klimm, F., Harrington, H. A., Kramár, M., Mischaikow, K., Porter, M. A., & Mucha, P. J. (2015) · Nature Communications · doi:10.1038/ncomms8723 · Cited by 148
“This has numerous applications, including the denoising of networks (see Supplementary Note 2 and Supplementary Figs 6 and 7).”
ResultInfluentialMacroecological trends in nestedness and modularity of seed‐dispersal networks: human impact matters
Sebastián‐González, E., Dalsgaard, B., Sandel, B., & Guimarães, P. R. (2014) · Global Ecology and Biogeography · doi:10.1111/geb.12270 · Cited by 160
“random graph approach of Clauset et al. (2008), which organ-”
Xu, B., Ye, D., Xing, Z., Xia, X., Chen, G.-B., & Li, S. (2016) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1145/2970276.2970357 · Cited by 171
“Link prediction in complex networks has attracted enormous attention from physics, biochemical, and computer science communities [7, 18, 19, 9, 3, 8].”
BackgroundMachine learning dismantling and early-warning signals of disintegration in complex systems
Grassia, M., Domenico, M. D., & Mangioni, G. (2021) · Nature Communications · doi:10.1038/s41467-021-25485-8 · Cited by 176
Uncovering the structure and temporal dynamics of information propagation
Gomez-Rodriguez, M., Leskovec, J., Balduzzi, D., & Schölkopf, B. (2014) · Network Science · doi:10.1017/nws.2014.3 · Cited by 165
“5]), hierarchical (Clauset et al., 2008) ([0 .”
Strong, Long-Term Temporal Dynamics of an Ecological Network
Olesen, J. M., Stefanescu, C., & Traveset, A. (2011) · PLoS ONE · doi:10.1371/journal.pone.0026455 · Cited by 153
“of high complexity [1,2] and they often reveal surprising,”
BackgroundGraph Mining Applications to Social Network Analysis
Tang, L., & Liu, H. (2010) · The Kluwer international series on advances in database systems · doi:10.1007/978-1-4419-6045-0_16 · Cited by 180
“[16] defines a random graph model for hierarchies such that two actors are connected based on the interaction probability of their least common ancestor node in the hierarchy.”
BackgroundLink prediction in heterogeneous data via generalized coupled tensor factorization
Ermiş, B., Acar, E., & Cemgil, A. T. (2013) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-013-0341-y · Cited by 144
Hierarchically‐Ordered Zeolites: A Critical Assessment
Hartmann, M., Thommes, M., & Schwieger, W. (2021) · Advanced Materials Interfaces · doi:10.1002/admi.202001841 · Cited by 148
Genome‐scale metabolic networks
Terzer, M., Maynard, N. D., Covert, M. W., & Stelling, J. (2009) · WIREs Systems Biology and Medicine · doi:10.1002/wsbm.37 · Cited by 140
“78 Available methods, thus, have limitations in automatically generating predictive network models, and novel concepts, such as Clauset et al., 79 are needed.”
MethodHidden geometric correlations in real multiplex networks
Kleineberg, K.-K., Boguñá, M., Serrano, M. Á., & Papadopoulos, F. (2016) · Nature Physics · doi:10.1038/nphys3812 · Cited by 154
“The problem of link prediction has been extensively studied in the context of predicting missing and future links in single layer networks [43, 44] and its generalization to real-world multilayer systems is recently gaining attention [45].”
BackgroundDiversity of meso-scale architecture in human and non-human connectomes
Betzel, R. F., Medaglia, J. D., & Bassett, D. S. (2018) · Nature Communications · doi:10.1038/s41467-017-02681-z · Cited by 157
“cale structure can be non-assortative. For instance, disassortative structure (Fig. 1B) refers to communities that preferentially avoid forming connections to the other members of their own community [35]. Core-periphery organization (Fig. 1C), on the other hand refers to the presence of a dense, central core communit…”
Community Detection and Classification in Hierarchical Stochastic Blockmodels
Lyzinski, V., Tang, M., Athreya, A., Park, Y., & Priebe, C. E. (2016) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2016.2634322 · Cited by 177
Link Prediction in Complex Networks: A Mutual Information Perspective
Tan, F., Xia, Y., & Zhu, B. (2014) · PLoS ONE · doi:10.1371/journal.pone.0107056 · Cited by 150
“Therefore, accurate prediction is more reasonable compared with blindly checking all latent interaction links [3,4].”
BackgroundMethodPredicting Adverse Drug Events Using Pharmacological Network Models
Cami, A., Arnold, A., Manzi, S., & Reis, B. (2011) · Science Translational Medicine · doi:10.1126/scitranslmed.3002774 · Cited by 131
“We had previously constructed integrated network representations of drug-drug interactions and ADEs and developed ERG ( 36 ) predictive models to identify the most likely “ missing ” edges ( 22 , 37 ) in those networks.”
MethodRole of graph architecture in controlling dynamical networks with applications to neural systems
Kim, J. Z., Soffer, J., Kahn, A. E., Vettel, J. M., Pasqualetti, F., & Bassett, D. S. (2017) · Nature Physics · doi:10.1038/nphys4268 · Cited by 149
Link prediction in paper citation network to construct paper correlation graph
Liu, H., Kou, H., Yan, C., & Qi, L. (2019) · EURASIP Journal on Wireless Communications and Networking · doi:10.1186/s13638-019-1561-7 · Cited by 144
“As far as we know, the similarity-based methods can be used to the large-scale networks, which is because it can calculate the similarity scores between two nodes [7].”
MethodSurvey on graph embeddings and their applications to machine learning problems on graphs
Makarov, I., Kiselev, D., Nikitinsky, N., & Šubelj, L. (2021) · PeerJ Computer Science · doi:10.7717/peerj-cs.357 · Cited by 155
Social Network Analysis: A Survey on Process, Tools, and Application
Singh, S. S., Muhuri, S., Mishra, S., Srivastava, D., Shakya, H. K., & Kumar, N. (2024) · ACM Computing Surveys · doi:10.1145/3648470 · Cited by 169
“For any given graph, probabilistic models evaluate a given objective function and optimize it based on different parameters of the graph [41, 165, 175].”
BackgroundMultilayer Stochastic Block Models Reveal the Multilayer Structure of Complex Networks
Vallès-Català, T., Massucci, F. A., Guimerà, R., & Sales‐Pardo, M. (2016) · Physical Review X · doi:10.1103/physrevx.6.011036 · Cited by 164
Using community information to improve the precision of link prediction methods
Soundarajan, S., & Hopcroft, J. E. (2012) · International World Wide Web Conference (WWW) · doi:10.1145/2187980.2188150 · Cited by 147
“2 Hierarchical Link Prediction We also consider a variety of link prediction methods that are based on the hierarchical link prediction algorithm of Clauset, Moore, and Newman [4].”
BackgroundMethodInfluentialProgresses and challenges in link prediction
Zhou, T. (2021) · iScience · doi:10.1016/j.isci.2021.103217 · Cited by 148
“…better than well-known similarity-based algorithms reported in Zhou et al. (2009) and Cannistraci et al. (2013a), hierarchical structure model (Clauset et al., 2008), and stochastic block model (Guimerà and Sales-Pardo, 2009), while slightly worse than LOOP (Pan et al., 2016), structural…”
BackgroundMethodInfluentialClustering of high throughput gene expression data
Pirim, H., Ekşioğlu, B., Perkins, A., & Yüceer, Ç. (2012) · Computers & Operations Research · doi:10.1016/j.cor.2012.03.008 · Cited by 143
“Communities appear to have a hierarchical structure in most real world contexts (Clauset et al., 2008).”
BackgroundLarge-scale structure of a nation-wide production network
Fujiwara, Y., & Aoyama, H. (2010) · The European Physical Journal B · doi:10.1140/epjb/e2010-00275-2 · Cited by 151
Hyperbolic Graph Attention Network
Zhang, Y., Wang, X., Shi, C., Jiang, X., & Ye, Y. F. (2021) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2021.3081431 · Cited by 219
Potential Theory for Directed Networks
Zhang, Q.-M., Lü, L., Wang, W., Yu-Xiao, & Zhou, T. (2013) · PLoS ONE · doi:10.1371/journal.pone.0055437 · Cited by 136
“The hierarchical organization is a well-known macroscopic feature for many undirected [36,37] and directed [38,39] networks, and our work indicates that for directed networks, nodes tend to be locally self-organized in a hierarchical manner.”
BackgroundCurvature and temperature of complex networks
Krioukov, D., Papadopoulos, F., Vahdat, A., & Boguñá, M. (2009) · Physical Review E · doi:10.1103/physreve.80.035101 · Cited by 126
Networks for systems biology: conceptual connection of data and function
Emmert‐Streib, F., & Dehmer, M. (2011) · IET Systems Biology · doi:10.1049/iet-syb.2010.0025 · Cited by 135
OWA operator based link prediction ensemble for social network
He, Y., Liu, J. N. K., Hu, Y., & Wang, X. (2014) · Expert Systems with Applications · doi:10.1016/j.eswa.2014.07.018 · Cited by 129
“There are two representative maximum likelihood methods: hierarchical structure method (Clauset et al., 2008) and stochastic block method (Airoldi et al., 2008).”
MethodSubgraph Robustness of Complex Networks Under Attacks
Shang, Y. (2017) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2017.2733545 · Cited by 129
Kuwae, T., Miyoshi, E., Hosokawa, S., Ichimi, K., Hosoya, J., Amano, T., Moriya, T., Kondoh, M., Ydenberg, R. C., & Elner, R. W. (2012) · Ecology Letters · doi:10.1111/j.1461-0248.2012.01744.x · Cited by 126
“Theoretical study can further incorporate empirical data for species traits and link strengths to simulate a real world context, as well as statistically and computationally identify missing and spurious links (Clauset et al. 2008).”
BackgroundSuperlinear scaling for innovation in cities
Arbesman, S., Kleinberg, J. M., & Strogatz, S. H. (2009) · Physical Review E · doi:10.1103/physreve.79.016115 · Cited by 123
Evolutionary informatics: unifying knowledge about the diversity of life
Parr, C. S., Guralnick, R., Cellinese, N., & Page, R. (2011) · Trends in Ecology & Evolution · doi:10.1016/j.tree.2011.11.001 · Cited by 136
Link prediction with node clustering coefficient
Wu, Z., Lin, Y., Wang, J., & Gregory, S. (2016) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2016.01.038 · Cited by 129
Community detection: Topological vs. topical
Ding, Y. (2011) · Journal of Informetrics · doi:10.1016/j.joi.2011.02.006 · Cited by 143
Co-Embedding of Nodes and Edges With Graph Neural Networks
Jiang, X., Zhu, R., Ji, P., & Li, S. (2020) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2020.3029762 · Cited by 149
The dynamical structure of political corruption networks
Ribeiro, H. V., Alves, L. G. A., Martins, A. F., Lenzi, E. K., & Perc, M. (2018) · Journal of Complex Networks · doi:10.1093/comnet/cny002 · Cited by 150
Prediction of Links and Weights in Networks by Reliable Routes
Zhao, J., Miao, L., Yang, J., Fang, H., Zhang, Q.-M., Nie, M., Holme, P., & Zhou, T. (2015) · Scientific Reports · doi:10.1038/srep12261 · Cited by 131
Community detection and graph partitioning
Newman, M. E. J. (2013) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/103/28003 · Cited by 135
“…approaches to the problem have been considered, but interest in recent years has focused particularly on statistical inference methods [3–5], partly because they give excellent results, but also because they are mathematically principled and, at least in some cases, provably optimal [5,…”
Self-citationStatistical inference links data and theory in network science
Peel, L., Peixoto, T. P., & Domenico, M. D. (2022) · Nature Communications · doi:10.1038/s41467-022-34267-9 · Cited by 142
Influence Maximization in Continuous Time Diffusion NetworksPreprint
Gomez-Rodriguez, M., & Schölkopf, B. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1205.1682 · Cited by 136
Graph regularized nonnegative matrix factorization for temporal link prediction in dynamic networks
Ma, X., Sun, P., & Wang, Y. (2017) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2017.12.092 · Cited by 123
Reconstructing Networks with Unknown and Heterogeneous Errors
Peixoto, T. P. (2018) · Physical Review X · doi:10.1103/physrevx.8.041011 · Cited by 161
“Our method shares some underlying similarities with well-known model-based approaches of edge prediction [5,6] but is different from them in fundamental aspects.”
BackgroundMethodUncovering the hidden geometry behind metabolic networks
Serrano, M. Á., Boguñá, M., & Sagués, F. (2012) · Molecular BioSystems · doi:10.1039/c2mb05306c · Cited by 124
Research Commentary—Information in Digital, Economic, and Social Networks
Sundararajan, A., Provost, F., Oestreicher-Singer, G., & Aral, S. (2013) · Information Systems Research · doi:10.1287/isre.1120.0472 · Cited by 115
Extending psychometric network analysis: Empirical evidence against g in favor of mutualism?
Kan, K.-J., van der Maas, H. L. J., & Levine, S. Z. (2019) · Intelligence · doi:10.1016/j.intell.2018.12.004 · Cited by 106
Heterogeneous Hypergraph Variational Autoencoder for Link Prediction
Fan, H., Zhang, F., Wei, Y., Li, Z., Zou, C., Gao, Y., & Dai, Q. (2021) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2021.3059313 · Cited by 147
“…analysis, aims to predict whether two nodes in a network are likely to have a link which is ubiquitous in a multitude of application domains, such as social relation finding [1], [2], knowledge graph completion [3], [4], protein interaction prediction [5], [6], and product recommendation [7], [8].”
BackgroundLink Prediction Based on Graph Topology: The Predictive Value of Generalized Clustering CoefficientPreprint
Huang, Z. (2010) · SSRN Electronic Journal · doi:10.2139/ssrn.1634014 · Cited by 125
Social Network Analysis in the Study of Terrorism and Insurgency: From Organization to Politics
Zech, S. T., & Gabbay, M. (2016) · International Studies Review · doi:10.1093/isr/viv011 · Cited by 125
Ringsmuth, A. K., Landsberg, M. J., & Hankamer, B. D. (2016) · Renewable and Sustainable Energy Reviews · doi:10.1016/j.rser.2016.04.016 · Cited by 119
Structure and Response in the World Trade Network
He, J., & Deem, M. W. (2010) · Physical Review Letters · doi:10.1103/physrevlett.105.198701 · Cited by 113
Link prediction via matrix completion
Pech, R., Hao, D., Pan, L., Cheng, H., & Zhou, T. (2017) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/117/38002 · Cited by 123
Metadata
- Authors
- Clauset, A., Moore, C., & Newman, M. E. J.
- Affiliations
- University of New Mexico (US)
- Santa Fe Institute (US)
- Corresponding author
- Clauset, Aaron
- Venue
- Nature
- Published
- 2008-05
- Volume
- 453
- Issue
- 7191
- Pages
- 98-101
- ISSN
- 0028-0836 (ISSN-L)
- 1476-4687
- OpenAlex
- W2157082398
- Cited by
- 2,171
- References
- 35
- Citations by year
- 2026: 35 · 2025: 58 · 2024: 78 · 2023: 99 · 2022: 157 · 2021: 152 · 2020: 167 · 2019: 141 · 2018: 170 · 2017: 132 · 2016: 162 · 2015: 127 · 2014: 131 · 2013: 128 · 2012: 115
- FWCI
- 81.70
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Nature (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- Deep Blue (University of Michigan) (submittedVersion)
- RePEc: Research Papers in Economics (submittedVersion)
- arXiv (Cornell University)
- Funders
- University of Michigan
- Santa Fe Institute
- Topics
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Bioinformatics and Genomic Networks
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Graph theory and applications
- Keywords
- network hierarchy, missing link prediction, community detection, complex networks, incomplete network data, degree distribution, clustering coefficient, network topology, protein-protein interaction network, food webs, social networks
- MeSH terms
- Algorithms, Models, Biological, Probability, Protein Binding, Sensitivity and Specificity, Social Behavior, Food Chain, Gene Regulatory Networks, Metabolic Networks and Pathways, Biosynthetic Pathways
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.