Source-linked AI summary
Link prediction in complex networks: a local naïve Bayes model
Zhen Liu, Qian-Ming Zhang, Linyuan Lü, Tao Zhou
TL;DR
Common-neighbor methods treat every common neighbor as contributing equally, although equal neighbor counts can correspond to different connection likelihoods. The paper proposes a local naïve Bayes model that weights common neighbors differently and reports more accurate predictions than corresponding basic indices across eight real networks, with a detailed US air-transportation case study.
Problem
Common-neighbor methods assume equal contributions from common neighbors, despite node pairs with the same common-neighbor count having different connection likelihoods.
Method
The local naïve Bayes model captures different roles of common neighbors and assigns them different weights when scoring non-observed links.
Results
Across eight real networks, the LNB forms outperform their corresponding CN, AA, and RA indices, with especially remarkable improvement on foodwebs.
Takeaways & Limitations
Accounting for common neighbors’ different roles provides more accurate missing-link predictions, including improved analysis of link types in the US air transportation network.
Takeaways & Limitations
The model relies on the naïve assumption that features are conditionally independent of one another.
Abstract
from arXiv · showhide
Common-neighbor-based method is simple yet effective to predict missing links, which assume that two nodes are more likely to be connected if they have more common neighbors. In such method, each common neighbor of two nodes contributes equally to the connection likelihood. In this Letter, we argue that different common neighbors may play different roles and thus lead to different contributions, and propose a local naïve Bayes model accordingly. Extensive experiments were carried out on eight real networks. Compared with the common-neighbor-based methods, the present method can provide more accurate predictions. Finally, we gave a detailed case study on the US air transportation network.
Introduction. –
Link prediction estimates whether unobserved node pairs are connected, with importance for understanding network evolution and costly biological-network experiments. Existing approaches include probabilistic, machine-learning, and node-similarity methods, but common-neighbor counts can miss differences between otherwise similar node pairs.
- Link prediction estimates the likelihood that two nodes are connected from observed network links.
- Accurate link prediction can provide evidence about mechanisms driving network evolution and support evaluation of network models.
- Biological-network link discovery is practically important because experiments identifying new interactions can be costly.
- Existing link-prediction methods include Markov-chain, machine-learning, and node-similarity algorithms.
- Common Neighbors predicts links using mutual-neighbor counts, but node pairs with equal counts may have different connection likelihoods.
Problem Description. –
The evaluation assigns scores to non-observed links and tests whether held-out links rank above nonexistent links. Accuracy is assessed across the full ranking with AUC and among the top L predictions with precision.
- Each nonexistent link receives a score, and links are ranked so higher-scoring pairs are predicted as more likely to exist.
- Observed links are split into a training set for prediction and a probe set reserved for testing.The training and probe sets are disjoint; the supplied implementation uses 90% and 10% of links, respectively.
- AUC measures whole-list ranking performance as the probability that a randomly chosen missing link outranks a randomly chosen nonexistent link.
- Precision measures the fraction of correctly predicted links among the top L highest-scoring links.If Lr probe-set links appear among the top L, precision equals Lr/L.
- AUC near 0.5 corresponds to chance-level ranking, while larger values above 0.5 indicate better-than-chance performance.
Method. –
The local naïve Bayes model ranks non-observed links by comparing connection and disconnection probabilities inferred from common neighbors. Unlike CN, it allows each common neighbor to contribute differently through a role function.
- Local Naïve Bayes Model: For a common neighbor w, P(w|A1) measures its occurrence among connected-node pairs, while P(w|A0) measures its occurrence among disconnected-node pairs.A1 and A0 denote connection and disconnection classes, respectively.
- Local Naïve Bayes Model: The model treats common neighbors as feature variables and assumes their roles are conditionally independent.Naïve Bayes combines the corresponding conditional probabilities for connection and disconnection.
- Local Naïve Bayes Model: For each non-observed node pair, the model scores connection likelihood and ranks links in descending order.Higher-ranked links are treated as more likely to exist.
- Local Naïve Bayes Model: The likelihood score is defined as the ratio of the posterior connection and disconnection probabilities, with larger scores indicating higher connection probability.The implementation applies add-one smoothing to prevent a zero score.
- Local Naïve Bayes Model: When Rw = 1 for every common neighbor, the model reduces to a monotone function of common-neighbor count and becomes equivalent to CN.Different Rw values therefore encode different common neighbors’ contributions to connection likelihood.
- Local Naïve Bayes Model: The method also introduces degree-dependent exponents, yielding Local Naïve Bayes forms corresponding to CN, AA, and RA indices.This extends the role-weighting idea to degree-based common-neighbor indices.
Results. –
The method was evaluated on eight real networks using AUC and precision. Across these networks, the Local Naïve Bayes forms generally outperformed their corresponding basic indices, with especially notable foodweb improvements.
- Experimental Results: Eight real networks, including USAir, C.elegans, Political Blogs, and two foodweb networks, were used in the experiments.The networks represent transportation, neural, political-blog, and foodweb systems.
- Experimental Results: The LNB forms generally outperform their corresponding basic forms on the eight-network evaluation.Accuracy was measured using AUC and precision.
- Experimental Results: For AUC, LNB improves prediction over the corresponding basic method on all eight networks except RA in the C.elegans network.The passage reports especially significant improvements on the foodweb networks.
- Experimental Results: For precision, LNB improves accuracy except for CN in the Political Blogs network.The result is consistent with LNB-CN capturing differing common-neighbor roles rather than assigning equal weights.
Case Study. –
The USAir case study shows that LNB-CN reorders predictions by recognizing that common neighbors can have different roles, especially across airport types and geographically separated pairs.
- Case Study.: USAir contains 332 airports and 2126 airlines organized into hubs, local centers, and local airports with sharply different link probabilities.The six airport-type link categories range from 97.06% for Hub-Hub links to 0.72% for LA-LA links.
- Case Study.: LNB-CN improves predictions for Hub-LC and LC-LC links by reducing scores for LC-LC pairs whose common neighbors play negative roles.Although LC-LC pairs have more common neighbors than Hub-LC pairs, Hub-LC links are more likely: 72.83% versus 26.24%.
- Case Study.: Among CN’s top-100 pairs moved below rank 100 by LNB-CN, only 2 of 11 were correct, while 6 were LC-LC and 3 were Hub-LC pairs.This indicates that LNB-CN lowers many non-existent links that CN ranks highly.
- Case Study.: Among LNB-CN’s top-100 pairs moved below rank 100 by CN, 5 of 6 were correct, indicating that LNB-CN raises missing links relative to CN.The figure compares corresponding ranks for the top-100 pairs selected by each method; hits are probe-set links and errors are non-existent links.
- Case Study.: Four geographically separated airport pairs each had 21 common neighbors but were ranked lower by LNB-CN because most common neighbors played negative roles.The pairs were ranked 128, 123, 119, and 114 by LNB-CN, versus within the top 82 by CN; passengers instead transfer through common hubs.
Conclusion. –
The paper proposes local naïve Bayes forms of common-neighbor similarity indices to weight common neighbors according to their differing roles. Across eight real networks and the USAir case study, these forms outperform their original indices, with especially notable gains on hierarchical foodwebs.
- Conclusion.: The proposed local naïve Bayes model assigns different weights to common neighbors according to their roles in link prediction.The model is applied to Common Neighbors, Adamic-Adar, and Resource Allocation indices and their corresponding LNB forms.
- Conclusion.: Across eight real networks, LNB forms outperform their corresponding original Common Neighbors, Adamic-Adar, and Resource Allocation indices.The improvement is described as particularly remarkable on foodwebs with obvious hierarchical structure and few same-level links.
- Conclusion.: In the US air transportation network, LNB methods capture geographically separated airport pairs that have many common neighbors but no direct airlines, improving prediction accuracy.The case study links these patterns to the roles of common neighbors rather than simply their count.