Published on Fri May 21 2010

Temporal Link Prediction using Matrix and Tensor Factorizations

Daniel M. Dunlavy, Tamara G. Kolda, Evrim Acar

In this paper, we consider the problem of temporal link prediction. We present a weight-based method for collapsing multi-year data into a single matrix. We show how the well-known Katz method for link prediction can be extended to bipartite graphs.

0
0
0
Abstract

The data in many disciplines such as social networks, web analysis, etc. is link-based, and the link structure can be exploited for many different data mining tasks. In this paper, we consider the problem of temporal link prediction: Given link data for times 1 through T, can we predict the links at time T+1? If our data has underlying periodic structure, can we predict out even further in time, i.e., links at time T+2, T+3, etc.? In this paper, we consider bipartite graphs that evolve over time and consider matrix- and tensor-based methods for predicting future links. We present a weight-based method for collapsing multi-year data into a single matrix. We show how the well-known Katz method for link prediction can be extended to bipartite graphs and, moreover, approximated in a scalable way using a truncated singular value decomposition. Using a CANDECOMP/PARAFAC tensor decomposition of the data, we illustrate the usefulness of exploiting the natural three-dimensional structure of temporal link data. Through several numerical experiments, we demonstrate that both matrix- and tensor-based techniques are effective for temporal link prediction despite the inherent difficulty of the problem. Additionally, we show that tensor-based techniques are particularly effective for temporal data with varying periodic patterns.

Thu Nov 13 2014
Artificial Intelligence
Scalable Link Prediction in Dynamic Networks via Non-Negative Matrix Factorization
We propose a scalable temporal latent space model for link prediction in dynamic social networks. The goal is to predict links over time based on a sequence of previous graph snapshots. The model assumes that each user lies in an unobserved latent space and interactions are more likely to form between similar users.
0
0
0
Sat Jun 06 2020
Neural Networks
Link Prediction for Temporally Consistent Networks
In the current link prediction approaches, only homogeneous networks are considered. We propose a time-parameterized matrix to represent dynamically evolving networks. We also propose a predictive influence index as a measure of a node's boosting or diminishing predictive influence.
0
0
0
Mon Apr 15 2013
Machine Learning
Link Prediction with Social Vector Clocks
State-of-the-art link prediction utilizes combinations of complex features from network panel data. We here show that computationally less expensive features can achieve the same performance in the common scenario in which the data is available as a sequence of interactions.
0
0
0
Tue Sep 06 2011
Machine Learning
Nonparametric Link Prediction in Large Scale Dynamic Networks
We propose a nonparametric approach to link prediction in large-scale dynamic networks. Our model uses graph-based features of pairs of nodes as well as neighborhoods to predict whether those nodes will be linked at each time step. The model allows for different types of evolution in different parts of the
0
0
0
Wed Jun 22 2016
Machine Learning
Link Prediction via Matrix Completion
Link prediction is a fundamental issue to understand the mechanisms by which new links are added to networks. We introduce the method of robust principal component analysis (robust PCA) into link prediction.
0
0
0
Thu Aug 30 2012
Machine Learning
Link Prediction via Generalized Coupled Tensor Factorisation
This study deals with the missing link prediction problem: the problem of predicting the existence of missing connections between entities of interest. We address link prediction using coupled analysis of relational datasets.
0
0
0