Fast Exact CoSimRank Search on Evolving and Static Graphs


In real Web applications, CoSimRank has been proposed as a powerful measure of node-pair similarity based on graph topologies. However, existing work on CoSimRank is restricted to static graphs. When the graph is updated with new edges arriving over time, it is cost-inhibitive to recompute all CoSimRank scores from scratch, which is impractical. In this study, we propose a fast dynamic scheme, \DCoSim for accurate CoSimRank search over evolving graphs. Based on \DCoSim, we also propose a fast scheme, \FCoSim, that greatly accelerates CoSimRank search over static graphs. Our theoretical analysis shows that \DCoSim and \FCoSim guarantee the exactness of CoSimRank scores. On the static graph G, to efficiently retrieve CoSimRank scores $\mathbfS $, \FCoSim is based on three ideas: (i) It first finds a "spanning polytree»» T over G. (ii) On T, a fast algorithm is designed to compute the CoSimRank scores $\mathbfS (T)$ over the "spanning polytree»» T. (iii) On G, \DCoSim is employed to compute the changes of $\mathbfS (T)$ in response to the delta graph $(G øminus T)$. Experimental evaluations verify the superiority of \DCoSim over evolving graphs, and the fast speedup of \FCoSim on large-scale static graphs against its competitors, without any loss of accuracy.

Publication DOI:
Divisions: College of Engineering & Physical Sciences
College of Engineering & Physical Sciences > Systems analytics research institute (SARI)
Additional Information: Copyright:ACM
Event Title: the 2018 World Wide Web Conference
Event Type: Other
Event Location: Lyon, France
Event Dates: 2018-04-23 - 2018-04-27
ISBN: 978-1-4503-5639-8, 978-1-4503-5639-8
Last Modified: 17 Jun 2024 08:32
Date Deposited: 25 Apr 2018 09:46
Full Text Link:
Related URLs: https://dl.acm. ... 3178876.3186126 (Publisher URL)
PURE Output Type: Conference contribution
Published Date: 2018-04-10
Accepted Date: 2018-02-18
Authors: Yu, Weiren (ORCID Profile 0000-0002-1082-9475)
Wang, Fan



Version: Accepted Version

| Preview

Export / Share Citation


Additional statistics for this record