Stacking Models for Nearly Optimal Link Prediction in Complex Networks
  Most real-world networks are incompletely observed. Algorithms that can
accurately predict which links are missing can dramatically speedup the
collection of network data and improve the validity of network models. 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 548 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 via meta-learning to construct
a series of "stacked" models that combine predictors into a single algorithm.
Applied to a broad range of synthetic networks, for which we may analytically
calculate optimal performance, these stacked models achieve optimal or nearly
optimal levels of accuracy. Applied to real-world networks, stacked models are
also superior, but their accuracy varies strongly by domain, suggesting that
link prediction may be fundamentally easier in social networks than in
biological or technological networks. These results indicate that the
state-of-the-art for link prediction comes from combining individual
algorithms, which achieves nearly optimal predictions. We close with a brief
discussion of limitations and opportunities for further improvement of these
results.
