TY - JOUR
T1 - Evaluating link prediction methods
AU - Yang, Yang
AU - Lichtenwalter, Ryan N.
AU - Chawla, Nitesh V.
N1 - Funding Information:
Research was sponsored in part by the Army Research Laboratory (ARL) and was accomplished under Cooperative Agreement Number W911NF-09-2-0053, and in part from grant #FA9550-12-1-0405 from the U.S. Air Force Office of Scientific Research (AFOSR) and the Defense Advanced Research Projects Agency (DARPA). The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the ARL, AFOSR, DARPA or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation hereon.
Publisher Copyright:
© 2014, Springer-Verlag London.
PY - 2015/12/1
Y1 - 2015/12/1
N2 - 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.
AB - 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.
KW - Class imbalance
KW - Link prediction and Evaluation
KW - Sampling
KW - Temporal effects on link prediction
KW - Threshold curves
UR - http://www.scopus.com/inward/record.url?scp=84944355719&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84944355719&partnerID=8YFLogxK
U2 - 10.1007/s10115-014-0789-0
DO - 10.1007/s10115-014-0789-0
M3 - Article
AN - SCOPUS:84944355719
SN - 0219-1377
VL - 45
SP - 751
EP - 782
JO - Knowledge and Information Systems
JF - Knowledge and Information Systems
IS - 3
ER -