Evaluating Link Prediction Accuracy on Dynamic Networks with Added and
  Removed Edges
  The task of predicting future relationships in a social network, known as
link prediction, has been studied extensively in the literature. Many link
prediction methods have been proposed, ranging from common neighbors to
probabilistic models. Recent work by Yang et al. has highlighted several
challenges in evaluating link prediction accuracy. In dynamic networks where
edges are both added and removed over time, the link prediction problem is more
complex and involves predicting both newly added and newly removed edges. This
results in new challenges in the evaluation of dynamic link prediction methods,
and the recommendations provided by Yang et al. are no longer applicable,
because they do not address edge removal. In this paper, we investigate several
metrics currently used for evaluating accuracies of dynamic link prediction
methods and demonstrate why they can be misleading in many cases. We provide
several recommendations on evaluating dynamic link prediction accuracy,
including separation into two categories of evaluation. Finally we propose a
unified metric to characterize link prediction accuracy effectively using a
single number.
