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.
link mining, link prediction, evolution, tensor factorization, CANDECOMP, PARAFAC
@article{DuKoAc11,
author = {Daniel M. Dunlavy and Tamara G. Kolda and Evrim Acar},
title = {Temporal Link Prediction using Matrix and Tensor Factorizations},
journal = {ACM Transactions on Knowledge Discovery from Data},
issuetitle = {Special Issue on Large-scale Data Mining: Theory and Applications},
volume = {5},
number = {2},
pages = {10 (27 pages)},
month = {February},
year = {2011},
doi = {10.1145/1921632.1921636},
}