Source-linked AI summary
Link Prediction in Complex Networks: A Survey
Linyuan Lu, Tao Zhou
TL;DR
Link prediction in complex networks seeks to recover missing or spurious relationships and assess how networks evolve. This survey synthesizes similarity-based, random-walk, maximum-likelihood, and probabilistic approaches, together with applications in reconstruction, evolution evaluation, and partially labelled classification. It also identifies unresolved challenges, especially for multi-dimensional networks and for combining within-class and between-class links.
Problem
Link prediction is needed because many biological and social networks contain missing or unknown interactions, while direct experimental discovery can be costly.
Method
The survey organizes similarity-based, maximum-likelihood, probabilistic, and physical approaches, and reviews applications in network reconstruction, evolution evaluation, and partially labelled classification.
Results
The survey reports that link prediction can extract missing information, identify possible spurious interactions, and evaluate network-evolving mechanisms.
Takeaways & Limitations
Link prediction provides a framework for analyzing incomplete networks and comparing explanations of their evolution.
Takeaways & Limitations
Important open scope boundaries include multi-dimensional links and models that jointly use within-class and between-class connections.
Abstract
from arXiv · showhide
Link prediction in complex networks has attracted increasing attention from both physical and computer science communities. The algorithms can be used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. This article summaries recent progress about link prediction algorithms, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods. We also introduce three typical applications: reconstruction of networks, evaluation of network evolving mechanism and classification of partially labelled networks. Finally, we introduce some applications and outline future challenges of link prediction algorithms.
1 Introduction
Link prediction addresses missing or future relationships in complex networks, where experiments and incomplete observations make direct identification difficult. This survey organizes recent algorithms, emphasizing structural and physical approaches and applications including network reconstruction and evaluation of network evolution.
- Motivation: Biological network link prediction can prioritize likely interactions, potentially reducing costly experimental checking when predictions are accurate.The passage cites substantial unknown interaction fractions in yeast and human cellular networks.
- Motivation: Link prediction also supports recommending likely future social links and evaluating competing mechanisms for evolving networks.The survey gives online friendship recommendation and Internet-topology models as examples.
- Research gap: Existing computer-science approaches based on Markov chains and statistics often give insufficient attention to hierarchical and community structure.The survey presents these structural characteristics as potentially useful for link prediction.
- Survey scope: The survey covers similarity-based, maximum-likelihood, and probabilistic-model algorithms, followed by applications and future challenges.Similarity-based methods are divided into local, global, and quasi-local indices.
2 Problem Description and Evaluation Metrics
Link prediction treats unobserved node pairs as candidates for missing or future links and evaluates ranked predictions against held-out observed links. AUC assesses ranking across candidates, whereas Precision focuses on the top-L predictions.
- Problem formulation: The task is to identify missing or future links within the nonexistent-link set U−E of an undirected network.The network excludes multiple links and self-connections.
- Validation: Random subsampling splits observed links into training and probe sets, but can select some links repeatedly or omit others.The training set is used for prediction, while probe-set information is withheld.
- Validation: K-fold cross-validation reduces this sampling bias by using every subset once for testing, although larger K increases computation.The passage describes 10-fold cross-validation as a reported cost-performance tradeoff.
- Metrics: AUC evaluates the full ranking, while Precision measures the fraction of correct links among the top-L predictions.AUC compares scores for randomly selected missing and nonexistent links; Precision is Lr/L.
- Metrics: An AUC near 0.5 corresponds to independently distributed scores, so values above 0.5 indicate performance better than chance.The degree of exceedance over 0.5 reflects improvement over pure chance.
3 Similarity-Based Algorithms
Similarity-based link prediction assigns scores to non-observed node pairs and ranks them by inferred likelihood, using local, global, or quasi-local structural information. Across reported experiments, resource-allocation and path-based methods perform strongly, while quasi-local methods offer accuracy–complexity tradeoffs for large networks.
- Similarity-based algorithms: Similarity-based algorithms rank non-observed node pairs by scores defined from node similarity, with higher-scoring pairs treated as more likely links.Structural similarity relies on network topology when node attributes are hidden.
- Similarity-based algorithms: The survey classifies 20 structural similarity indices into 10 local, 7 global, and 3 quasi-local indices.Quasi-local indices use more information than local methods without requiring global topological information.
- 3.1 Local Similarity Indices: RA performs best overall among local indices, while AA and CN achieve the second-best overall performance across tested real networks.PA has the worst overall performance and can perform worse than chance in the router-level Internet and power-grid networks.
- 3.1 Local Similarity Indices: Geographic constraints explain why PA performs poorly in the Internet and power-grid networks, whereas it performs better for USAir where links are less distance-sensitive.The LHN1 index is comparatively effective for recovering links between two low-degree nodes.
- 3.2 Global Similarity Indices: Global indices can be more accurate than local indices but require whole-network information and often incur prohibitive computation, motivating quasi-local alternatives.The survey describes quasi-local indices as retaining useful information while discarding superfluous information.
- 3.3 Quasi-Local Indices: LP improves prediction by using higher-order neighborhood information to distinguish similarity scores, achieving the best Precision among LP, Katz, and LHN2 while remaining lighter to compute.LRW and SRW also outperform other indices with optimal walking steps correlated with average shortest distance, and their n-step complexity is approximately O(N⟨k⟩^n).
4 Maximum Likelihood Methods
Maximum likelihood methods infer organizing principles and parameters from observed network structure, then estimate the likelihood of unobserved links. The survey discusses hierarchical and stochastic block models, which can reveal network organization but are computationally demanding.
- Overview: Maximum likelihood algorithms infer network-structure rules and parameters by maximizing the likelihood of the observed structure, then score non-observed links.The resulting link likelihoods support ranking candidate links.
- Limitations: Maximum likelihood methods are very time consuming: they can handle networks with up to a few thousand nodes but fail on huge online networks with millions of nodes.Hierarchical sampling may require O(N^2) Markov-chain steps and can take exponential time in the worst case.
- Hierarchical Structure Model: Hierarchical structure models represent networks with dendrograms whose internal nodes specify connecting probabilities for pairs according to their lowest common ancestor.For a fixed dendrogram, the probabilities are chosen to best fit the observed network.
- Hierarchical Structure Model: Hierarchical prediction samples dendrograms in proportion to likelihood, averages connecting probabilities across samples, and ranks unconnected node pairs by those averages.The procedure uses Markov chain Monte Carlo sampling.
- Stochastic Block Model: Stochastic block models partition nodes into groups and make connection probabilities depend on the groups containing each pair.They estimate group-to-group probabilities from observed edge counts and can evaluate link reliability.
- Stochastic Block Model: Empirical comparisons across five disparate networks found the stochastic-block-model maximum likelihood method outperformed the hierarchical model and common-neighbors similarity algorithm overall.Reliability can identify likely missing links and possible spurious links.
5 Probabilistic Models
Probabilistic models learn latent relational structure from observed networks and estimate conditional probabilities for missing links. The survey distinguishes relational Bayesian, Markov, and dependency networks, alongside the more expressive DAPER model and a relational Gaussian-process approach.
- Probabilistic Models: Probabilistic models fit parameters Θ to an observed network and estimate each nonexistent link’s existence probability as P(Aij = 1|Θ).They abstract the underlying structure before predicting missing links.
- Probabilistic Relational Models: Probabilistic relational models represent joint distributions over attributes of objects and related objects in a relational dataset.The data, model, and inference graphs describe input relationships, attribute dependencies, and instantiated test-set dependencies.
- Relational Bayesian Networks: Relational Bayesian Networks use directed acyclic graphs and conditional probability distributions, but complete ground-network inference limits scalability and model specification is burdensome.They require a complete conditional model for each attribute of each class.
- Relational Markov Networks: Relational Markov Networks use undirected graphs and clique potential functions, with MAP learning and belief-propagation inference that create high learning complexity.They are trained discriminatively rather than specifying a complete joint distribution.
- Relational Dependency Networks: Relational Dependency Networks represent cyclic relational dependencies with conditional distributions, using pseudo-likelihood learning and Gibbs sampling for unobserved variables.Their pseudo-likelihood need not factor the full joint distribution.
- Probabilistic Entity Relationship Models: DAPER gives relationships first-class status and represents entities, relationships, attributes, probabilistic arcs, local distributions, and inference constraints.The survey describes it as more expressive than PRMs or plate models and suitable when relational structure is uncertain.
- Relational Gaussian-Process Approach: A relational Gaussian-process model uses marginalized likelihood to exchange information across the relational network and adapt kernels to link dependencies.Its nonparametric priors are defined over infinite-dimensional tensor matrices representing entity-tuple relationships.
6 Applications
The survey presents link prediction as a tool for reconstructing networks, evaluating evolving mechanisms, and classifying partially labeled networks. Applications combine structural similarity with likelihood-based or external factors, while reconstruction and global indices retain important practical limitations.
- 6.1 Reconstruction of Networks: Reconstruction alternates removing the least reliable observed link and adding the most reliable absent link using a greedy algorithm.The exact reliability-maximizing optimization is too costly to implement directly.
- 6.1 Reconstruction of Networks: Reconstruction generally improves estimates of clustering, modularity, assortativity, congestability, synchronizability, and spreading threshold.The evaluation compares global properties of observed and reconstructed networks across six metrics.
- 6.1 Reconstruction of Networks: The reconstruction procedure assumes equal numbers of missing and spurious links, although real networks may violate this assumption substantially.The survey notes that the greedy solution may also differ considerably from the true maximum-reliability optimum.
- 6.2 Evaluation of Network Evolving Mechanisms: For evolving-mechanism evaluation, link-prediction accuracy provides a quantitative basis for comparing candidate mechanisms that explain link formation.The survey illustrates this framework with Chinese city airline networks using topology, geography, population, GDP, and tertiary-industry factors.
- 6.2 Evaluation of Network Evolving Mechanisms: A common-neighbor and tertiary-industry combination reaches an AUC of 0.928 at λ ≈ 0.2 in the Chinese city airline network.The airline-network experiment uses leave-one-out evaluation over 1,378 links.
7 Outlook
The outlook identifies unresolved challenges in extending link prediction beyond static, unweighted, undirected networks and suggests hybrid, attribute-aware, and time-sensitive approaches. It also highlights multi-dimensional networks as an important frontier.
- 7 Outlook: Current studies overwhelmingly focus on unweighted, undirected networks, leaving weighted and directed link prediction less resolved.For weighted networks, existing studies disagree about whether stronger or weaker links are more informative for predicting missing links.
- 7 Outlook: Multi-dimensional networks remain challenging because links may have signs or different meanings, and predicting both link existence and sign is still understudied.The paper identifies positive-versus-negative relations as one example of this unresolved setting.
- 7 Outlook: Networks containing multiple node classes require methods that jointly model within-class and between-class links.Existing work has studied links between users and objects while ignoring connections within a node class.
- 7 Outlook: Hybrid or ensemble algorithms may improve prediction accuracy by selecting and organizing multiple individual predictors for a target network.The authors describe ensemble systems as potentially valuable in practice, although their scientific significance is unclear to them.
- 7 Outlook: External node attributes can enhance link prediction, especially when observed links are unreliable.Attributes such as age, sex, and job can provide predictive information independently of network structure.
- 7 Outlook: Single-snapshot approaches struggle with repeated link occurrences, motivating temporal methods that model link evolution and give greater relevance to recent events.The paper uses repeated co-authorship and changing author interests as examples of why time-sensitive prediction is needed.