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 201–300 of 1,000
Quantifying the spatial homogeneity of urban road networks via graph neural networks
Xue, J., Jiang, N., Liang, S., Pang, Q., Yabe, T., Ukkusuri, S. V., & Ma, J. (2022) · Nature Machine Intelligence · doi:10.1038/s42256-022-00462-y · Cited by 128
Model selection for degree-corrected block models
Yan, X., Shalizi, C. R., Jensen, J. E., Krząkała, F., Moore, C., Zdeborová, L., Zhang, P., & Zhu, Y. (2014) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2014/05/p05007 · Cited by 147
Self-citationWatts, S., Dormann, C. F., González, A. M. M., & Ollerton, J. (2016) · Annals of Botany · doi:10.1093/aob/mcw114 · Cited by 113
“This algorithm follows the approach of Clauset et al. (2008) based on a hierarchical representation of interaction frequencies and optimal allocation of species into modules.”
MethodMa, X., Sun, P., & Qin, G. (2017) · Pattern Recognition · doi:10.1016/j.patcog.2017.06.025 · Cited by 119
A systemic analysis of link prediction in social network
Haghani, S., & Keyvanpour, M. R. (2017) · Artificial Intelligence Review · doi:10.1007/s10462-017-9590-2 · Cited by 121
Time-series–based prediction of complex oscillator networks via compressive sensing
Wang, W.-X., Yang, R., Lai, Y.-C., Kovanis, V. I., & Harrison, M. A. F. (2011) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/94/48006 · Cited by 120
Social network models predict movement and connectivity in ecological landscapes
Fletcher, R. J., Acevedo, M. A., Reichert, B. E., Pias, K. E., & Kitchens, W. M. (2011) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1107549108 · Cited by 120
Transitive node similarity for link prediction in social networks with positive and negative links
Symeonidis, P., Tiakas, E., & Manolopoulos, Y. (2010) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/1864708.1864744 · Cited by 118
Temporal Link Prediction: A Survey
Divakaran, A., & Mohan, A. (2019) · New Generation Computing · doi:10.1007/s00354-019-00065-z · Cited by 110
“A combination of maximum likelihood and Monte Carlo sampling algorithm [21] was introduced to infer existence likelihood of links in static networks.”
BackgroundA new link prediction in multiplex networks using topologically biased random walks
Nasiri, E., Berahmand, K., & Li, Y. (2021) · Chaos Solitons & Fractals · doi:10.1016/j.chaos.2021.111230 · Cited by 113
Link Prediction Methods and Their Accuracy for Different Social Networks and Network Metrics
Gao, F., Musiał, K., Cooper, C., & Tsoka, S. (2015) · Scientific Programming · doi:10.1155/2015/172879 · Cited by 113
“In the context of network link prediction, AUC can be interpreted as the probability that a randomly chosen missing links ( L 1 ∪ L 2 − L 1 ) is given a higher similarity score than a randomly chosen pair of unconnected links ( U − ( L 1 ∪ L 2 )) [12].”
BackgroundLink prediction via linear optimization
Pech, R., Hao, D., Lee, Y.-L., Yuan, Y., & Zhou, T. (2019) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2019.121319 · Cited by 111
“…17,18 that assign a similarity score to every pair of nodes and rank all non-observed links according to their scores, maximum likelihood methods 19,20 that presuppose some network organizing principles with detailed rules and specific parameters being obtained by maximizing the likelihood of…”
MethodA Survey of Statistical Network Models
Goldenberg, A. (2009) · now publishers, Inc. eBooks · doi:10.1561/9781601983213 · Cited by 106
Spatial Guilds in the Serengeti Food Web Revealed by a Bayesian Group Model
Baskerville, E. B., Dobson, A. P., Bedford, T., Allesina, S., Anderson, T. M., & Pascual, M. (2011) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1002321 · Cited by 113
“In network inference, there are only a few examples of complete Bayesian models [25,26] and a few examples of MCMC for maximum-likelihood inference [27,28], but Bayesian inference in phylogenetics has been long established [29,30], and provides a clear methodological analogue.”
BackgroundModel Selection and Hypothesis Testing for Large-Scale Network Models with Overlapping Groups
Peixoto, T. P. (2015) · Physical Review X · doi:10.1103/physrevx.5.011033 · Cited by 134
“This issue tends to escalate as more elaborate models and methods are developed, including features such as degree correction [19], community overlap [14, 15, 18, 20], hierarchical structure [6, 7, 21], self-similarity [22, 23], bipartiteness [5], edge and node correlates [24, 25], social tiers [26], multilayer struct…”
BackgroundInfluentialNewman, M. E. J. (2018) · Oxford University Press eBooks · doi:10.1093/oso/9780198805090.003.0006 · Cited by 112
Self-citationHME: A Hyperbolic Metric Embedding Approach for Next-POI Recommendation
Feng, S., Tran, L. V., Cong, G., Chen, L., Li, J., & Li, F. (2020) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/3397271.3401049 · Cited by 131
“It has been studied that power-law distributions often indicate implicit hierarchical structures [1, 31, 34], which can explain many topological properties of graphs [8].”
BackgroundThe art of community detection
Gulbahce, N., & Lehmann, S. (2008) · BioEssays · doi:10.1002/bies.20820 · Cited by 114
“Recently, Clauset, Moore, and Newman,((1)) introduced a new algorithm that identifies such heterogeneities in complex networks by utilizing the hierarchy that necessarily organizes the many levels of structure.”
Wuchty, S., & Uzzi, B. (2011) · PLoS ONE · doi:10.1371/journal.pone.0026972 · Cited by 107
“help advance research across disciplines [1,2,3,4,5,6,7,8,10,11, 12,13].”
BackgroundLink prediction in citation networks
Shibata, N., Kajikawa, Y., & Sakata, I. (2011) · Journal of the American Society for Information Science and Technology · doi:10.1002/asi.21664 · Cited by 104
Bayesian analysis for partially observed network data, missing ties, attributes and actors
Koskinen, J. H., Robins, G. L., Wang, P., & Pattison, P. E. (2013) · Social Networks · doi:10.1016/j.socnet.2013.07.003 · Cited by 117
Measuring the robustness of network community structure using assortativity
Shizuka, D., & Farine, D. R. (2016) · Animal Behaviour · doi:10.1016/j.anbehav.2015.12.007 · Cited by 108
Estimating network structure from unreliable measurements
Newman, M. E. J. (2018) · Physical review. E · doi:10.1103/physreve.98.062321 · Cited by 124
Self-citationAnticipating technological convergence: Link prediction using Wikipedia hyperlinks
Kim, J., Kim, S., & Lee, C. (2018) · Technovation · doi:10.1016/j.technovation.2018.06.008 · Cited by 98
Finding Overlapping Communities Using Disjoint Community Detection Algorithms
Gregory, S. (2009) · Studies in computational intelligence · doi:10.1007/978-3-642-01206-8_5 · Cited by 108
“Yet other algorithms [3, 5, 17] aim to detect a hierarchy of communities: for example, a number of research c ommunities each divided into several research groups.”
BackgroundInfluence Estimation and Maximization in Continuous-Time Diffusion Networks
Gomez-Rodriguez, M., Song, L., Du, N., Zha, H., & Schölkopf, B. (2016) · ACM Transactions on Information Systems · doi:10.1145/2824253 · Cited by 109
“We consider three types of Kronecker networks with very different structure: random [Erd˝os and R´enyi 1960] (parameter matrix [0.5, 0.5; 0.5, 0.5]), hierarchial [Clauset et al. 2008] ([0.9, 0.1; 0.1; 0.9]) and core-periphery [Leskovec et al. 2008] ([0.9, 0.5; 0.5, 0.3]).”
MethodInfluentialThe use of network analyses for elucidating mechanisms in cardiovascular disease
Díez, D., Wheelock, Å. M., Goto, S., Haeggström, J. Z., Paulsson‐Berne, G., Hansson, G. K., Hedin, U., Gabrielsen, A., & Wheelock, C. E. (2009) · Molecular BioSystems · doi:10.1039/b912078e · Cited by 102
Improved Bayesian inference for the stochastic block model with application to large networks
McDaid, A. F., Murphy, T. B., Friel, N., & Hurley, N. (2012) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2012.10.021 · Cited by 124
Continuous Hierarchical Representations with Poincaré Variational Auto-EncodersPreprint
Mathieu, É., Lan, C. L., Maddison, C. J., Tomioka, R., & Teh, Y. W. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.06033 · Cited by 131
“Edges in complex networks can typically be explained by a latent hierarchy over the nodes (Clauset et al., 2008).”
BackgroundSoft Autonomous Materials—Using Active Elasticity and Embedded Distributed Computation
Correll, N., Önal, Ç. D., Liang, H., Schoenfeld, E., & Rus, D. (2014) · Springer Tracts in Advanced Robotics · doi:10.1007/978-3-642-28572-1_16 · Cited by 91
“Advances in decentralized algorithms for self-organizing machines [1, 15], understanding of self-organizing biological systems [5] and large networks [7], enable the embedded scalable computation required by autonomous materials.”
BackgroundBerahmand, K., Nasiri, E., Forouzandeh, S., & Li, Y. (2021) · Journal of King Saud University - Computer and Information Sciences · doi:10.1016/j.jksuci.2021.05.006 · Cited by 104
Network Structure, Metadata, and the Prediction of Missing Nodes and Annotations
Hric, D., Peixoto, T. P., & Fortunato, S. (2016) · Physical Review X · doi:10.1103/physrevx.6.031038 · Cited by 115
Mentzen, W. I., Peng, J., Ransom, N., Nikolau, B. J., & Wurtele, E. S. (2008) · BMC Plant Biology · doi:10.1186/1471-2229-8-76 · Cited by 106
“Hierarchical modular organization has been postulated as the topology explaining the observed features of biological networks, like scale-free character, high clustering coefficient and short path lengths [74,75].”
BackgroundSpectral tripartitioning of networks
Richardson, T., Mucha, P. J., & Porter, M. A. (2009) · Physical Review E · doi:10.1103/physreve.80.036111 · Cited by 90
FriendSensing: recommending friends using mobile phones
Quercia, D., & Capra, L. (2009) · Proceedings of the third ACM conference on Recommender systems · doi:10.1145/1639714.1639766 · Cited by 88
“The shortest path is the simplest algorithm among the four and yet it has been shown to work best on a number of social networks [4, 24].”
BackgroundNetwork analysis for gene discovery in plant‐specialized metabolism
Higashi, Y., & Saito, K. (2013) · Plant Cell & Environment · doi:10.1111/pce.12069 · Cited by 94
Link Prediction on Complex Networks: An Experimental Survey
Wu, H., Song, C., Ge, Y., & Ge, T. (2022) · Data Science and Engineering · doi:10.1007/s41019-022-00188-2 · Cited by 103
“Hierarchical structure model (HSM) [47] is suitable for networks which exhibit hierarchical organizations such as metabolic networks.”
BackgroundTourism destinations: A universality conjecture based on network science
Baggio, R. (2020) · Annals of Tourism Research · doi:10.1016/j.annals.2020.102929 · Cited by 95
A Hyperbolic-to-Hyperbolic Graph Convolutional Network
Dai, J., Wu, Y., Gao, Z. F., & Jia, Y. (2021) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr46437.2021.00022 · Cited by 132
Origin of the scaling law in human mobility: Hierarchy of traffic systems
Han, X.-P., Hao, Q., Wang, B.-H., & Zhou, T. (2011) · Physical Review E · doi:10.1103/physreve.83.036117 · Cited by 88
Nonparametric Bayesian modeling of complex networks: an introduction
Schmidt, M. N., & Mørup, M. (2013) · IEEE Signal Processing Magazine · doi:10.1109/msp.2012.2235191 · Cited by 106
Bursting the Filter Bubble: Fairness-Aware Network Link Prediction
Masrour, F., Wilson, T., Yan, H., Tan, P., & Esfahanian, A. H. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i01.5429 · Cited by 128
“Another class of link prediction methods employ machine learning methods, such as those based on probabilistic graphical models (Clauset, Moore, and Newman 2008), matrix factorization (Scripps et al. 2008), and supervised classification (Al Hasan et al. 2006; Wang et al. ).”
MethodTowards an eco‐phylogenetic framework for infectious disease ecology
Fountain‐Jones, N. M., Pearse, W. D., Escobar, L. E., Alba, A., Carver, S., Davies, T. J., Kraberger, S. J., Papeş, M., Vandegrift, K. J., Worsley‐Tonks, K. E. L., et al. (2017) · Biological reviews/Biological reviews of the Cambridge Philosophical Society · doi:10.1111/brv.12380 · Cited by 91
Using null models to infer microbial co-occurrence networks
Connor, N., Barberán, A., & Clauset, A. J. (2017) · PLoS ONE · doi:10.1371/journal.pone.0176751 · Cited by 93
“A generative link-prediction model allows us to test the degree to which our assumptions about the underlying structure of the system are correct (Clauset et al. 2008, Guimerá & Sales-Pardo 2009).”
BackgroundSelf-citationThe Geometry of Continuous Latent Space Models for Network Data
Smith, A. L., Asta, D. M., & Calder, C. A. (2019) · Statistical Science · doi:10.1214/19-sts702 · Cited by 110
Local dominance unveils clusters in networks
Shi, D., Shang, F., Chen, B., Expert, P., Lü, L., Stanley, E., Lambiotte, R., Evans, T., & Li, R. (2024) · Communications Physics · doi:10.1038/s42005-024-01635-4 · Cited by 96
“Such cluster or community structure provides a coarse-grained representation of the underlying complex system 8 – 11 , often associated to different functions and impacting its collective behaviors 12 – 14 , and their unsupervised detection is thus essential in different areas of data science 1,10 .”
InfluentialNetwork-level analysis of cortical thickness of the epileptic brain
Raj, A., Mueller, S. G., Young, K., Laxer, K. D., & Weiner, M. (2010) · NeuroImage · doi:10.1016/j.neuroimage.2010.05.045 · Cited by 83
“…study biochemical and metabolic interactions, epidemiological relationships or protein interaction, and gene expression interactions (Guimerà et al., 2007; Price and Shmulevich, 2007; Steuer, 2007; Martínez-Beneito et al., 2008; Clauset et al., 2008; Charbonnier et al., 2008; Liang andWang, 2008).”
Multifractal network generator
Palla, G., Lovász, L., & Vicsek, T. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0912983107 · Cited by 93
Hierarchical Community Detection by Recursive Partitioning
Li, T., Lei, L., Bhattacharyya, S., den Berge, K. V., Sarkar, P., Bickel, P. J., & Levina, E. (2020) · Journal of the American Statistical Association · doi:10.1080/01621459.2020.1833888 · Cited by 112
“One line of work treats the tree as a parameter and takes a Bayesian approach (e.g., Clauset, Moore, and Newman 2008; Blundell and Teh 2013).”
BackgroundMethodInfluentialNetwork modeling of signal transduction: establishing the global view
Kestler, H. A., Wawra, C., Kracher, B., & Kühl, M. (2008) · BioEssays · doi:10.1002/bies.20834 · Cited by 86
“mentioned topological properties of small-world networks can be explained and even reproduced in silico by assuming the existence of a network hierarchy and the knowledge of this hierarchical structure can even help to predict missing connections in the network.( 61 )”
BackgroundDetecting evolving patterns of self‐organizing networks by flow hierarchy measurement
Luo, J., & Magee, C. L. (2011) · Complexity · doi:10.1002/cplx.20368 · Cited by 92
Estimating potential trade links in the international crude oil trade: A link prediction approach
Guan, Q., An, H., Gao, X., Huang, S., & Li, H. (2016) · Energy · doi:10.1016/j.energy.2016.02.099 · Cited by 84
Identification of subpopulations from connectivity matrices
Jacobi, M. N., André, C., Döös, K., & Jonsson, P. R. (2012) · Ecography · doi:10.1111/j.1600-0587.2012.07281.x · Cited by 89
Link prediction approach combined graph neural network with capsule network
Liu, X., Li, X., Fiumara, G., & Meo, P. D. (2022) · Expert Systems with Applications · doi:10.1016/j.eswa.2022.118737 · Cited by 82
Technology opportunity analysis using hierarchical semantic networks and dual link prediction
Liu, Z., Jian, F., & Uden, L. (2023) · Technovation · doi:10.1016/j.technovation.2023.102872 · Cited by 82
Pharmacointeraction Network Models Predict Unknown Drug-Drug Interactions
Cami, A., Manzi, S. F., Arnold, A. D., & Reis, B. Y. (2013) · PLoS ONE · doi:10.1371/journal.pone.0061468 · Cited by 87
“Such a ‘‘link-prediction’’ approach has been used in other applications, such as social, metabolic or food networks [23,24].”
MethodRevealing Density-Based Clustering Structure from the Core-Connected Tree of a Network
Huang, J., Sun, H., Song, Q., Deng, H., & Han, J. (2013) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2012.100 · Cited by 88
Estrada‐Peña, A., de la Fuente, J., Ostfeld, R. S., & Cabezas‐Cruz, A. (2015) · Scientific Reports · doi:10.1038/srep10361 · Cited by 84
Link prediction in multiplex networks based on interlayer similarity
Najari, S., Salehi, M., Ranjbar, V., & Jalili, M. (2019) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2019.04.214 · Cited by 88
“Examples include local relation models [36], hierarchical probabilistic models [37], and probabilistic relation models such as Bayesian relations [38] or Markova relation network [39].”
MethodPain-Evoked Reorganization in Functional Brain Networks
Zheng, W., Woo, C., Yao, Z., Goldstein, P., Atlas, L. Y., Roy, M., Schmidt, L., Krishnan, A., Jepma, M., Hu, B., et al. (2019) · Cerebral Cortex · doi:10.1093/cercor/bhz276 · Cited by 83
“These findings extend earlier work showing correlations between brain activity and perceived pain (Coghill et al. 1999; Koyama et al. 2005; Baliki et al. 2009; Wager et al. 2013; Atlas et al. 2014).”
BackgroundLink Prediction: Fair and Effective Evaluation
Lichtnwalter, R., & Chawla, N. V. (2012) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1109/asonam.2012.68 · Cited by 100
“Thus, even in domains where link prediction can seem impossibly difficult or offer a high ratio of false positives to true positives, it may be useful [4].”
BackgroundHierarchies in the Structure of Personality Traits
Markon, K. E. (2009) · Social and Personality Psychology Compass · doi:10.1111/j.1751-9004.2009.00213.x · Cited by 87
Mapping the Evolution of Scientific Fields
Herrera, M., Roberts, D. C. K., & Gulbahce, N. (2010) · PLoS ONE · doi:10.1371/journal.pone.0010355 · Cited by 91
“There have been a number of methods to find the communities in networks which describe the inherent structure or functional units of a network [20–23].”
MethodBibliometric Analysis of Social Robotics Research: Identifying Research Trends and Knowledgebase
Mejía, C., & Kajikawa, Y. (2017) · Applied Sciences · doi:10.3390/app7121316 · Cited by 89
Link Prediction in Complex Networks: A Clustering PerspectivePreprint
Feng, X., Zhao, J., & Xua, K. (2016) · Cited by 81
Reconstructing a credit network
Caldarelli, G., Chessa, A., Pammolli, F., Gabrielli, A., & Puliga, M. (2013) · Nature Physics · doi:10.1038/nphys2580 · Cited by 88
Structural link prediction based on ant colony approach in social networks
Sherkat, E., Rahgozar, M., & Asadpour, M. (2014) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2014.10.011 · Cited by 83
“[12], a likelihood approach for inferring hierarchical structure from network data called Dendrogram introduced and showed that the existence of hierarchy can explain how commonly observed topological properties of networkswould be reproduced.”
BackgroundHipólito, I., Ramstead, M. J. D., Convertino, L., Bhat, A., Friston, K., & Parr, T. (2021) · Neuroscience & Biobehavioral Reviews · doi:10.1016/j.neubiorev.2021.02.003 · Cited by 79
“, a fractal hierarchy of neuronal systems and the global integration of functionally segregated units (Sporns, 2006; Clauset et al., 2008).”
BackgroundCoupledLP: Link Prediction in Coupled Networks
Dong, Y., Zhang, J., Tang, J., Chawla, N. V., & Wang, B. (2015) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2783258.2783329 · Cited by 91
“, computer science [27, 38, 4], network science [7, 42], and biology [30, 5, 36, 8, 14].”
BackgroundCover time for random walks on arbitrary complex networks
Maier, B. F., & Brockmann, D. (2017) · Physical review. E · doi:10.1103/physreve.96.042307 · Cited by 79
“Coli interaction network and the grassland species food web is most likely related to the fact that those networks are strongly hierarchically clustered [35, 36] and hence similar to low-dimensional spatial networks with short-range interaction probability concerning random walks and search processes [37].”
BackgroundReconstructing commuters network using machine learning and urban indicators
Spadon, G., de Carvalho, A. C. P. L. F., Rodrigues-Jr, J. F., & Alves, L. G. A. (2019) · Scientific Reports · doi:10.1038/s41598-019-48295-x · Cited by 86
Finding missing edges in networks based on their community structure
Yan, B., & Gregory, S. (2012) · Physical Review E · doi:10.1103/physreve.85.056112 · Cited by 81
A linguistic rule-based approach to extract drug-drug interactions from pharmacological documents
Segura-Bédmar, I., Martı́nez, P., & de Pablo-Sánchez, C. (2011) · BMC Bioinformatics · doi:10.1186/1471-2105-12-s2-s1 · Cited by 79
Stochastic block models: A comparison of variants and inference methods
Funke, T., & Becker, T. (2019) · PLoS ONE · doi:10.1371/journal.pone.0215296 · Cited by 100
Identifying Community Structures from Network Data via Maximum Likelihood Methods
Čopič, J., Jackson, M. O., & Kirman, A. P. (2009) · The B E Journal of Theoretical Economics · doi:10.2202/1935-1704.1523 · Cited by 88
“`s;g(�) = (k1 k3)T In(�)(g) + (k2 k4)T In(�)(s) + k3T(g) + k4T(s): ( 3 )”
Fast hierarchy construction for dense subgraphs
Sarıyüce, A. E., & Pınar, A. (2016) · Proceedings of the VLDB Endowment · doi:10.14778/3021924.3021927 · Cited by 77
“Hierarchy has been shown to be a central organizing principle of complex networks, which is useful to relate communities of a graph and can offer insight into many network phenomena [9].”
BackgroundLink prediction for tree-like networks
Shang, K.-K., Li, T.-C., SMALL, M. P., Burton, D., & Yan, W. (2019) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.5107440 · Cited by 84
Feng, S., An, H., Li, H., Qi, Y., Wang, Z., Guan, Q., Li, Y., & Qi, Y. (2020) · Journal of Cleaner Production · doi:10.1016/j.jclepro.2020.120992 · Cited by 77
Wang, Y., Liu, R., Lin, D., Chen, D., Li, P., Hu, Q., & Chen, C. L. P. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3100928 · Cited by 76
“The study in [15] has suggested complex systems often exhibit a hierarchical organization.”
BackgroundBootstrapping Topological Properties and Systemic Risk of Complex Networks Using the Fitness Model
Musmeci, N., Battiston, S., Caldarelli, G., Puliga, M., & Gabrielli, A. (2013) · Journal of Statistical Physics · doi:10.1007/s10955-013-0720-1 · Cited by 91
“The reconstruction of statistical properties of a network when only partial information is available is one of the outstanding and unresolved problems in the field of statistical physics of networks [4, 13].”
BackgroundMethodCombining food web and species distribution models for improved community projections
Pellissier, L., Rohr, R. P., Ndiribe, C. C., Pradervand, J., Salamin, N., Guisan, A., & Wisz, M. S. (2013) · Ecology and Evolution · doi:10.1002/ece3.843 · Cited by 81
“The food web model can be interpolated by fitting and predicting linkages between species to the original dataset (here referred as “interpolation”) or extrapolated by projecting the model on to an independent dataset to infer potential links between poorly known species, or species in a different or hypothetical comm…”
BackgroundMethodRemoving spurious interactions in complex networks
Zeng, A., & Cimini, G. (2012) · Physical Review E · doi:10.1103/physreve.85.036101 · Cited by 79
An exploration of climate data using complex networks
Steinhaeuser, K., Chawla, N. V., & Ganguly, A. R. (2010) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1882471.1882476 · Cited by 74
“A variety of algorithms with different characteristics have been proposed and applied in a number of settings including social networks [15], protein interaction networks [1], and food webs [ 2 ].”
BackgroundInformation filtering based on transferring similarity
Duo, S., Zhou, T., Liu, J.-G., Liu, R.-R., Jia, C.-X., & Wang, B.-H. (2009) · Physical Review E · doi:10.1103/physreve.80.017101 · Cited by 76
Efficient Routing on Large Road Networks Using Hierarchical Communities
Song, Q., & Wang, X. (2010) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2010.2072503 · Cited by 79
“The Associate Editor for this paper was M. Á. Sotelo Vázquez.”
BackgroundDescriptive vs. Inferential Community Detection in Networks: Pitfalls, Myths and Half-Truths
Peixoto, T. P. (2023) · Cambridge University Press eBooks · doi:10.1017/9781009118897 · Cited by 107
“This information can be used not only to propagate the uncertainties to the community assignments [26] but also to reconstruct the missing or noisy measurements of the network itself [37, 54].”
BackgroundLink prediction in complex networks: a clustering perspective
Feng, X., Zhao, J. C., & Xu, K. (2012) · The European Physical Journal B · doi:10.1140/epjb/e2011-20207-x · Cited by 72
An information-theoretic model for link prediction in complex networks
Zhu, B., & Xia, Y. (2015) · Scientific Reports · doi:10.1038/srep13707 · Cited by 75
“For the hierarchical structure of networks, Clauset et al. proposed a Hierarchical Structure Model that estimates the connection likelihood by using a dendrogram 8 .”
MethodConsistencies and inconsistencies between model selection and link prediction in networks
Vallès-Català, T., Peixoto, T. P., Sales‐Pardo, M., & Guimerà, R. (2018) · Physical review. E · doi:10.1103/physreve.97.062316 · Cited by 84
“This is in contrast to similar frameworks that have been derived with much more specific models in mind [1, 2].”
BackgroundResultInfluentialBayesian inference of network structure from unreliable data
Young, J.-G., Cantwell, G. T., & Newman, M. E. J. (2020) · Journal of Complex Networks · doi:10.1093/comnet/cnaa046 · Cited by 91
Self-citationTransforming Graph Data for Statistical Relational Learning
Rossi, R. A., McDowell, L. K., Aha, D. W., & Neville, J. (2012) · Journal of Artificial Intelligence Research · doi:10.1613/jair.3659 · Cited by 82
“In another related investigation, Clauset, Moore, and Newman (2008) evaluate a hierarchical random graph predictor against local topology metrics such as common neighbors, Jaccard’s coefficient and the degree product on three types of networks: a metabolic, ecology and a social network.”
BackgroundCommunities and bottlenecks: Trees and treelike networks have high modularity
Bagrow, J. P. (2012) · Physical Review E · doi:10.1103/physreve.85.066118 · Cited by 79
Duality of interaction outcomes in a plant–frugivore multilayer network
Genrich, C. M., Mello, M. A. R., Silveira, F. A. O., Bronstein, J. L., & Paglia, A. P. (2016) · Oikos · doi:10.1111/oik.03825 · Cited by 77
Almansoori, W., Gao, S., Jarada, T. N., Elsheikh, A. M. A., Murshed, A. N., Jida, J., Alhajj, R., & Rokne, J. G. (2012) · Network Modeling Analysis in Health Informatics and Bioinformatics · doi:10.1007/s13721-012-0005-7 · Cited by 77
Predictors of short-term decay of cell phone contacts in a large scale communication network
Raeder, T., Ližardo, O., Hachen, D. S., & Chawla, N. V. (2011) · Social Networks · doi:10.1016/j.socnet.2011.07.002 · Cited by 81
Adapting the Stochastic Block Model to Edge-Weighted NetworksPreprint
Aicher, C., Jacobs, A. Z., & Clauset, A. J. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.5782 · Cited by 82
“…have been made to allow degree heterogeneity within blocks (Karrer & Newman, 2011), probabilistic or mixed block membership (Airoldi et al., 2008; Ball et al., 2011), infinite number of blocks (Kemp et al., 2006), or hierarchical (nested) relationships among blocks (Clauset et al., 2008).”
BackgroundSelf-citationA Unifying Framework for Strong Structural Controllability
Jia, J., van Waarde, H. J., Trentelman, H. L., & Camlibel, M. K. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2981425 · Cited by 69
“This issue of missing knowledge appears, for example, in social networks [13], the world wide web [14], biological networks [15], [16], and ecological systems [17].”
BackgroundExperimental analyses on 2-hop-based and 3-hop-based link prediction algorithms
Zhou, T., Lee, Y.-L., & Wang, G. (2020) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2020.125532 · Cited by 75
Structural link analysis and prediction in microblogs
Yin, D., Hong, L., & Davison, B. D. (2011) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2063576.2063743 · Cited by 68
Predicting and recommending collaborations: An author-, institution-, and country-level analysis
Yan, E., & Guns, R. (2014) · Journal of Informetrics · doi:10.1016/j.joi.2014.01.008 · Cited by 73
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.