  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.
