Hierarchical structure and the prediction of missing links in networks

By Aaron Clauset, Cristopher Moore, Mark Newman. 2008

2,150 citations recorded by the source corpus.

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.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Community detection in graphs (2009, methodology): “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.”
Supervised random walks: predicting and recommending links in social networks (2010, background): “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.”
Graph Embedding Techniques, Applications, and Performance: A Survey (2017, methodology): “Approaches for link prediction include similarity based methods [13], [14], maximum likelihood models [15], [16], and probabilistic models [17],”
Defining invasiveness and invasibility in ecological networks (2016, methodology): “Finally, the level of modularity was measured using a new algorithm QuanBimo (Dormann and Straub 2014; adapted from Claused and Newman 2008).”
The science of science: from the perspective of complex systems (2017, background): “Link prediction is a microscopic prediction seeking to retrieve missing links and forecast future links in a network [253].”
Hierarchical cooperation of transcription factors from integration analysis of DNA sequences, ChIP-Seq and ChIA-PET data (2019, background): “The hierarchical structure is an important feature of society networks [56] and genetic regulatory networks [57].”
Communities in Networks (2009, methodology): “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 comm”
Molecular ecological network analyses (2012, background): “Most complex systems have common characteristics such as small world, scale-free, modularity and hierarchy [8,53,54].”
Hierarchical block structures and high-resolution model selection in large networks (2013, methodology): “We also predict that it should serve as a more reﬁned 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…”