Imperial College London
Portrait Picture

ProfessorJulieMcCann

Faculty of Engineering, Department of Computing

Vice-Dean (Research) for the Faculty of Engineering
 
 
 
//

Contact

 

+44 (0)20 7594 8375j.mccann Website

 
 
//

Assistant

 

Miss Teresa Ng +44 (0)20 7594 8300

 
//

Location

 

260ACE ExtensionSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Yu:2017:10.1007/s00778-017-0488-z,
author = {Yu, W and Lin, X and Zhang, W and McCann, JA},
doi = {10.1007/s00778-017-0488-z},
journal = {VLDB JOURNAL},
pages = {79--104},
title = {Dynamical SimRank search on time-varying networks},
url = {http://dx.doi.org/10.1007/s00778-017-0488-z},
volume = {27},
year = {2017}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - 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
AU  - Yu,W
AU  - Lin,X
AU  - Zhang,W
AU  - McCann,JA
DO  - 10.1007/s00778-017-0488-z
EP  - 104
PY  - 2017///
SN  - 1066-8888
SP  - 79
TI  - Dynamical SimRank search on time-varying networks
T2  - VLDB JOURNAL
UR  - http://dx.doi.org/10.1007/s00778-017-0488-z
UR  - http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000424027200004&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
UR  - http://hdl.handle.net/10044/1/59793
VL  - 27
ER  -
Download