Journal
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA
Volume 5, Issue 2, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1921632.1921636
Keywords
Link mining; link prediction; evolution; tensor factorization; CANDECOMP; PARAFAC
Funding
- Sandia National Laboratories
- United States Department of Energy's National Nuclear Security Administration [DE-AC04-94AL85000]
Ask authors/readers for more resources
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 article, 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 article, 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 multiyear 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available