Conference Proceedings

CrashSim: An efficient algorithm for computing simrank over static and temporal graphs

M Li, FM Choudhury, R Borovica-Gajic, Z Wang, J Xin, J Li

Proceedings - 2020 IEEE 36th International Conference on Data Engineering (ICDE) | IEEE | Published : 2020

Abstract

SimRank 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 ty..

View full abstract

Grants

Awarded by ARC Linkage Projects


Awarded by National Natural Science Foundation of of China


Awarded by China Postdoctoral Science Foundation


Awarded by Fundamental Research Funds for the Central Universities


Awarded by Open Program of Neusoft Institution of Intelligent Healthcare Technology, Co. Ltd.


Funding Acknowledgements

Mo Li is supported by the Chinese Scholarship Council. This work is partially supported by the ARC Linkage Projects (No. LP180100750), the National Natural Science Foundation of of China (Nos. 61472069 and 61402089), China Postdoctoral Science Foundation (Nos. 2019T120216 and 2018M641705), the Fundamental Research Funds for the Central Universities (N180408019 and N180101028), the CETC Joint Fund, the Open Program of Neusoft Institution of Intelligent Healthcare Technology, Co. Ltd. (No. NRIHTOP1802), and the fund of Acoustics Science and Technology Laboratory.