|
Abstract:
|
Predicting missing links in networks is a fundamental task in network analysis and modeling. Here, I will describe a novel meta-learning solution to this problem, which makes predictions that appear to be nearly optimal, by learning to combine three popular classes of prediction methods. We evaluate 203 methods individually and in stacked generalization on (i) synthetic data with known structure, for which we analytically calculate the optimal link prediction performance, and (ii) a large corpus of 548 structurally diverse networks from social, biological, technological, information, economic, and transportation domains. Across settings, supervised stacking nearly always performs best and produces nearly-optimal performance on synthetic networks. Moreover, we show that accuracy saturates quickly, and good predictions typically require only a handful of individual predictors. Applied to real data, we quantify the utility of each method on different types of networks, and then show that the difficulty of predicting missing links varies considerably across domains: it is easiest in social networks and hardest in technological networks. I'll close with forward-looking comments.
|
