Nonparametric Link Prediction in Dynamic Networks

Abstract

We propose a non-parametric link prediction algorithm for a sequence of graph snapshots over time. The model predicts links based on the features of its endpoints, as well as those of the local neighborhood around the endpoints. This allows for different types of neighborhoods in a graph, each with its own dynamics (e.g, growing or shrinking communities). We prove the consistency of our estimator, and give a fast implementation based on locality-sensitive hashing. Experiments with simulated as well as five real-world dynamic graphs show that we outperform the state of the art, especially when sharp fluctuations or non-linearities are present.

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

Cited by in corpus (12)

• Scalable Link Prediction in Dynamic Networks via Non-Negative Matrix Factorization
• Rate-optimal graphon estimation
• TREND: TempoRal Event and Node Dynamics for Graph Representation Learning
• Non-parametric Bayesian modeling of complex networks
• Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks
• Bayesian Fused Lasso regression for dynamic binary networks
• Central limit theorems for an Indian buffet model with random weights
• Link Prediction in Graphs with Autoregressive Features
• Detecting Friendship Within Dynamic Online Interaction Networks
• Homophily and Triadic Closure in Evolving Social Networks
• Temporal networks as a modeling framework
• Community detection over a heterogeneous population of non-aligned networks