Link prediction accuracy on real-world networks under non-uniform missing-edge patterns.

Area of Science:

• Network Science
• Data Mining
• Machine Learning

Background:

• Real-world network datasets often have missing edges due to data collection biases.
• Uniform missing data is a common, yet often unrealistic, assumption for evaluating link prediction algorithms.

Purpose of the Study:

• To investigate how different non-uniform missing-edge patterns impact link prediction accuracy.
• To compare the performance of various link prediction algorithms under diverse missing data scenarios.
• To provide guidance for selecting appropriate link prediction methods based on network data characteristics.

Main Methods:

• Analysis of 9 link prediction algorithms from 4 families.
• Evaluation across 20 distinct missing-edge patterns, categorized into 5 groups.
• A comparative simulation study using 250 real-world network datasets from 6 domains.

Main Results:

• Significant variations in link prediction algorithm performance were observed across different missing-edge patterns.
• The study highlights the substantial impact of non-uniform missing data on evaluation outcomes.
• Algorithm performance is highly dependent on the specific characteristics of the missing data.

Conclusions:

• The assumption of uniform missing data can lead to misleading evaluations of link prediction methods.
• Researchers should consider the data collection process and resulting missing-edge patterns when selecting algorithms.
• This work offers a framework for choosing link prediction tools tailored to real-world network data.