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)
- Lakhina, A., Byers, J. W., Crovella, M. & Xie, P. in INFOCOM 2003: Twenty-Second Annual Joint Conf. IEEE Computer and Communications Societies (ed. Bauer, F.) Vol. 1 332–341 (IEEE, Piscataway, New Jersey, 2003)
Cited by
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
“Clauset et al. (Clauset et al., 2007; Clauset et al., 2008) described the hierarchical organization of a graph by introducing a class of hierarchical random graphs.”
BackgroundMethodInfluentialMolecular ecological network analyses
Deng, Y., Jiang, Y.-H., Yang, Y., He, Z., Luo, F., & Zhou, J. (2012) · BMC Bioinformatics · doi:10.1186/1471-2105-13-113 · Cited by 3,196
“Most complex systems have common characteristics such as small world, scale-free, modularity and hierarchy [8,53,54].”
BackgroundLink prediction in complex networks: A survey
Lü, L., & Zhou, T. (2011) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2010.11.027 · Cited by 2,819
Newman, M. (2018) · doi:10.1093/oso/9780198805090.001.0001 · Cited by 2,297
Self-citationStochastic blockmodels and community structure in networks
Karrer, B., & Newman, M. E. J. (2011) · Physical Review E · doi:10.1103/physreve.83.016107 · Cited by 2,025
Self-citationLink communities reveal multiscale complexity in networks
Ahn, Y.-Y., Bagrow, J. P., & Lehmann, S. (2010) · Nature · doi:10.1038/nature09182 · Cited by 1,949
“Several prominent methods for finding hierarchical organization exist, 12,13 however, none are able to handle overlap since hierarchical structure always assumes disjoint community partition.”
BackgroundMethodPredicting missing links via local information
Zhou, T., Lü, L., & Zhang, Y.-C. (2009) · The European Physical Journal B · doi:10.1140/epjb/e2009-00335-8 · Cited by 1,813
Graph embedding techniques, applications, and performance: A survey
Goyal, P., & Ferrara, E. (2018) · Knowledge-Based Systems · doi:10.1016/j.knosys.2018.03.022 · Cited by 1,801
“Approaches for link prediction include similarity based methods [13], [14], maximum likelihood models [15], [16], and probabilistic models [17],”
MethodIndices, Graphs and Null Models: Analyzing Bipartite Ecological Networks
Dormann, C. F., Frund, J., Bluthgen, N., & Gruber, B. (2009) · The Open Ecology Journal · doi:10.2174/1874213000902010007 · Cited by 1,772
Introducing the bipartite Package: Analysing Ecological Networks
Dormann, C. F., Gruber, B., & Fründ, J. (2008) · GoeScholar The Publication Server of the Georg-August-Universität Göttingen (Georg-August-Universität Göttingen) · Cited by 1,893
Finding Statistically Significant Communities in Networks
Lancichinetti, A., Radicchi, F., Ramasco, J. J., & Fortunato, S. (2011) · PLoS ONE · doi:10.1371/journal.pone.0018961 · Cited by 1,187
“Instead, a method should be able to recognize if there is hierarchical structure and, if yes, identify the corresponding levels [27–29].”
Modular and hierarchically modular organization of brain networks
Meunier, D., Lambiotte, R., & Bullmore, E. T. (2010) · Frontiers in Neuroscience · doi:10.3389/fnins.2010.00200 · Cited by 1,156
“…methods aiming at uncovering hierarchies made of overlapping communities by partitioning the links of the network (Evans and Lambiotte, 2009; Ahn et al., 2010), as well as methods based on the likelihood of hierarchical random graphs to have generated the system in question (Clauset et al., 2008).”
MethodHyperbolic geometry of complex networks
Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., & Boguñá, M. (2010) · Physical Review E · doi:10.1103/physreve.82.036106 · Cited by 1,059
Finding overlapping communities in networks by label propagation
Gregory, S. (2010) · New Journal of Physics · doi:10.1088/1367-2630/12/10/103018 · Cited by 806
Supervised random walks: predicting and recommending links in social networks
Backstrom, L., & Leskovec, J. (2011) · Proceedings of the fourth ACM international conference on Web search and data mining · doi:10.1145/1935826.1935914 · Cited by 982
“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.”
BackgroundPhylogenetic Molecular Ecological Network of Soil Microbial Communities in Response to Elevated CO 2
Zhou, J., Deng, Y., Luo, F., He, Z., & Yang, Y. (2011) · mBio · doi:10.1128/mbio.00122-11 · Cited by 939
Performance of modularity maximization in practical contexts
Good, B. H., de Montjoye, Y.-A., & Clauset, A. (2010) · Physical Review E · doi:10.1103/physreve.81.046106 · Cited by 937
Self-citationWang, D., Wang, J., Lu, M., Song, F., & Cui, Q. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq241 · Cited by 913
Consensus clustering in complex networks
Lancichinetti, A., & Fortunato, S. (2012) · Scientific Reports · doi:10.1038/srep00336 · Cited by 795
“Also, in order to deliver possibly more reliable results, methods should ideally exploit all features of the system, like edge directedness and weight (for directed and weighted networks, respectively), and account for properties of the partitions, like hierarch”
MethodStructure and dynamics of molecular networks: A novel paradigm of drug discovery
Csermely, P., Korcsmáros, T., Kiss, H. J. M., London, G., & Nussinov, R. (2013) · Pharmacology & Therapeutics · doi:10.1016/j.pharmthera.2013.01.016 · Cited by 892
“• Edge prediction can be performed by comparing the network to an appropriately selectedmodel network, to a similar real world network, or to an ensemble of networks (Liben-Nowell & Kleinberg, 2007; Clauset et al., 2008; Nepusz et al., 2008; Xu et al., 2011a; Gutfraind et al., 2012).”
MethodBroido, A. D., & Clauset, A. (2019) · Nature Communications · doi:10.1038/s41467-019-08746-5 · Cited by 875
Self-citationRosvall, M., Axelsson, D., & Bergstrom, C. T. (2009) · The European Physical Journal Special Topics · doi:10.1140/epjst/e2010-01179-1 · Cited by 844
Kronecker Graphs: An Approach to Modeling Networks
Leskovec, J., Chakrabarti, D., Kleinberg, J. M., Faloutsos, C., & Ghahramani, Z. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0812.4905 · Cited by 697
“Thus, we simulate draws from the permutation distributionP (σ|G,Θ), and then evaluate the quantities at the sampled permutations to obtain the expected values of log-likelihood and gradient.”
BackgroundMethodA Survey of Statistical Network Models
Goldenberg, A., Zheng, A. X., Fienberg, S. E., & Airoldi, E. M. (2010) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000005 · Cited by 819
“, predicting missing links in the network [238; 73; 198], or attribute related, e.”
Missing and spurious interactions and the reconstruction of complex networks
Guimerà, R., & Sales-Pardo, M. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0908366106 · Cited by 797
Communities, modules and large-scale structure in networks
Newman, M. E. J. (2012) · Nature Physics · doi:10.1038/nphys2162 · Cited by 787
“5 shows one example, drawn from my own work 71 .”
Self-citationDecelle, A., Krzakala, F., Moore, C., & Zdeborová, L. (2011) · Physical Review E · doi:10.1103/physreve.84.066106 · Cited by 747
Self-citationRobustness and resilience of complex networks
Artime, O., Grassia, M., De Domenico, M., Gleeson, J. P., Makse, H. A., Mangioni, G., Perc, M., & Radicchi, F. (2024) · Nature Reviews Physics · doi:10.1038/s42254-023-00676-y · Cited by 672
Inferring networks of diffusion and influence
Gomez Rodriguez, M., Leskovec, J., & Krause, A. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835933 · Cited by 679
A Survey of Link Prediction in Complex Networks
Martínez, V., Berzal, F., & Cubero, J.-C. (2017) · ACM Computing Surveys · doi:10.1145/3012704 · Cited by 695
“The method proposed by Clauset et al. [2008] represents a hierarchically structured network by a dendrogram with | V | leaves and | V | − 1 internal nodes.”
MethodInferring Networks of Diffusion and Influence
Gomez-Rodriguez, M., Leskovec, J., & Krause, A. (2012) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2086737.2086741 · Cited by 445
Similarity index based on local paths for link prediction of complex networks
Lü, L., Jin, C.-H., & Zhou, T. (2009) · Physical Review E · doi:10.1103/physreve.80.046122 · Cited by 678
Poincaré Embeddings for Learning Hierarchical Representations
Nickel, M., & Kiela, D. (2017) · arXiv · doi:10.48550/arxiv.1705.08039 · Cited by 667
A method for detecting modules in quantitative bipartite networks
Dormann, C. F., & Strauss, R. (2014) · Methods in Ecology and Evolution · doi:10.1111/2041-210x.12139 · Cited by 533
“The focus of virtually all these algorithms was on unweighted and one-mode networks (see, e.g., Clauset et al. , 2008; Lancichinetti & Fortunato, 2011; Jacobi et al. , 2012, for a recent examples).”
BackgroundMethodPopularity versus similarity in growing networks
Papadopoulos, F., Kitsak, M., Serrano, M. Á., Boguñá, M., & Krioukov, D. (2012) · Nature · doi:10.1038/nature11459 · Cited by 634
“The framework may thus be used for link prediction, a notoriously difficult and important problem in many disciplines [29], with applications ranging from predicting protein interactions or terrorist connections to designing recommender and collaborative filtering systems [30].”
MethodSimplicial closure and higher-order link prediction
Benson, A. R., Abebe, R., Schaub, M. T., Jadbabaie, A., & Kleinberg, J. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1800683115 · Cited by 548
Schwieger, W., Machoke, A. G., Weissenberger, T., Inayat, A., Selvam, T., Klumpp, M., & Inayat, A. (2016) · Chemical Society Reviews · doi:10.1039/c5cs00599j · Cited by 575
Link prediction based on local random walk
Liu, W., & Lü, L. (2010) · EPL (Europhysics Letters) · doi:10.1209/0295-5075/89/58007 · Cited by 572
Link prediction in social networks: the state-of-the-art
Wang, P., Xu, B., Wu, Y., & Zhou, X. (2015) · Science China Information Sciences · doi:10.1007/s11432-014-5237-y · Cited by 548
“Clauset et al.[59] proposed a model to infer hierarchical structure from network and apply it to solve the link prediction problem.”
BackgroundA Survey of Link Prediction in Social Networks
Hasan, M. A., & Zaki, M. J. (2011) · Social Network Data Analytics · doi:10.1007/978-1-4419-8462-3_9 · Cited by 566
Temporal Link Prediction Using Matrix and Tensor Factorizations
Dunlavy, D. M., Kolda, T. G., & Acar, E. (2011) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1921632.1921636 · Cited by 375
“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 [Clauset et al. 2008].”
BackgroundImproved community detection in weighted bipartite networks
Beckett, S. J. (2016) · Royal Society Open Science · doi:10.1098/rsos.140536 · Cited by 530
Link prediction techniques, applications, and performance: A survey
Kumar, A., Singh, S. S., Singh, K., & Biswas, B. (2020) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2020.124289 · Cited by 516
Communities in NetworksPreprint
Porter, M. A., Onnela, J.-P. “., & Mucha, P. J. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0902.3788 · Cited by 536
“et’s consider the departmental organization at a university and suppose that the network in Fig. 0.3 represents collaborations among professors. (It actually represents grassland species interactions [23].) At one level of inspection, everybody in the mathematics department might show up in one community, such as the…”
BackgroundMethodInfluentialLaplacian Dynamics and Multiscale Modular Structure in Networks
Lambiotte, R., Delvenne, J., & Barahona, M. (2008) · doi:10.48550/arxiv.0812.1770 · Cited by 345
Dynamics of information diffusion and its applications on complex networks
Zhang, Z.-K., Liu, C., Zhan, X.-X., Lu, X., Zhang, C.-X., & Zhang, Y.-C. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.07.002 · Cited by 484
Navigability of complex networks
Boguñá, M., Krioukov, D., & Claffy, K. C. (2009) · Nature Physics · doi:10.1038/nphys1130 · Cited by 486
Statistical Models for Social Networks
Snijders, T. A. B. (2011) · Annual Review of Sociology · doi:10.1146/annurev.soc.012809.102709 · Cited by 460
“Almost the same model was proposed later by Clauset et al. (2008). For each ‘level’ k, the graph with edge set Ek can be regarded as a ‘smoothed’ version of the observed graph, representing the setting structure at level k, where k = 1 represents the most fine-grained and the maximum value k = K the most coarse settin…”
Wildlife diseases: from individuals to ecosystems: Ecology of wildlife diseases
Tompkins, D. M., Dunn, A. M., Smith, M. J., & Telfer, S. (2011) · Journal of Animal Ecology · doi:10.1111/j.1365-2656.2010.01742.x · Cited by 448
The ground truth about metadata and community detection in networks
Peel, L., Larremore, D. B., & Clauset, A. (2017) · Science Advances · doi:10.1126/sciadv.1602548 · Cited by 449
Self-citationUnderstanding brain networks and brain organization
Pessoa, L. (2014) · Physics of Life Reviews · doi:10.1016/j.plrev.2014.03.005 · Cited by 464
“In a similar vein, most real-world networks have multiple plausible hierarchical representations of roughly equal likelihood [146, 147].”
BackgroundFriendship prediction and homophily in social media
Aiello, L. M., Barrat, A., Schifanella, R., Cattuto, C., Markines, B., & Menczer, F. (2012) · ACM Transactions on the Web · doi:10.1145/2180861.2180866 · Cited by 441
Comparing Community Structure to Characteristics in Online Collegiate Social Networks
Red, V., Kelsic, E. D., Mucha, P. J., & Porter, M. A. (2011) · SIAM Review · doi:10.1137/080734315 · Cited by 331
“One of the presently dominant approaches in community detection involves the optimization of a quality function known as modularity, which counts the total edge weight of all intra-community connections compared to that which might be expected at random (under some null model) [27,71,73,74,76], though there are also n…”
BackgroundMethodInfluentialRandom Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
Lambiotte, R., Delvenne, J.-C., & Barahona, M. (2014) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2015.2391998 · Cited by 398
“This relationship is particularly relevant when the network is composed of tightly-knit modules or communities [4], [5], [6], [7], [8], [9], which can lead, for instance, to partially coherent dynamics [10], [11], or to the emergence of co-operation [12] and coexistence of heterogeneous ideas in a…”
BackgroundSpectral methods for community detection and graph partitioning
Newman, M. E. J. (2013) · Physical Review E · doi:10.1103/physreve.88.042822 · Cited by 424
“Along with many studies focusing on local properties of networks, such as clustering [3], degree distributions [4, 5], and correlations [6, 7], are studies that examine large-scale properties like path lengths [3], percolation [8, 9], or hierarchy [10, 11].”
Self-citationUncovering the Temporal Dynamics of Diffusion Networks
Gomez-Rodriguez, M., Balduzzi, D., & Schölkopf, B. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1105.0697 · Cited by 360
“5] ), hierarchical (Clauset et al., 2008) ( [0 .”
Robust detection of dynamic community structure in networks
Bassett, D. S., Porter, M. A., Wymbs, N. F., Grafton, S. T., Carlson, J. M., & Mucha, P. J. (2013) · Chaos: An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.4790830 · Cited by 425
The science of science: From the perspective of complex systems
Zeng, A., Shen, Z., Zhou, J., Wu, J., Fan, Y., Wang, Y., & Stanley, H. E. (2017) · Physics Reports · doi:10.1016/j.physrep.2017.10.001 · Cited by 410
“Link prediction is a microscopic prediction seeking to retrieve missing links and forecast future links in a network [253].”
BackgroundHierarchical Block Structures and High-Resolution Model Selection in Large Networks
Peixoto, T. P. (2014) · Physical Review X · doi:10.1103/physrevx.4.011047 · Cited by 248
“We also predict that it should serve as a more refined method of detecting missing information in networks [23, 44], as well as for the prediction of the network evolution [87], determining the more salient topological features [88, 89], or large-scale functional summaries of the network topology…”
BackgroundMethodToward link predictability of complex networks
Lü, L., Pan, L., Zhou, T., Zhang, Y.-C., & Stanley, H. E. (2015) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1424644112 · Cited by 412
“On the other hand, a better understanding of network organization should be transferable to a good link prediction algorithm, e.g., the prior assumption of hierarchical organization of networks can be directly applied to the design of a prediction algorithm (18).”
BackgroundCannistraci, C. V., Alanis-Lobato, G., & Ravasi, T. (2013) · Scientific Reports · doi:10.1038/srep01613 · Cited by 401
“As a further investigation, we compared CAR’s indices with two sophisticated statistical inference techniques : the Hierarchical Random Graph 27 and the Stochastic Block Model 28 - see SI section IIIC for details.”
MethodEfficient and principled method for detecting communities in networks
Ball, B., Karrer, B., & Newman, M. E. J. (2011) · Physical Review E · doi:10.1103/physreve.84.036103 · Cited by 386
“This approach, which applies methods of statistical inference to networks, has been explored by a number of authors for the nonover-lapping case, including some work that goes back several decades [4–7].”
MethodSelf-citationStructure and inference in annotated networks
Newman, M. E. J., & Clauset, A. (2016) · Nature Communications · doi:10.1038/ncomms11863 · Cited by 379
Self-citationRosvall, M., & Bergstrom, C. T. (2011) · PLoS ONE · doi:10.1371/journal.pone.0018209 · Cited by 393
“w that is associated with movements into the mi ner levels of the hierarchy fqij x g. The relative rate of codeword use is Qi= q i y =q ;q i1 x =q ;:::;q imi x =q i , where qi = q i y + Xmi j=1 qij x (9) is the total codeword use. The Shannon information of movements in this submodule, weighted by how often the code i…”
BackgroundInfluentialSocial Network Analysis and Mining for Business Applications
Bonchi, F., Castillo, C., Gionis, A., & Jaimes, A. (2011) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/1961189.1961194 · Cited by 359
Signal propagation in complex networks
Ji, P., Ye, J., Mu, Y., Lin, W., Tian, Y., Hens, C., Perc, M., Tang, Y., Sun, J., & Kurths, J. (2023) · Physics Reports · doi:10.1016/j.physrep.2023.03.005 · Cited by 360
A tutorial in connectome analysis: Topological and spatial features of brain networks
Kaiser, M. (2011) · NeuroImage · doi:10.1016/j.neuroimage.2011.05.025 · Cited by 371
A classification for community discovery methods in complex networks
Coscia, M., Giannotti, F., & Pedreschi, D. (2011) · Statistical Analysis and Data Mining: The ASA Data Science Journal · doi:10.1002/sam.10133 · Cited by 353
Hyperbolic Graph Convolutional Neural Networks
Chami, I., Ying, R., Ré, C., & Leskovec, J. (2019) · arXiv · doi:10.48550/arxiv.1910.12933 · Cited by 344
“However, many real-world graphs, such as protein interaction networks and social networks, often exhibit scale-free or hierarchical structure [7, 50] and Euclidean embeddings, used by existing GCNs, have a high distortion when embedding such graphs [6, 32].”
BackgroundKovács, I. A., Palotai, R., Szalay, M. S., & Csermely, P. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012528 · Cited by 338
Comparing species interaction networks along environmental gradients
Pellissier, L., Albouy, C., Bascompte, J., Farwig, N., Graham, C., Loreau, M., Maglianesi, M. A., Melián, C. J., Pitteloud, C., Roslin, T., et al. (2018) · Biological Reviews · doi:10.1111/brv.12366 · Cited by 317
Zhuang, K., Izallalen, M., Mouser, P., Richter, H., Risso, C., Mahadevan, R., & Lovley, D. R. (2011) · The ISME Journal · doi:10.1038/ismej.2010.117 · Cited by 319
Data based identification and prediction of nonlinear and complex dynamical systems
Wang, W.-X., Lai, Y.-C., & Grebogi, C. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.06.004 · Cited by 299
Link prediction in weighted networks: The role of weak ties
Lü, L., & Zhou, T. (2010) · EPL (Europhysics Letters) · doi:10.1209/0295-5075/89/18001 · Cited by 320
Fundamental structures of dynamic social networks
Sekara, V., Stopczynski, A., & Lehmann, S. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1602803113 · Cited by 313
Dale, M. R. T., & Fortin, M.-J. (2010) · Annual Review of Ecology, Evolution, and Systematics · doi:10.1146/annurev-ecolsys-102209-144718 · Cited by 265
Assessment of network module identification across complex diseases
The DREAM Module Identification Challenge Consortium, Choobdar, S., Ahsen, M. E., Crawford, J., Tomasoni, M., Fang, T., Lamparter, D., Lin, J., Hescott, B., Hu, X., et al. (2019) · Nature Methods · doi:10.1038/s41592-019-0509-5 · Cited by 294
Evaluating link prediction methods
Yang, Y., Lichtenwalter, R. N., & Chawla, N. V. (2015) · Knowledge and Information Systems · doi:10.1007/s10115-014-0789-0 · Cited by 287
Network analyses structure genetic diversity in independent genetic worlds
Halary, S., Leigh, J. W., Cheaib, B., Lopez, P., & Bapteste, E. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0908978107 · Cited by 263
Learning Latent Block Structure in Weighted NetworksPreprint
Aicher, C., Jacobs, A. Z., & Clauset, A. J. (2016) · Cited by 271
Self-citationBrown, B. L., Swan, C. M., Auerbach, D. A., Campbell Grant, E. H., Hitt, N. P., Maloney, K. O., & Patrick, C. (2011) · Journal of the North American Benthological Society · doi:10.1899/10-129.1 · Cited by 261
“…modeling (Labonne et al. 2008, Grant 2011), graph theory (Auerbach and Poff 2011), fractal analysis (Turcotte et al. 1998), geostatistical modeling (Peterson et al. 2007), hierarchy theory (Clauset et al. 2008), and approaches that combine elements of several methods (Rodriguez-Iturbe et al. 2009).”
Multi-Attribute Partitioning of Power Networks Based on Electrical Distance
Cotilla-Sanchez, E., Hines, P. D. H., Barrows, C., Blumsack, S., & Patel, M. (2013) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2013.2263886 · Cited by 263
“Partitioning methods can also be used to reveal complex community structures in large-scale networks [10], [11].”
MethodNetwork structure from rich but noisy data
Newman, M. E. J. (2018) · Nature Physics · doi:10.1038/s41567-018-0076-1 · Cited by 225
Self-citationCardiac and Respiratory Patterns Synchronize between Persons during Choir Singing
Müller, V., & Lindenberger, U. (2011) · PLoS ONE · doi:10.1371/journal.pone.0024893 · Cited by 256
“, [19,20,21,30]) than the present system of eleven choir members and a conductor.”
BackgroundLearning latent block structure in weighted networks
Aicher, C., Jacobs, A. Z., & Clauset, A. (2015) · Journal of Complex Networks · doi:10.1093/comnet/cnu026 · Cited by 238
“Other choices of θ can generate hierarchical, multi-partite, or core-periphery patterns [9, 26].”
BackgroundResultSelf-citationWang, S., Celebi, M. E., Zhang, Y.-D., Yu, X., Lu, S., Yao, X., Zhou, Q., Miguel, M.-G., Tian, Y., Gorriz, J. M., et al. (2021) · Information Fusion · doi:10.1016/j.inffus.2021.07.001 · Cited by 241
Community structure and scale-free collections of Erdős-Rényi graphs
Seshadhri, C., Kolda, T. G., & Pinar, A. (2012) · Physical Review E · doi:10.1103/physreve.85.056109 · Cited by 241
“[32] A.”
BackgroundNetwork-Based Methods for Prediction of Drug-Target Interactions
Wu, Z., Li, W., Liu, G., & Tang, Y. (2018) · Frontiers in Pharmacology · doi:10.3389/fphar.2018.01134 · Cited by 237
“Although many recommendation algorithms and link prediction algorithms have been proposed up to date (Clauset et al., 2008; Guimera and Sales-Pardo, 2009; Lu and Zhou, 2011; Lu et al., 2012; Pan et al., 2016), few of them were applied in DTI prediction.”
MethodMultiresolution community detection for megascale networks by information-based replica correlations
Ronhovde, P., & Nussinov, Z. (2009) · Physical Review E · doi:10.1103/physreve.80.016109 · Cited by 245
Sequential algorithm for fast clique percolation
Kumpula, J. M., Kivelä, M., Kaski, K., & Saramäki, J. (2008) · Physical Review E · doi:10.1103/physreve.78.026109 · Cited by 230
The Network Completion Problem: Inferring Missing Nodes and Edges in Networks
Kim, M., & Leskovec, J. (2011) · Proceedings of the 2011 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972818.5 · Cited by 217
“The network completion has been studied in the context of survey sampling [12] and the inference of missing links mainly in social and biological networks [11, 7].”
BackgroundPersonalized recommendation via integrated diffusion on user–item–tag tripartite graphs
Zhang, Z.-K., Zhou, T., & Zhang, Y.-C. (2010) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2009.08.036 · Cited by 231
“and Yi-Cheng Zhang Data set Pure U-I Pure I-T Optimum λopt Del.icio.us 0.8098 0.8486 0.8588 0.32 MovieLens 0.8065 0.8163 0.8233 0.44 BibSonomy 0.7374 0.7600 0.7852 0.44 • The area under the ROC curve [31, 32]: In the present case, the area under the ROC curve, abbreviated by AUC, for a particular user is the probabili…”
BackgroundMethodInfluentialA machine learning approach for predicting hidden links in supply chain with graph neural networks
Kosasih, E. E., & Brintrup, A. (2022) · International Journal of Production Research · doi:10.1080/00207543.2021.1956697 · Cited by 197
Semantic linking through spaces for cyber-physical-socio intelligence: A methodology
Zhuge, H. (2011) · Artificial Intelligence · doi:10.1016/j.artint.2010.09.009 · Cited by 226
“The probabilistic method was used to predict the missing links in networks [11].”
MethodThe network of plants volatile organic compounds
Vivaldo, G., Masi, E., Taiti, C., Caldarelli, G., & Mancuso, S. (2017) · Scientific Reports · doi:10.1038/s41598-017-10975-x · Cited by 212
Physiological regulatory networks: ecological roles and evolutionary constraints
Cohen, A. A., Martin, L. B., Wingfield, J. C., McWilliams, S. R., & Dunne, J. A. (2012) · Trends in Ecology & Evolution · doi:10.1016/j.tree.2012.04.008 · Cited by 219
Schleuning, M., Ingmann, L., Strauß, R., Fritz, S. A., Dalsgaard, B., Matthias Dehling, D., Plein, M., Saavedra, F., Sandel, B., Svenning, J., et al. (2014) · Ecology Letters · doi:10.1111/ele.12245 · Cited by 221
“In principle, this algorithm follows the approach of Clauset et al. (2008).”
MethodAcademic social networks: Modeling, analysis, mining and applications
Kong, X., Shi, Y., Yu, S., Liu, J., & Xia, F. (2019) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2019.01.029 · Cited by 200
“Among them, CNM is a classical greedy-type algorithm proposed by Clauset, Newman, and Moore with the computational complexity of O ( n log 2 n ) (Clauset et al., 2008).”
Assessing the relevance of node features for network structure
Bianconi, G., Pin, P., & Marsili, M. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0811511106 · Cited by 221
Towards time-aware link prediction in evolving social networks
Tylenda, T., Angelova, R., & Bedathur, S. (2009) · Proceedings of the 3rd Workshop on Social Network Mining and Analysis · doi:10.1145/1731011.1731020 · Cited by 215
“[5] use hierarchical random graph models for link prediction.”
Method
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.