Dynamical SimRank search on time-varying networks - Yu,W; Lin,X; Zhang,W; McCann,JA (VLDB JOURNAL, 2017)
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., LTSF (Shao et al. in PVLDB 8(8):838–849, 2015) and READS (Zhang et al. in PVLDB 10(5):601–612, 2017)] mainly focus on top-k search with respect to a given query. For all-pairs dynamical SimRank search, Li et al.’s approach (Li et al. in EDBT, 2010) 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(r4n2) time and O(r2n2) 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(Kn2) time and O(n2) memory in the worst case to update n2 pairs 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| (≤n2) is the size of “affected areas” in ΔΔS, and in practice, |AFF|n2. (3) We also consider edge updates that accomp