Spectral evolution in dynamic networks
We introduce and study the spectral evolution model, which characterizes the growth of large networks in terms of the eigenvalue decomposition of their adjacency matrices: In large networks, changes over time result in a change of a graphs spectrum, leaving the eigenvectors unchanged. We validate this hypothesis for several large social, collaboration, rating, citation, and communication networks. Following these observations, we introduce two link prediction algorithms based on the learning of the changes to a networks spectrum. These new link prediction methods generalize several common graph kernels that can be expressed as spectral transformations. The first method is based on reducing the link prediction problem to a one-dimensional curve-fitting problem which can be solved efficiently. The second algorithm extrapolates a networks spectrum to predict links. Both algorithms are evaluated on fifteen network datasets for which edge creation times are known.
link prediction graph kernels spectral graph theory network dynamics