Link prediction in dynamic networks using random dot product graphs
arXiv:1912.10419 · doi:10.1007/s10618-021-00784-2
Abstract
The problem of predicting links in large networks is an important task in a variety of practical applications, including social sciences, biology and computer security. In this paper, statistical techniques for link prediction based on the popular random dot product graph model are carefully presented, analysed and extended to dynamic settings. Motivated by a practical application in cyber-security, this paper demonstrates that random dot product graphs not only represent a powerful tool for inferring differences between multiple networks, but are also efficient for prediction purposes and for understanding the temporal evolution of the network. The probabilities of links are obtained by fusing information at two stages: spectral methods provide estimates of latent positions for each node, and time series models are used to capture temporal dynamics. In this way, traditional link prediction methods, usually based on decompositions of the entire network adjacency matrix, are extended using temporal information. The methods presented in this article are applied to a number of simulated and real-world graphs, showing promising results.
References in corpus (32)
- Adam: A Method for Stochastic Optimization
- DeepWalk: Online Learning of Social Representations
- Semi-Supervised Classification with Graph Convolutional Networks
- Inductive Representation Learning on Large Graphs
- Link Prediction in Complex Networks: A Survey
- Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec
- Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks
- A Separable Model for Dynamic Networks
- dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning
- Temporal Link Prediction using Matrix and Tensor Factorizations
- DynGEM: Deep Embedding Method for Dynamic Graphs
- Scalable Link Prediction in Dynamic Networks via Non-Negative Matrix Factorization
- Dynamic stochastic blockmodels for time-evolving social networks
- Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds
- Latent Space Models for Dynamic Networks
- A state-space mixed membership blockmodel for dynamic network tomography
- Watch Your Step: Learning Node Embeddings via Graph Attention
- Statistical inference on random dot product graphs: a survey
- Nonparametric Bayes dynamic modeling of relational data
- Dynamic Poisson Factorization
- Bayesian Inference and Testing of Group Differences in Brain Networks
- A Comparative Study for Unsupervised Network Representation Learning
- Joint Embedding of Graphs
- Network classification with applications to brain connectomics
- Inference for multiple heterogeneous networks with a common invariant subspace
- A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference
- Semiparametric spectral modeling of the Drosophila connectome
- DynamicGEM: A Library for Dynamic Graph Embedding Methods
- The Multiple Random Dot Product Graph Model
- The multilayer random dot product graph
- A statistical interpretation of spectral embedding: the generalised random dot product graph
- Graph-aware Modeling of Brain Connectivity Networks