Link Prediction on Evolving Data Using Matrix and Tensor Factorizations
Evrim Acar, Daniel Dunlavy, Tamara G. Kolda · IEEE ... International Conference on Data Mining workshops · 2009
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 tensor-based 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 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.
Cited by 149 works. doi:10.1109/icdmw.2009.54
Authors
References
- Matrix Factorization Techniques for Recommender Systems
- Analysis of Individual Differences in Multidimensional Scaling Via an N-way Generalization of “Eckart-Young” Decomposition
- Lessons from the Netflix prize challenge
- Tensor Decompositions and Applications
- A New Status Index Derived from Sociometric Analysis
- Foundations of the PARAFAC procedure: Models and conditions for an "explanatory" multi-model factor analysis
- The Analysis of Time Series
- Using latent semantic analysis to improve access to textual information
- Numerical Methods for Large Eigenvalue Problems
- The link‐prediction problem for social networks