Source-linked AI summary
Predicting Missing Links via Local Information
Tao Zhou, Linyuan Lu, Yi-Cheng Zhang
TL;DR
The paper addresses how to predict missing links and compares local similarity measures for this task. It reports that common neighbors performs best overall, Adamic–Adar second, and proposes new measures, while noting that the findings need further empirical evidence.
Problem
The paper examines how to predict missing links and addresses a lack of systematic comparison and clear understanding among similarity measures.
Method
The paper compares local similarity measures for nonexistent links and proposes a new resource-allocation-inspired measure.
Results
Common neighbors performs best overall, while the Adamic–Adar index performs second best; other measures show remarkable differences in performance.
Takeaways & Limitations
The comparison identifies common neighbors and Adamic–Adar as the strongest overall measures among those evaluated, while motivating further measure design.
Takeaways & Limitations
The validity of the conclusions needs further evidence from more empirical results.
Abstract
from arXiv · showhide
Missing link prediction of networks is of both theoretical interest and practical significance in modern science. In this paper, we empirically investigate a simple framework of link prediction on the basis of node similarity. We compare nine well-known local similarity measures on six real networks. The results indicate that the simplest measure, namely common neighbors, has the best overall performance, and the Adamic-Adar index performs the second best. A new similarity measure, motivated by the resource allocation process taking place on networks, is proposed and shown to have higher prediction accuracy than common neighbors. It is found that many links are assigned same scores if only the information of the nearest neighbors is used. We therefore design another new measure exploited information of the next nearest neighbors, which can remarkably enhance the prediction accuracy.
1 Introduction
The introduction frames missing-link prediction as useful for incomplete networks and recommendations, then identifies a need to understand how topology affects algorithm performance. The paper addresses this through local node-similarity measures, proposing resource-allocation and next-nearest-neighbor approaches.
- Motivation: Missing-link prediction can reduce costly laboratory or field searches by prioritizing interactions likely to exist.The same approach can suggest promising friendships in online social networks.
- Limitations of prior approaches: Existing approaches often use content or node attributes that are generally unavailable, limiting their applications.This motivates prediction using network topology alone.
- Open problem: A comprehensive understanding of how prediction performance depends on network topology remains lacking.The introduction highlights choosing algorithms from structural features such as small-world behavior, degree heterogeneity, mixing pattern, and community structure.
- Open problem: Local-information algorithms are generally fast but less accurate, whereas global-topology methods are more accurate but computationally more complex.The paper therefore seeks a tradeoff between prediction quality and computational demands.
- Paper approach and contributions: The study compares nine local similarity measures on six real networks and finds common neighbors performs best overall, with Adamic-Adar second.It also proposes a resource-allocation measure that outperforms common neighbors without requiring more information or computation, plus a next-nearest-neighbor measure that improves accuracy by breaking score degeneracy.
- Paper approach and contributions: Many links receive identical scores from nearest-neighbor information, motivating a measure that uses next-nearest neighbors to remarkably enhance accuracy.The paper describes these equal scores as degenerate states.
2 Method
The method assigns similarity scores to nonexistent links using network topology, ranks candidates by score, and evaluates predictions against held-out links. Accuracy is measured with AUC using a 90% training and 10% probe split.
- Scoring and ranking: Each algorithm assigns a similarity score s_xy to every node pair, treating score and similarity interchangeably.Nonexistent links are sorted in decreasing score order, placing the most likely links at the top.
- Evaluation protocol: Observed links are randomly divided into a training set used as known information and a probe set reserved for testing.The two sets are disjoint.
- Evaluation protocol: 90% of links form the training set, while the remaining 10% constitute the probe set.The probe links are withheld from the prediction procedure.
- Evaluation metric: In implementation, AUC is estimated from n independent comparisons, awarding full credit to higher-scoring missing links and half credit to ties.The equation uses n′ for wins and n′′ for tied comparisons.
3 Data
The study uses six representative real networks from biological, collaboration, infrastructure, political, Internet, and transportation domains. It summarizes their topology with network size, connectivity, efficiency, clustering, assortativity, and degree heterogeneity measures.
- Network sample: The dataset spans protein interactions, scientific coauthorship, an electrical grid, political blogs, Internet routers, and US air transportation.The networks are drawn from disparate fields and are treated as the empirical test cases.
- Network sample: The US air-transportation network contains 332 airports and 2126 airlines.Nodes represent airports and links represent airline connections.
- Topological characterization: Table 1 summarizes node and link counts, giant-component size, efficiency, clustering, assortativity, and degree heterogeneity for the six networks.The study defines these as monitored topological features used to characterize the datasets.
- Topological characterization: The protein-interaction dataset has assortative coefficient 0.461, unlike the negative assortativity expected for physical protein interactions.The paper attributes this difference to the dataset representing functional rather than physical interactions.
- Topological characterization: The collaboration network has an extremely large clustering coefficient because all participants in an act are fully connected.This clustering reflects the network’s construction rule.
Based on Local Information
The paper compares nine local similarity measures for link prediction across six example networks. Common neighbors performs best overall, while performance differences depend on network structure and the measure’s treatment of node degree.
- Evaluation: Nine local similarity measures are compared using algorithmic accuracies on six example networks.Table 2 reports accuracies measured by area under the curve.
- Overall comparison: Common neighbors, the simplest measure, performs best overall.Its strong performance is reported across the six example networks.
- Overall comparison: Adamic-Adar performs second best, with accuracies consistently close to the best measure.Jaccard, Sørensen, and Hub Depressed Index perform far worse for PB and USAir.
- Structural dependence: Differences among the first seven measures are small when node degrees are similar or clustering is low.Large differences emerge mainly when clustering and degree heterogeneity are both large.
- Preferential attachment: Preferential attachment has the worst overall performance despite requiring minimal information.It performs relatively well for PB and USAir but badly for networks with many components and for geographically constrained networks.
- Preferential attachment: Preferential attachment cannot capture geographical localization, contributing to poor performance in the router-level Internet and power grid.These networks contain physical links for which long geographical distances are rare.
Allocation
The paper introduces resource allocation as a node-similarity measure motivated by resource transfer through common neighbors. It reports higher accuracy than the nine existing measures, especially on networks with particular structural features.
- Resource allocation measure: Resource allocation assigns similarity according to the amount of resource transferred between nodes through common neighbors.Each common neighbor distributes one unit of resource equally among its neighbors, producing a symmetric similarity.
- Results: Resource allocation performs best among all nine existing measures.Its strongest results occur for PB and USAir, which have large clustering, high degree heterogeneity, and no strongly assortative linking pattern.
- Comparison with Adamic-Adar: Adamic-Adar and resource allocation have similar forms because both reduce contributions from high-degree common neighbors.Their prediction results are close for low-average-degree networks but differ clearly on PB and USAir, where resource allocation performs better.
- Asymmetric extension: The resource-allocation process can be extended to an asymmetric similarity in which resource starts at x and is distributed two steps toward y.The resulting importance of y from x is not generally equal to the importance of x from y.
Breaking the Degenerate States
The paper addresses tied scores produced by nearest-neighbor information by incorporating length-3 paths into a local-path similarity measure. This substantially improves accuracy in most tested networks, except USAir.
- Degenerate scores: Common-neighbor scores are highly degenerate: 99.59% of more than 10^7 node pairs receive zero, while 91.11% of positive-scoring pairs receive score 1.Only 4.48% of positive-scoring pairs receive score 2.
- Local Path index: The length-3 contribution is intended to break degenerate states and distinguish scores that nearest-neighbor information leaves tied.The parameter ϵ is set close to zero so that the added term mainly separates tied scores.
- Practical limitation: Tuning ϵ can produce higher accuracy, but the optimal value differs across networks and may be impractical to find for huge networks.The paper therefore treats a parameter-dependent implementation as less practical for large-scale use.
- Results: With ϵ = 10^-3, Local Path substantially enhances accuracy in all tested networks except USAir.The measure is evaluated on six example networks using the fixed parameter.
- Results: Local Path performs worse than common neighbors in USAir because its hierarchical hub structure makes the added length-3 information change rankings little.The network contains hubs, local centers, and small local airports with many shared neighbors.
7 Conclusion and Discussion
The paper compares local similarity measures for link prediction, identifies strong-performing simple and resource-allocation-based measures, and extends local information with next-nearest neighbors. It also discusses tradeoffs between prediction accuracy, computational efficiency, and empirical scope.
- Common neighbors has the best overall performance among the compared measures, while Adamic-Adar performs second best.
- Preferential attachment performs relatively well when networks have a rich-club phenomenon, but performs worst overall and is less effective under other structural conditions.
- RA is proposed from a resource allocation process and performs better than Adamic-Adar, especially on networks with high average degrees.The measure is equivalent to a one-step random walk starting from common neighbors.
- The empirical conclusions remain limited because real networks contain unknown and uncontrollable factors, and RA’s suitability for transportation networks needs further evidence.
- Many local measures assign identical scores when using nearest-neighbor information alone, while next-nearest-neighbor information can break these degeneracies and enhance accuracy.
- Local algorithms offer a potential efficiency–accuracy tradeoff because global methods may require substantial time or memory, whereas very local methods may have lower accuracy.