The Library
Fast exact CoSimRank search on evolving and static graphs
Tools
Tools
Tools
Yu, Weiren and Wang, Fan (2018) Fast exact CoSimRank search on evolving and static graphs. In: WWW '18, Lyon France, Apr 2018. Published in: WWW '18: Proceedings of the 2018 World Wide Web Conference pp. 599-608. ISBN 9781450356398. doi:10.1145/3178876.3186126
|
PDF
WRAP-Fast-exact-CoSimRank-evolving-static-graphs-Yu-2018.pdf - Accepted Version - Requires a PDF viewer. Download (796Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/3178876.3186126
Abstract
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.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics T Technology > TK Electrical engineering. Electronics Nuclear engineering |
||||||
| Divisions: | Faculty of Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Web application, Similarity (Geometry), Topology, Graph theory | ||||||
| Journal or Publication Title: | WWW '18: Proceedings of the 2018 World Wide Web Conference | ||||||
| Publisher: | ACM | ||||||
| ISBN: | 9781450356398 | ||||||
| Book Title: | Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18 | ||||||
| Official Date: | April 2018 | ||||||
| Dates: |
|
||||||
| Page Range: | pp. 599-608 | ||||||
| DOI: | 10.1145/3178876.3186126 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Publisher Statement: | © Author | ACM 2018. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in WWW '18: Proceedings of the 2018 World Wide Web Conference, http://dx.doi.org/10.1145/3178876.3186126 | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | WWW '18 | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Lyon France | ||||||
| Date(s) of Event: | Apr 2018 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
