Temporal Link Prediction using Matrix and Tensor Factorizations

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.

Publication
ACM Transactions on Knowledge Discovery from Data
Date
Citation
D. M. Dunlavy, T. G. Kolda, E. Acar. Temporal Link Prediction using Matrix and Tensor Factorizations. ACM Transactions on Knowledge Discovery from Data (Special Issue on Large-scale Data Mining: Theory and Applications), Vol. 5, No. 2, pp. 10 (27 pages), 2011. https://doi.org/10.1145/1921632.1921636

Keywords

link mining, link prediction, evolution, tensor factorization, CANDECOMP, PARAFAC

BibTeX

@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},
}