Performance measures for link prediction algorithms, estimated from 50 repetitions of cross-validation with 10% of edges removed from the network.

We divide our algorithms into three categories: “Elementary” denotes algorithms based on node degrees or simple similarity measures such as counts of common neighbors between node pairs; “Machine learning” denotes methods such as matrix factorization, Bayesian, and deep-learning methods; “SBM” denotes network-based methods that make use of the stochastic block model. The performance measures we use are the area under the ROC curve (AUROC), the area under the precision/recall curve (AUPR), area under the precision/recall curve normalized by prevalence, and precision over the top 100 predictions. Numbers in parentheses indicate standard errors on the trailing digits. Numbers in bold indicate the best performers. Running time is for a single run of each algorithm.