Dynamical SimRank search on time-varying networks

Abstract

SimRank is an appealing pair-wise similarity measure based on graph structure. It iteratively follows the intuition that two nodes are assessed as similar if they are pointed to by similar nodes. Many real graphs are large, and links are constantly subject to minor changes. In this article, we study the efficient dynamical computation of all-pairs SimRanks on time-varying graphs. Existing methods for the dynamical SimRank computation (e.g., L-TSF and READS) mainly focus on top-k search with respect to a given query. For all-pairs dynamical SimRank search, Li et al.'s approach was proposed for this problem. It first factorizes the graph via a singular value decomposition (SVD), and then incrementally maintains such a factorization in response to link updates at the expense of exactness. As a result, all pairs of SimRanks are updated approximately, yielding O(r^4*n^2) time and O(r^2*n^2) memory in a graph with n nodes, where r is the target rank of the low-rank SVD. Our solution to the dynamical computation of SimRank comprises of five ingredients: (1) We first consider edge update that does not accompany new node insertions. We show that the SimRank update ∆S in response to every link update is expressible as a rank-one Sylvester matrix equation. This provides an incremental method requiring O(Kn^2) time and O(n^2) memory in the worst case to update n2pairs of similarities for K iterations. (2) To speed up the computation further, we propose a lossless pruning strategy that captures the "affected areas" of ∆S to eliminate unnecessary retrieval. This reduces the time of the incremental SimRank to O(K(m+|AFF|)), where m is the number of edges in the old graph, and |AFF| (<=n^2) is the size of "affected areas" in ∆S, and in practice, |AFF|<.