File(s) under permanent embargo
CrashSim: an efficient algorithm for computing SimRank over static and temporal graphs
conference contribution
posted on 2020-01-01, 00:00 authored by Mo Li, Farhana M Choudhury, Renata Borovica-Gajic, Zhiqiong Wang, Junchang Xin, Jianxin LiJianxin LiSimRank is a significant metric to measure the similarity of nodes in graph data analysis. The problem of SimRank computation has been studied extensively, however there is no existing work that can provide one unified algorithm to support the SimRank computation both on static and temporal graphs. In this work, we first propose CrashSim, an index-free algorithm for single-source SimRank computation in static graphs. CrashSim can provide provable approximation guarantees for the computational results in an efficient way. In addition, as the reallife graphs are often represented as temporal graphs, CrashSim enables efficient computation of SimRank in temporal graphs. We formally define two typical SimRank queries in temporal graphs, and then solve them by developing an efficient algorithm based on CrashSim, called CrashSim-T. From the extensive experimental evaluation using five real-life and synthetic datasets, it can be seen that the CrashSim algorithm and CrashSim-T algorithm substantially improve the efficiency of the state-of-the-art SimRank algorithms by about 30%, while achieving the precision of the result set with about 97%.
History
Event
Data Engineering. International Conference (36th : 2020 : Dallas, Tex.)Pagination
1141 - 1152Publisher
IEEELocation
Dallas, Tex.Place of publication
Piscataway, N.J.Publisher DOI
Start date
2020-04-20End date
2020-04-24ISSN
1063-6382eISSN
2375-026XISBN-13
9781728129037Language
engPublication classification
E1 Full written paper - refereedEditor/Contributor(s)
UnknownTitle of proceedings
ICDE 2020 : Proceedings of the IEEE 36th International Conference on Data EngineeringUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC