  Link prediction has aroused extensive attention since it can both discover
hidden connections and predict future links in the networks. Many unsupervised
link prediction algorithms have been proposed to find these links in a variety
of networks. However, there is an evaluation conundrum in unsupervised link
prediction. Unobserved links heavily outnumber observed links in large
networks, so it is unrealistic to quantify the existence likelihood of all
unobserved links to evaluate these algorithms. In this paper, we propose a new
evaluation paradigm that is sampling unobserved links to address this problem.
First, we demonstrate that the proposed paradigm is feasible in theory. Then,
we perform extensive evaluation experiments in real-world networks of different
contexts and sizes. The results show that the performance of similarity-based
link prediction algorithms is highly stable even at a low sampling ratio in
large networks, and the evaluation time degradation caused by sampling is
striking. Our findings have broad implications for link prediction.
