Abstract

Most real-world networks are incompletely observed. Algorithms that can accurately predict which links are missing can dramatically speed up network data collection and improve network model validation. Many algorithms now exist for predicting missing links, given a partially observed network, but it has remained unknown whether a single best predictor exists, how link predictability varies across methods and networks from different domains, and how close to optimality current methods are. We answer these questions by systematically evaluating 203 individual link predictor algorithms, representing three popular families of methods, applied to a large corpus of 550 structurally diverse networks from six scientific domains. We first show that individual algorithms exhibit a broad diversity of prediction errors, such that no one predictor or family is best, or worst, across all realistic inputs. We then exploit this diversity …

Date

September 22, 2020

Authors

Amir Ghasemian, Homa Hosseinmardi, Aram Galstyan, Edoardo M Airoldi, Aaron Clauset

Journal

Proceedings of the National Academy of Sciences

Volume

117

Issue

38

Pages

23393-23400

Publisher

National Academy of Sciences