Stacking models for nearly optimal link prediction in complex networks

Area of Science:

• Network science
• Data science
• Computational science

Background:

• Real-world networks are often incomplete, necessitating accurate link prediction.
• Existing link prediction algorithms vary in performance, with no clear best method identified across different network types.

Purpose of the Study:

• To systematically evaluate the performance of numerous link prediction algorithms.
• To determine if a universally superior predictor exists and how performance varies across domains.
• To develop improved link prediction strategies by combining existing methods.

Main Methods:

• Evaluated 203 individual link predictor algorithms from three families on 550 diverse networks.
• Employed network-based metalearning to create "stacked" models combining multiple predictors.
• Assessed performance on both synthetic and real-world network datasets.

Main Results:

• Individual algorithms showed diverse prediction errors; no single method was consistently best.
• Stacked models achieved optimal or near-optimal accuracy on synthetic networks.
• Stacked models outperformed individual predictors on real-world networks, with accuracy varying by domain (e.g., easier for social networks).

Conclusions:

• Combining diverse link prediction algorithms via metalearning represents the state-of-the-art.
• Stacked models offer significant improvements for incomplete network analysis.
• Domain-specific characteristics influence the fundamental difficulty of link prediction.