Abstract
Link prediction is a fundamental task in network science, typically evaluated by randomly splitting edges into training and test sets. However, real-world network data is often collected through biased sampling methods like Breadth-First Search (BFS) rather than uniform observation. This paper investigates how different sampling strategies affect the performance of ten local information-based link prediction algorithms across nine diverse datasets. The results demonstrate that standard random evaluation overestimates prediction accuracy, and the optimal algorithm choice is contingent upon the underlying sampling process.
Introduction
In network science, link prediction aims to identify missing or future connections within a network, with applications ranging from social network friend recommendations to identifying protein-protein interactions. The standard evaluation paradigm involves taking a complete network, randomly hiding a percentage of edges (the "probe" or test set), and assessing an algorithm's ability to recover them using the remaining training set.
However, this "Pure Random" (PR) split rarely reflects how data is acquired in practice. Most large-scale networks are explored via web crawlers or APIs that follow specific paths, introducing inherent biases toward highly connected nodes (hubs). This study addresses a critical gap: Does evaluating link prediction on randomly split data provide a false sense of accuracy, and how do these algorithms perform when the data is subject to realistic, biased sampling?
Methodology
Link Prediction Algorithms
The authors evaluated ten lightweight, local information-based algorithms. These methods score potential links based on neighborhood overlap, including:
- Common Neighbors (CN)
- Adamic-Adar (AA)
- Resource Allocation (RA)
- Salton Index (SAI)
- Jaccard Index (JI)
- Preferential Attachment (PA)
Sampling Strategies
To simulate realistic data collection, the researchers generated training and test sets using five distinct sampling strategies:
- Pure Random (PR): The idealized baseline used in most literature.
- Breadth-First Search (BFS): A common crawling method that biases toward hubs.
- Metropolis-Hastings Random Walk (MHRW): A modified walk designed to sample nodes uniformly.
- Frontier Sampling (FS): A technique utilizing multiple dependent random walks.
- Forest Fire (FF): A probabilistic method that mimics the way networks evolve and spread.
Evaluation Framework
The experiments were conducted on the giant connected components of nine diverse real-world networks, including Netscience (co-authorships), Power (electrical grid), Yeast (protein interactions), and Caltech (Facebook friendships). Accuracy was measured using the Area Under the Curve (AUC), representing the probability that a missing link is correctly ranked higher than a nonexistent one.
Key Insights
The "Random" Illusion
Across all datasets, prediction algorithms performed at their peak under Pure Random (PR) sampling. Because real-world data collection is rarely purely random, historical benchmarks have likely significantly overestimated the real-world efficacy of these algorithms. When moving from PR to biased methods like BFS or Forest Fire, AUC scores dropped consistently. For instance, on the Dimes dataset, the CN algorithm’s AUC fell from 0.87 (PR) to 0.73 (BFS) and 0.69 (FF).
Why Biased Sampling Degrades Performance
The study found that sampling methods like BFS and Forest Fire tend to capture the dense cores of networks for the training set, leaving edges with very few common neighbors in the test set. Since local prediction algorithms rely heavily on shared neighbors to identify potential links, they struggle to predict these relatively isolated missing links.
Algorithm Sensitivity and Selection
The research reveals that there is no single "best" algorithm; the optimal choice depends on the sampling method:
- Resource Allocation (RA) is generally superior for random or uniform sampling (PR, MHRW, FS).
- Salton Index (SAI) performs better on datasets gathered via biased crawling (BFS, FF).
- Preferential Attachment (PA), which relies on node degrees, performed poorly across the board and suffered catastrophic failures under BFS and FS compared to random sampling.
Conclusion
This study highlights the necessity of accounting for data collection methods in network analysis. The bias introduced by sampling significantly alters the difficulty of the link prediction task and shifts the relative performance of different metrics. Future research and practical applications should prioritize sampling-aware algorithm selection: if a network was crawled using BFS, engineers should favor metrics like the Salton Index over standard benchmarks like Resource Allocation. While this study focused on local methods, it sets the stage for investigating how global and machine-learning-based approaches handle similar sampling biases.
Summary updated