  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.
