Robustness of Link-prediction Algorithm Based on Similarity and Application to Biological Networks

Liang Wang, Ke Hu, Yi TangarXiv 2013 · arXiv

Abstract

In the study of complex networks, link prediction is essential for uncovering hidden connections. However, real-world data is often noisy, containing both false positives and negatives. This paper investigates the robustness of similarity-based link prediction algorithms—Common Neighbors (CN), Adamic-Adar (AA), Resource Allocation (RA), and Local Path (LP)—against varying levels of noise. The authors find that the LP index generally exhibits superior resilience in small-world networks. Furthermore, they propose a novel link-weighting scheme based on local structural reliability, which significantly enhances prediction accuracy and robustness, particularly in biological networks such as protein-protein interaction and food web models.

Introduction

Complex networks, ranging from cellular protein interactions to global social ties, are frequently mapped with incomplete or erroneous data. Link prediction algorithms act as cartographers, estimating the likelihood of missing connections based on observed topology. While accuracy is a standard benchmark, the robustness of these algorithms—their ability to maintain performance despite noise—is less understood. This study addresses this gap by evaluating classic algorithms under simulated noise and introducing a weighting mechanism to bolster resilience.

Methodology and Robustness Metrics

The research evaluates four primary similarity-based indices: Common Neighbors (CN), Adamic-Adar (AA), Resource Allocation (RA), and the Local Path (LP) index. To quantify resilience, the authors define a robustness metric ($r$) as the ratio of the algorithm's Area Under the Curve (AUC) on a noisy network to its AUC on the original, clean network. Noise is introduced by randomly swapping a fraction ($p$) of existing links with non-existent ones.

Robustness (r) of four link prediction algorithms across eight diverse networks as noise (p) increases.

Key Findings on Algorithm Resilience

The analysis reveals that the Local Path (LP) index is the most robust in small-world networks. By considering paths of length three, LP maintains a "wider horizon" that is less susceptible to local perturbations than indices like CN, which rely solely on immediate shared neighbors. However, this advantage disappears in sparse, non-small-world structures like the Power Grid, where LP performance degrades rapidly.

Network topology plays a critical role in buffering noise. Networks characterized by high average degree and significant degree heterogeneity (the presence of "hubs") tend to be more naturally robust, as the structural redundancy helps cancel out the influence of erroneous links.

To combat the inherent noise in biological datasets, such as Protein-Protein Interaction (PPI) networks, the authors propose transforming unweighted networks into weighted ones. They utilize the "link clustering coefficient"—a measure of how many common neighbors two connected nodes share—as a proxy for link reliability. This weighting scheme prioritizes structurally "supported" links, effectively denoising the input data.

Comparison of AUC performance between un-weighted and weighted versions of CN and LP algorithms across various datasets.

Results and Application

The proposed weighting scheme significantly improves performance in biological contexts. In the South Florida Food Web (FW) network, the AUC increased from 0.610 to 0.680. Similar gains were observed in social networks like Political Blogs, where structural reliability proved to be a powerful predictor. Generally, robustness remains high until noise levels reach approximately 40%, after which performance declines linearly.

Conclusion

While the Local Path index offers superior baseline robustness for most complex networks, the introduction of structural weighting provides a significant boost in accuracy for noisy biological data. Future research may explore iterative weighting processes to further refine network stability and extend these findings to even larger, multi-layered datasets.

Summary updated

BibTeX
@misc{wang2013robustness,
  author = {Liang Wang and Ke Hu and Yi Tang},
  title = {{Robustness of Link-prediction Algorithm Based on Similarity and Application to Biological Networks}},
  year = {2013},
  eprint = {1302.5878},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1302.5878},
}
Figure