Evaluating Link Prediction Methods

Abstract

Link prediction is a popular research area with important applications in a variety of disciplines, including biology, social science, security, and medicine. The fundamental requirement of link prediction is the accurate and effective prediction of new links in networks. While there are many different methods proposed for link prediction, we argue that the practical performance potential of these methods is often unknown because of challenges in the evaluation of link prediction, which impact the reliability and reproducibility of results. We describe these challenges, provide theoretical proofs and empirical examples demonstrating how current methods lead to questionable conclusions, show how the fallacy of these conclusions is illuminated by methods we propose, and develop recommendations for consistent, standard, and applicable evaluation metrics. We also recommend the use of precision-recall threshold curves and associated areas in lieu of receiver operating characteristic curves due to complications that arise from extreme imbalance in the link prediction classification problem.

References in corpus (4)

• Power-law distributions in empirical data
• Hierarchical structure and the prediction of missing links in networks
• Predicting Positive and Negative Links in Online Social Networks
• Supervised Random Walks: Predicting and Recommending Links in Social Networks

Cited by in corpus (7)

• E-LSTM-D: A Deep Learning Framework for Dynamic Network Link Prediction
• A supervised approach to time scale detection in dynamic networks
• Limitations and Alternatives for the Evaluation of Large-scale Link Prediction
• Automatic Discovery of Families of Network Generative Processes
• Applications of Multi-view Learning Approaches for Software Comprehension
• SNE: Signed Network Embedding
• Hierarchical Hyperlink Prediction for the WWW