Link Prediction on Evolving Data 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 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.

Publication
In ICDMW’09: Proceedings of the 2009 IEEE International Conference on Data Mining Workshops
Date
Citation
E. Acar, D. M. Dunlavy, T. G. Kolda. Link Prediction on Evolving Data using Matrix and Tensor Factorizations. In ICDMW’09: Proceedings of the 2009 IEEE International Conference on Data Mining Workshops, Miami, FL (2009-12-06), pp. 262-269, 2009. https://doi.org/10.1109/ICDMW.2009.54

Keywords

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

Comments

Presented at LDMTA’09: ICDM’09 Workshop on Large Scale Data Mining Theory and Applications.

BibTeX

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