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 time periods 1 through T, can we predict the links in time period T +1? Specifically, we look at bipartite graphs changing over time and consider matrix- and tensorbased methods for predicting 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 threedimensional structure of temporal link data. Through several numerical experiments, we demonstrate that both matrixand tensor-based techniques are effective for temporal link prediction despite the inherent difficulty of the problem.
link mining, link prediction, evolution, tensor factorization, CANDECOMP, PARAFAC
Presented at LDMTA’09: ICDM’09 Workshop on Large Scale Data Mining Theory and Applications.
@inproceedings{AcDuKo09,
author = {Evrim Acar and Daniel M. Dunlavy and Tamara G. Kolda},
title = {Link Prediction on Evolving Data using Matrix and Tensor Factorizations},
booktitle = {ICDMW'09: Proceedings of the 2009 IEEE International Conference on Data Mining Workshops},
venue = {Miami, FL},
eventdate = {2009-12-06},
pages = {262--269},
month = {December},
year = {2009},
doi = {10.1109/ICDMW.2009.54},
}