Source-linked AI summary
Hierarchical structure and the prediction of missing links in networks
Aaron Clauset, Cristopher Moore, M. E. J. Newman
TL;DR
The paper models networks with hierarchical, inhomogeneous connection probabilities rather than uniform probabilities. It samples dendrograms, predicts missing connections, and reports strong practical performance while noting computational and evaluation limits.
Problem
Uniform edge probabilities do not represent networks whose connection rates are controlled by hierarchical structure.
Method
The method samples dendrograms with probability proportional to likelihood using Markov chain Monte Carlo and scores candidate missing connections.
Results
With 50% of the network missing, the method predicts missing connections about ten times better than chance across three networks.
Takeaways & Limitations
The approach can support interactive discovery of missing connections by iteratively testing predictions and updating the network.
Takeaways & Limitations
The fitting procedure lacks a rigorous performance guarantee and may require exponential time to equilibrate in the worst case.
Abstract
from arXiv · showhide
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, where vertices divide into groups that further subdivide into groups of groups, and so forth over multiple scales. In many cases these 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 demonstrate 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 partially 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.
APPENDIX A: HIERARCHICAL RANDOM GRAPHS
The hierarchical random graph assigns edge probabilities according to the dendrogram’s lowest common ancestors, allowing multiscale organization and nonuniform connectivity patterns.
- Each dendrogram is a binary tree whose leaves represent vertices and whose internal nodes represent nested vertex groups.
- A vertex pair’s connection probability equals the parameter associated with its lowest common ancestor in the dendrogram.
- Equal-probability connections among three subcommunities can be represented by any of three equally likely binary dendrograms.
- Unlike Erdős–Rényi G(n, p), the model has independent but inhomogeneous edge probabilities controlled by dendrogram topology and node parameters.
APPENDIX B: FITTING THE HIERARCHICAL RANDOM GRAPH TO DATA
The paper fits hierarchical random graphs to observed networks by evaluating dendrogram likelihoods and sampling plausible structures with Monte Carlo methods. High-likelihood dendrograms partition vertices into groups with connections that are very common or very rare, but practical convergence lacks a rigorous guarantee.
- The fitting objective is to maximize, or more generally sample, the likelihood of hierarchical random-graph models generating the observed network.
- In the six-vertex example, L(D2) = 0.0433... exceeds L(D1) = 0.00165... because D2 separates two highly connected subgraphs at the first level.
- For a fixed dendrogram, each node probability is the fraction of potential cross-subtree edges that appear in the observed graph.
- High-likelihood dendrograms partition vertices into groups whose between-group connection probabilities are close to 0 or 1, minimizing entropy.
- Markov chain Monte Carlo samples dendrograms through subtree rearrangements and Metropolis–Hastings acceptance, while many dendrograms can have similar likelihoods.
- The likelihood reaches a plateau after roughly O(n^2) steps, but equilibration may take exponential time in the worst case and the method handles up to a few thousand vertices reasonably.
APPENDIX C: RESAMPLING FROM THE HIERARCHICAL RANDOM GRAPH
The resampling procedure generates networks from dendrograms sampled according to their likelihoods, then averages network statistics across the resulting ensemble. This tests whether inferred hierarchy reproduces structural properties of the observed network.
- Resampling initializes a random dendrogram, runs Monte Carlo to equilibrium, and samples dendrograms at regular intervals.
- For each sampled dendrogram, the procedure generates a graph by independently placing every vertex pair with probability determined by its lowest common ancestor.
- Averages over sampled graphs estimate equilibrium-ensemble distributions of degree, clustering, vertex-vertex distance, and other network statistics.
- Consensus dendrograms weight the most likely sampled dendrograms proportionally to the square of their likelihood.
- For the grassland network, resampled and original degree and vertex-vertex distance distributions are compared.
APPENDIX D: PREDICTING MISSING CONNECTIONS
The method predicts missing connections by averaging hierarchical-graph probabilities for unconnected vertex pairs and ranking candidates. It performs strongly on the example networks, but its advantage depends on hierarchical structure and evaluation choice.
- Prediction procedure: The algorithm samples dendrograms with a Monte Carlo procedure, averages connection probabilities for unconnected vertex pairs, and ranks pairs by decreasing mean probability.The highest-ranked pairs are treated as the most likely missing connections.
- Results: The top 1% of predictions are highly accurate, although large networks may still produce too many candidates for feasible experimental checking.The authors suggest iteratively testing a small number of predictions, adding confirmed results, and rerunning the algorithm.
- Prediction procedure: The method is compared with common-neighbor, Jaccard, degree-product, and short-path scores that rank candidate pairs using local or path-based information.These alternatives were previously investigated for link prediction.
- Results: 10 times better than chance is achieved when 50% of the network is missing, while accuracy rises as high as 200 times better than chance when few connections are missing.The ratio compares the probability that the top-ranked pair is connected with the corresponding probability for a randomly chosen unconnected pair.
- Evaluation caveat: The ratio-based evaluation can favor easy-to-predict missing edges, whereas AUC measures overall ranking of missing connections against nonexistent ones.High-degree pairs in heavy-tailed networks can make simple heuristics appear effective under the ratio measure.
- Scope: On Erdős–Rényi graphs no method performs better than chance, while degree-based guessing performs well and the hierarchical method performs poorly on configuration-model graphs without hierarchical structure.These tests indicate that the hierarchical method is not expected to outperform simpler heuristics when the graph lacks hierarchy.