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 301–400 of 1,000
Choosing to Grow a Graph: Modeling Network Formation as Discrete Choice
Overgoor, J., Benson, A. R., & Ugander, J. H. (2019) · International World Wide Web Conference (WWW) · doi:10.1145/3308558.3313662 · Cited by 80
“ns by incorporating this structure. Additional related work. There is a strong connection between our work and work on link prediction and missing data methods using network features to predict edges [15, 44]. A network formation model implicitly makes claims about what edges are most likely to form next, and thus can…”
BackgroundSurvey on Big Data System and Analytic Technology
Cheng, X., Jin, X., Wang, Y., Guo, J., Zhang, T., & Li, G. (2014) · Cited by 85
Mejía, C., D’Ippolito, B., & Kajikawa, Y. (2021) · Creativity and Innovation Management · doi:10.1111/caim.12453 · Cited by 77
A Structural Evolution-Based Anomaly Detection Method for Generalized Evolving Social Networks
Wang, H., Gao, Q. Z., Li, H., Wang, H., Yan, L., & Liu, G. (2020) · The Computer Journal · doi:10.1093/comjnl/bxaa168 · Cited by 66
The Nature of Complex Networks
Dorogovtsev, S. N., & Mendes, J. F. F. (2022) · doi:10.1093/oso/9780199695119.001.0001 · Cited by 85
Structural inference for uncertain networks
Martin, T., Ball, B., & Newman, M. E. J. (2016) · Physical review. E · doi:10.1103/physreve.93.012306 · Cited by 77
“Kro- gan et al. used a value of 0.273 for their threshold, but there is little doubt that their results would be different if they had chosen a different value and little known about how to choose the value correctly.”
BackgroundInfluentialSelf-citationLi, Z. (., Fang, X., & Sheng, O. R. L. (2018) · ACM Transactions on Management Information Systems · doi:10.1145/3131782 · Cited by 65
“In general, probabilistic model-based methods (Kashima and Abe 2006, Clauset et al. 2008, Lu et al. 2010, Backstrom and Leskovec 2011, Hopcroft et al. 2011, Yang et al. 2011, Kim and Leskovec 2011, Barbieri et al. 2014, Dong et al. 2015, Song et al. 2015) predict the linkage likelihood 𝐿 𝑖𝑗…”
MethodA One Health framework for exploring zoonotic interactions demonstrated through a case study
Desvars-Larrive, A., Vogl, A. E., Puspitarani, G. A., Yang, L., Joachim, A., & Käsbohrer, A. (2024) · Nature Communications · doi:10.1038/s41467-024-49967-7 · Cited by 85
Is stochastic thermodynamics the key to understanding the energy costs of computation?
Wolpert, D. H., Korbel, J., Lynn, C. W., Tasnim, F., Grochow, J. A., Kardeş, G., Aimone, J. B., Balasubramanian, V., DeGiuli, E., Doty, D. S., et al. (2024) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2321112121 · Cited by 94
Correlations between Community Structure and Link Formation in Complex Networks
Liu, Z., He, J.-L., Kapoor, K., & Srivastava, J. (2013) · PLoS ONE · doi:10.1371/journal.pone.0072908 · Cited by 75
“Based on a similar principle of statistics as used by HRG model but from another angle of view, Roger Guimerà et al. proposed a Stochastic Block Model (SBM) which can predict both missing links and spurious links and is able to give much better accuracies of prediction on various kinds of networks than current popula…”
MethodInfluentialRedner, S. (2008) · Nature · doi:10.1038/453047a · Cited by 65
Role of weak ties in link prediction of complex networks
Lü, L., & Zhou, T. (2009) · doi:10.1145/1651274.1651285 · Cited by 65
Average Distance, Diameter, and Clustering in Social Networks with Homophily
Jackson, M. O. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-92185-1_3 · Cited by 82
Complex systems and network science: a survey
Yang, K., Li, J., Liu, M., Lei, T., Xu, X., Wu, H., Cao, J., & Qi, G. (2023) · Journal of Systems Engineering and Electronics · doi:10.23919/jsee.2023.000080 · Cited by 74
Similarity-based link prediction in social networks using latent relationships between the users
Zareie, A., & Sakellariou, R. (2020) · Scientific Reports · doi:10.1038/s41598-020-76799-4 · Cited by 69
Back to the Past: Source Identification in Diffusion Networks from Partially Observed CascadesPreprint
Farajtabar, M., Gomez-Rodriguez, M., Du, N., Zamani, M., Hongyuan Zha, B., & Song, L. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1501.06582 · Cited by 64
“…which mimic the information diffusion traces in real world networks [Gomez-Rodriguez et al., 2010], ( ii ) random networks ([0.5 0.5; 0.5 0.5]), typically used in physics and graph theory [Easley and Kleinberg, 2010], and ( iii ) hierarchical networks ([0.9 0.1; 0.1 0.9]) [Clauset et al., 2008].”
MethodInfluentialConsistency of community structure in complex networks
Riolo, M. A., & Newman, M. E. J. (2020) · Physical review. E · doi:10.1103/physreve.101.052306 · Cited by 69
“However, as pointed out by a number of authors [10– 12], simply reporting the single best division of a network, as defined by an objective function, misses much of the insight that is to be gained from community analysis.”
BackgroundSelf-citationZhou, L., Lü, K., Yang, P., Wang, L., & Kong, B. (2015) · Expert Systems with Applications · doi:10.1016/j.eswa.2015.07.023 · Cited by 63
“Clauset et al. (2008) used a dendrogram and a set of probabilities associated to the internal vertices of the dendrogram to describe the hierarchical organization of a graph.”
MethodExploring the structural regularities in networks
Shen, H., Cheng, X., & Guo, J. (2011) · Physical Review E · doi:10.1103/physreve.84.056111 · Cited by 66
Link prediction by deep non-negative matrix factorization
Chen, G., Wang, H., Fang, Y., & Jiang, L. (2021) · Expert Systems with Applications · doi:10.1016/j.eswa.2021.115991 · Cited by 64
Mining Missing Hyperlinks from Human Navigation Traces
West, R., Paranjape, A., & Leskovec, J. (2015) · International World Wide Web Conference (WWW) · doi:10.1145/2736277.2741666 · Cited by 62
“More recently approaches based on network community detection [8, 15, 16] and random walks [4] were considered for predicting missing links.”
BackgroundYang, L., Peng, L., Zhang, L.-M., Zhang, L.-L., & Yang, S. (2009) · Computers and Electronics in Agriculture · doi:10.1016/j.compag.2009.06.003 · Cited by 62
Transitive node similarity: predicting and recommending links in signed social networks
Symeonidis, P., & Tiakas, E. (2013) · World Wide Web · doi:10.1007/s11280-013-0228-2 · Cited by 66
Prediction of missing links based on community relevance and ruler inference
Ding, J., Jiao, L., Wu, J., & Liu, F. (2016) · Knowledge-Based Systems · doi:10.1016/j.knosys.2016.01.034 · Cited by 63
Protein Interaction Networks—More Than Mere Modules
Pinkert, S., Schultz, J., & Reichardt, J. (2010) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000659 · Cited by 72
Disconnected, fragmented, or united? a trans-disciplinary review of network science
Hidalgo, C. A. (2016) · Applied Network Science · doi:10.1007/s41109-016-0010-3 · Cited by 75
“…and Albert 1999), (Albert and Barabási 2002), (Krapivsky and Redner 2001), its hierarchical structure (Trusina et al. 2004), (Ravasz et al. 2002), (Clauset et al. 2008), community structure (Palla et al. 2005), (Ahn et al. 2010), (Girvan and Newman 2002), (Blondel et al. 2008), (Fortunato 2010),…”
BackgroundXun, W., Huang, T., Li, W., Ren, Y., Xiong, W., Ran, W., Li, D., Shen, Q., & Zhang, R. (2017) · Applied Soil Ecology · doi:10.1016/j.apsoil.2017.08.013 · Cited by 67
Ma, C., Chen, H., Lai, Y., & Zhang, H.-F. (2018) · Physical review. E · doi:10.1103/physreve.97.022301 · Cited by 68
Chen, G., Xu, C. G., Wang, J., Feng, J., & Feng, J. (2020) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.113290 · Cited by 62
Tracking the dynamics of co-word networks for emerging topic identification
Huang, L., Chen, X., Ni, X., Liu, J., Cao, X., & Wang, C. (2021) · Technological Forecasting and Social Change · doi:10.1016/j.techfore.2021.120944 · Cited by 64
Modeling multi-scale data via a network of networks
Gu, S., Jiang, M., Guzzi, P. H., & Milenković, T. (2022) · Bioinformatics · doi:10.1093/bioinformatics/btac133 · Cited by 64
“These include: multiplex, multimodal, multilevel, and interdependent networks [25, 16, 7, 14, 9, 23], which are sometimes used interchangeably and sometimes also referred to as “networks of networks”; hierarchical networks [8]; higher-order networks [31]; hypergraphs [4]; and simplicial complexes [17].”
BackgroundA Broader Picture of Random-walk Based Graph Embedding
Huang, Z., Silva, A., & Singh, A. (2021) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3447548.3467300 · Cited by 73
“Multiscale graph embedding based on random-walks has attracted limited interest in the literature [11, 63], though many real-life networks are known to have a multiscale (or hierarchical) structure [13, 49].”
BackgroundDynamic Infinite Relational Model for Time-varying Relational Data Analysis
Ishiguro, K., Iwata, T., Ueda, N., & Tenenbaum, J. B. (2010) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 59
Modeling Adoption and Usage of Competing Products
Valera, I., & Gomez-Rodriguez, M. (2015) · Proceedings · doi:10.1109/icdm.2015.40 · Cited by 69
“3]), (ii) hierarchical networks [47] ([0.”
Predicting missing links in complex networks based on common neighbors and distance
Yang, J.-X., & Zhang, X. (2016) · Scientific Reports · doi:10.1038/srep38208 · Cited by 68
A link prediction approach to cancer drug sensitivity prediction
Turki, T., & Wei, Z. (2017) · BMC Systems Biology · doi:10.1186/s12918-017-0463-8 · Cited by 66
“In this paper, we model the cancer drug sensitivity as a link prediction problem, which is a classical research topic in computational social science [16 – 19] and bio-medicine [20, 21].”
MethodEstimating Missing Unit Process Data in Life Cycle Assessment Using a Similarity-Based Approach
Hou, P., Cai, J., Qu, S., & Xu, M. (2018) · Environmental Science & Technology · doi:10.1021/acs.est.7b05366 · Cited by 66
Stability of similarity measurements for bipartite networks
Liu, J.-G., Hou, L., Pan, X., Guo, Q., & Zhou, T. (2016) · Scientific Reports · doi:10.1038/srep18653 · Cited by 59
Principles and open questions in functional brain network reconstruction
Korhonen, O., Zanin, M., & Papo, D. (2021) · Human Brain Mapping · doi:10.1002/hbm.25462 · Cited by 68
Coevolution of epidemic and infodemic on higher-order networks
Li, W., Cai, M., Zhong, X., Liu, Y., Lin, T., & Wang, W. (2023) · Chaos Solitons & Fractals · doi:10.1016/j.chaos.2023.113102 · Cited by 59
Hierarchical clustering in minimum spanning trees
Yu, M., Hillebrand, A., Tewarie, P. K. B., Meier, J. M., van Dijk, B. W., Mieghem, P. V., & Stam, C. J. (2015) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.4908014 · Cited by 70
Drug-therapy networks and the prediction of novel drug targets
Spiro, Z., Kovacs, I. A., & Csermely, P. (2008) · Journal of Biology · doi:10.1186/jbiol81 · Cited by 56
“Where the data-set is not as straightforwardly hierarchical as the ATC-classification [14], network hierarchy can be explored by various other techniques [18-20].”
BackgroundMethodInfluentialCommunity detection in social networks using user frequent pattern mining
Moosavi, S. A., Jalali, M., Misaghian, N., Shamshirband, S., & Anisi, M. H. (2016) · Knowledge and Information Systems · doi:10.1007/s10115-016-0970-8 · Cited by 64
“With the purpose of solving this challenge, researchers have suggested other methods based on the Bayesian probability model [8,14,23]; this model allows overlap of community members, but this method frequently focuses on the structure of network graphs.”
MethodPredicting protein–protein interactions in the context of protein evolution
Lewis, A. C. F., Saeed, R., & Deane, C. M. (2009) · Molecular BioSystems · doi:10.1039/b916371a · Cited by 63
Bayesian model selection of stochastic block models
Yan, X. (2016) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1109/asonam.2016.7752253 · Cited by 67
“There are also other variants capable of modeling overlapping, hierarchical and even “meta-data” dependent communities [9], [10], [11].”
BackgroundLink prediction based on hyperbolic mapping with community structure for complex networks
Wang, Z., Wu, Y., Li, Q., Jin, F., & Xiong, W. (2016) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2016.01.010 · Cited by 57
Link prediction for interdisciplinary collaboration via co-authorship network
Cho, H., & Yu, Y. (2018) · Social Network Analysis and Mining · doi:10.1007/s13278-018-0501-6 · Cited by 60
“…al. 1999; Jeh and Widom 2002; Liu and Lü 2010); some predict links based on probabilistic models (e.g. Geyer 1992); some estimate the network structure via maximum likelihood estimation (e.g. Guimerá and Sales-Pardo 2009); others utilise the community detection methods (e.g. Clauset et al. 2008).”
BackgroundMethodHierarchical core maintenance on large dynamic graphs
Lin, Z., Zhang, F., Lin, X., Zhang, W., & Tian, Z. (2021) · Proceedings of the VLDB Endowment · doi:10.14778/3446095.3446099 · Cited by 57
Joint multi-label learning and feature extraction for temporal link prediction
Ma, X., Tan, S., Xie, X., Zhong, X., & Deng, J. (2021) · Pattern Recognition · doi:10.1016/j.patcog.2021.108216 · Cited by 60
Nodes' Evolution Diversity and Link Prediction in Social Networks
Wang, H., Hu, W., Qiu, Z., & Du, B. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2017.2728527 · Cited by 58
“For example, the prior assumption of hierarchical network organizations can be directly applied to the design of a link prediction algorithm [21].”
BackgroundMethodInfluentialCLP-ID: Community-based link prediction using information diffusion
Singh, S. S., Mishra, S., Kumar, A., & Biswas, B. (2019) · Information Sciences · doi:10.1016/j.ins.2019.11.026 · Cited by 56
Review on Learning and Extracting Graph Features for Link Prediction
Mutlu, E. C., Oghaz, T., Rajabi, A., & Garibay, I. (2020) · Machine Learning and Knowledge Extraction · doi:10.3390/make2040036 · Cited by 65
“The model was first proposed in the work of [76], in which it develops a hierarchical network model that can be represented by a dendrogram, with | N | leaves and | N − 1 | internal nodes.”
BackgroundSoK: Privacy-Preserving Data Synthesis
Hu, Y., Wu, F., Li, Q., Long, Y., Garrido, G. M., Ge, C., Ding, B., Forsyth, D. A., Li, B., & Song, D. X. (2024) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp54263.2024.00002 · Cited by 100
“Compared to other works, the HRG model achieves the smallest global sensitivity and therefore requires the least amount of noise to ensure edge-DP.”
BackgroundInfluentialUbiquitousness of link-density and link-pattern communities in real-world networks
Šubelj, L., & Bajec, M. (2012) · The European Physical Journal B · doi:10.1140/epjb/e2011-20448-7 · Cited by 65
Estimating topological properties of weighted networks from limited information
Cimini, G., Squartini, T., Gabrielli, A., & Garlaschelli, D. (2015) · Physical Review E · doi:10.1103/physreve.92.040802 · Cited by 66
Scalable text and link analysis with mixed-topic link models
Zhu, Y., Yan, X., Getoor, L. C., & Moore, C. (2013) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2487575.2487693 · Cited by 62
“[8, 23, 34]) is a natural generalization task in networks, and another way to measure the quality of our model and our EM algorithm.”
Self-citationFeng, S., Li, H., Qi, Y., Guan, Q., & Wen, S. (2017) · Energy · doi:10.1016/j.energy.2017.09.030 · Cited by 55
Friend recommendation in social networks based on multi-source information fusion
Cheng, S., Zhang, B., Zou, G., Huang, M., & Zhang, Z. (2018) · International Journal of Machine Learning and Cybernetics · doi:10.1007/s13042-017-0778-1 · Cited by 63
Link Prediction in Weighted Networks: A Weighted Mutual Information Model
Zhu, B., & Xia, Y. (2016) · PLoS ONE · doi:10.1371/journal.pone.0148265 · Cited by 54
Link prediction using node information on local paths
Aziz, F., Gul, H., Muhammad, I., & Uddin, M. I. (2020) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2020.124980 · Cited by 57
Predicting Links and Inferring Attributes using a Social-Attribute Network (SAN)Preprint
Gong, N. Z., Talwalkar, A., Mackey, L. W., Huang, L., Shin, E. C. R., Shin, R., & Stefanov, E. (2011) · arXiv (Cornell University) · Cited by 54
Graph Geometry Interaction Learning
Zhu, S., Pan, S., Zhou, C. D., Wu, J. X., Cao, Y., & Wang, B. (2020) · Monash University Research Portal (Monash University) · doi:10.48550/arxiv.2010.12135 · Cited by 71
Link prediction approach to recommender systems
Lakshmi, T. J., & Bhavani, S. D. (2023) · Computing · doi:10.1007/s00607-023-01227-0 · Cited by 55
“Clauset et al. [35] propose a probabilistic model based on hierarchical structure of the network.”
Link Prediction for Partially Observed Networks
Zhao, Y., Wu, Y.-J., Levina, E., & Zhu, J. (2017) · Journal of Computational and Graphical Statistics · doi:10.1080/10618600.2017.1286243 · Cited by 61
“Other supervised methods use probabilistic models for incomplete networks to do link prediction, for example, the hierarchical structure models [6], latent space models [11], latent variable models [10, 18], and stochastic relational models [21].”
MethodIncreasing the reliability of protein–protein interaction networks via non-convex semantic embedding
Zhu, L., You, Z., & Huang, D.-S. (2013) · Neurocomputing · doi:10.1016/j.neucom.2013.04.027 · Cited by 55
“Obviously, the number of direct and indirect interactions is much lower for sparser networks due to limited connectivity, which makes them sensitive to noise and inevitably leads to unreliable indices [19,20].”
BackgroundSemi-supervised Graph Embedding Approach to Dynamic Link Prediction
Hisano, R. (2018) · Springer proceedings in complexity · doi:10.1007/978-3-319-73198-8_10 · Cited by 53
Link direction for link prediction
Shang, K.-K., SMALL, M. P., & Yan, W.-S. (2016) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2016.11.129 · Cited by 53
Extended resource allocation index for link prediction of complex network
Liu, S., Ji, X., Liu, C., & Bai, Y. (2017) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2017.02.078 · Cited by 53
Common power laws for cities and spatial fractal structures
Mori, T., Smith, T. E., & Hsu, W. (2020) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1913014117 · Cited by 67
Revealing Consensus and Dissensus between Network Partitions
Peixoto, T. P. (2021) · Physical Review X · doi:10.1103/physrevx.11.021003 · Cited by 72
Assessment of community efforts to advance network-based prediction of protein–protein interactions
Wang, X., Madeddu, L., Spirohn, K., Martini, L., Fazzone, A., Becchetti, L., Wytock, T. P., Kovács, I. A., Balogh, O. M., Benczik, B., et al. (2023) · Nature Communications · doi:10.1038/s41467-023-37079-7 · Cited by 58
“The likelihood of D associated with a set of probabilities {pr} is, then, given by [38]: L(D, {pr}) = ∏ r∈D pr r (1− pr)rrr .”
BackgroundLink prediction based on path entropy
Xu, Z., Pu, C., & Yang, J. J. (2016) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2016.03.091 · Cited by 53
Ferrario, E., Pedroni, N., & Zio, E. (2016) · Reliability Engineering & System Safety · doi:10.1016/j.ress.2016.06.007 · Cited by 60
“In addition, several studies show that networks often exhibit hierarchical organization [Ravasz and Barabasi, 2003; Clauset et al., 2008].”
BackgroundGalaxy Network Embedding: A Hierarchical Community Structure Preserving Approach
Du, L., Lu, Z., Wang, Y., Song, G., Wang, Y., & Chen, W. (2018) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2018/287 · Cited by 58
“…community structure preservation, four Hierarchical Random Graphs (HRG) with explicit hierarchical community structure are generated by [ Clauset et al. , 2008 ] , i.e. Syn with 125nodes (125 nodes, 406 edges), Syn with 1800nodes (1800nodes, 739637 edges), Syn with 2560nodes (2560…”
BackgroundLocal differential privacy for social network publishing
Liu, P., Xu, Y., Jiang, Q., Tang, Y., Guo, Y., Wang, L.-E., & Li, X. (2019) · Neurocomputing · doi:10.1016/j.neucom.2018.11.104 · Cited by 53
On the Spectral Characterization and Scalable Mining of Network Communities
Yang, B., Liu, J., & Feng, J. (2010) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.233 · Cited by 52
“The optimization based methods solve an NCMP by transforming it into an optimization problem and trying to find an optimal solution for a predefined objective function, such as different kinds of cut criteria adopted by different spectral methods [5], [6], [7], [8], [9], the evaluation function used in theKernighan-Li…”
MethodHierarchical Graph Clustering using Node Pair SamplingPreprint
Bonald, T., Charpentier, B., Galland, A., & Hollocou, A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.01664 · Cited by 81
Active learning for node classification in assortative and disassortative networks
Moore, C., Yan, X., Zhu, Y., Rouquier, J., & Lane, T. D. R. (2011) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2020408.2020552 · Cited by 64
“This approach was used, for instance, for a hierarchical block model in [10].”
MethodSelf-citationGuan, Q., & An, H. (2017) · Applied Energy · doi:10.1016/j.apenergy.2017.06.026 · Cited by 51
Similarity-based future common neighbors model for link prediction in complex networks
Li, S., Huang, J., Zhang, Z., Liu, J., Huang, T., & Chen, H. (2018) · Scientific Reports · doi:10.1038/s41598-018-35423-2 · Cited by 62
Hierarchical zeolites: synthesis, structural control, and catalytic applications
Qu, H., Ma, Y., Li, B., & Wang, L. (2020) · Emergent Materials · doi:10.1007/s42247-020-00088-z · Cited by 56
Community Structure in Online Collegiate Social NetworksPreprint
Traud, A. L., Kelsic, E. D., Mucha, P. J., & Porter, M. A. (2008) · arXiv (Cornell University) · Cited by 96
Submodular Inference of Diffusion Networks from Multiple TreesPreprint
Gomez-Rodriguez, M., & Schölkopf, B. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1205.1671 · Cited by 51
“…three different 1,024 node Kronecker networks: a random network (Erdős & Rényi, 1960) (parameter matrix[0.5, 0.5; 0.5, 0.5]), a hierarchical network (Clauset et al., 2008) ([0.9, 0.1; 0.1, 0.9]) and a core-periphery network (Leskovec et al., 2008) ([0.9, 0.5; 0.5, 0.3]), and200 observed cascades.”
InfluentialMultiscale community detection in Cytoscape
Singhal, A., Cao, S., Churas, C., Pratt, D., Fortunato, S., Zheng, F., & Ideker, T. (2020) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1008239 · Cited by 53
Mørup, M., & Schmidt, M. N. (2012) · Neural Computation · doi:10.1162/neco_a_00314 · Cited by 61
“Link prediction as measured by the area under curve (AUC) of the receiver operator characteristic has become a standard for the evaluation of network models [2, 16].”
MethodPredicting Hidden Links in Supply Networks
Brintrup, A. M., Wichmann, P., Woodall, P., McFarlane, D., Nicks, E., & Krechel, W. E. (2018) · Complexity · doi:10.1155/2018/9104387 · Cited by 50
“[10] proposed the hierarchical random graph model, which builds a dendrogram representing a hierarchical abstraction of the network under study.”
BackgroundA gravitation-based link prediction approach in social networks
Bastami, E., Mahabadi, A., & Taghizadeh, E. (2018) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2018.03.001 · Cited by 53
Tuning Hierarchical ZSM-5 Zeolite for Both Gas- and Liquid-Phase Biorefining
Zhao, S., Wang, W. D., Wang, L., Schwieger, W., Wang, W., & Huang, J. (2019) · ACS Catalysis · doi:10.1021/acscatal.9b04104 · Cited by 49
Wen, J., Gabryś, B., & Musiał, K. (2022) · IEEE Access · doi:10.1109/access.2022.3184801 · Cited by 58
“[36], knowledge graphs [37] and biochemical networks of protein interaction [38] and metabolism [35].”
BackgroundDetection of node group membership in networks with group overlap
Sawardecker, E. N., Sales‐Pardo, M., & Amaral, L. A. N. (2008) · The European Physical Journal B · doi:10.1140/epjb/e2008-00418-0 · Cited by 49
Connectivity, Cycles, and Persistence Thresholds in Metapopulation Networks
Artzy‐Randrup, Y., & Stone, L. (2010) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000876 · Cited by 49
“many other scientific contexts including the dynamics of disease epidemics that spread via complex large-scale travel networks, internet traffic and computer virus dynamics or metabolic network analyses [10–14].”
BackgroundProactive Defense for Evolving Cyber Threats
Sandia National Laboratories (SNL-NM), A., Colbaugh, R., (NNSA), U. N. N. S. A., & Glass, K. (2012) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.2172/1059470 · Cited by 50
An Empirical Study of the Relation between Community Structure and Transitivity
Orman, G. K., Labatut, V., & Cherifi, H. (2012) · Studies in computational intelligence · doi:10.1007/978-3-642-30287-9_11 · Cited by 55
“Contrarily to the first cited studies [3, 4], we consider non-hierarchical networks, since this property does not seem to”
BackgroundLack of Gromov-hyperbolicity in small-world networks
Shang, Y. (2012) · Open Mathematics · doi:10.2478/s11533-012-0032-8 · Cited by 52
Statistics of the network of organic chemistry
Jacob, P., & Lapkin, A. A. (2018) · Reaction Chemistry & Engineering · doi:10.1039/c7re00129k · Cited by 53
Structure-oriented prediction in complex networks
Ren, Z.-M., Zeng, A., & Zhang, Y. (2018) · Physics Reports · doi:10.1016/j.physrep.2018.05.002 · Cited by 50
“[123] focused on the hierarchical structure inherent in social and biological networks and proposed the hierarchical structure model (HSM) to predict missing links.”
BackgroundMatching–centrality decomposition and the forecasting of new links in networks
Rohr, R. P., Naisbit, R. E., Mazza, C., & Bersier, L. (2016) · Proceedings of the Royal Society B Biological Sciences · doi:10.1098/rspb.2015.2702 · Cited by 54
“Models have been devised to predict these ‘missing links’ and thus correct a network dataset for this incomplete sampling or direct future research towards these candidate interactions [4,5].”
BackgroundSpectral clustering for link prediction in social networks with positive and negative links
Symeonidis, P., & Mantas, N. (2013) · Social Network Analysis and Mining · doi:10.1007/s13278-013-0128-6 · Cited by 53
Detecting Communities under Differential Privacy
Nguyen, H. H., Imine, A., & Rusinowitch, M. (2016) · ACM Workshop on Privacy in the Electronic Society (WPES) · doi:10.1145/2994620.2994624 · Cited by 61
Link prediction in complex networks based on the interactions among paths
Yao, Y., Zhang, R., Yang, F., Tang, J., Yuan, Y., & Hu, R. (2018) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2018.06.051 · Cited by 47
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.