SimRank calculations for large temporal graphs

MIAO Zhuang; YUAN Ye; QIAO Baiyou; WANG Yishu; MA Yuliang; WANG Guoren

doi:10.16511/j.cnki.qhdxxb.2018.26.050

PDF(1026 KB)

Journal of Tsinghua University(Science and Technology) ›› 2018, Vol. 58 ›› Issue (12) : 1066-1071. DOI: 10.16511/j.cnki.qhdxxb.2018.26.050

COMPUTER SCIENCE AND TECHNOLOGY

SimRank calculations for large temporal graphs

{{article.zuoZhe_EN}}

Author information +

History +

Abstract

Similarity calculations have many real life applications. The research on similarity calculations have mainly been focused on static graphs with many similarity calculation models based on SimRank. In real life, many systems, such as communication networks, are modeled by temporal graphs. However, the traditional SimRank algorithm cannot be implemented in temporal graphs. Therefore, this study analyzes the similarity calculation problem for large temporal graphs. A temporal-aware SimRank (TaSimRank) algorithm was developed to compute the node similarity through an efficient iterative method based on the topological structure and time constraints of the graph. An approximate algorithm is then used to implement the similarity calculations using a tree-based index built by a random walk and the Monte Carlo method. The algorithm balances the calculational time and efficiency. Tests on real temporal graphs demonstrate the effectiveness and extensibility of these approaches.

Key words

temporal graph / similarity / random walk

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

MIAO Zhuang, YUAN Ye, QIAO Baiyou, WANG Yishu, MA Yuliang, WANG Guoren. SimRank calculations for large temporal graphs[J]. Journal of Tsinghua University(Science and Technology). 2018, 58(12): 1066-1071 https://doi.org/10.16511/j.cnki.qhdxxb.2018.26.050

References

[1] SALTON G, MCGILL M J. Introduction to modern information retrieval[J]. McGraw-Hill, 1983, 55(4):239-240.
[2] HERLOCKER J L, KONSTAN J A, TERVEEN L G, et al. Evaluating collaborative filtering recommender systems[J]. ACM Transactions on Information Systems, 2004, 22(1):5-53.
[3] HOLME P, SARAMAKI J. Temporal networks[J]. Physics Reports, 2012, 519(3):97-125.
[4] WU H H, CHENG J, HUANG S L, et al. Path problems in temporal graphs[J]. Proceedings of the VLDB Endowment, 2014, 7(9):721-732.
[5] WU H, HUANG Y, CHENG J, et al. Reachability and time-based path queries in temporal graphs[C]//IEEE, International Conference on Data Engineering. Helsinki, Finland:IEEE, 2016:145-156.
[6] JEH G, WIDOM J. SimRank:A measure of structural-context similarity[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Edmonton, Alberta, Canada:ACM, 2002:538-543.
[7] YU W R, LIN X M, ZHANG W J. Towards efficient SimRank computation on large networks[C]//Proceedings of 2013 IEEE International Conference on Data Engineering. Brisbane, Australia:IEEE, 2013:601-612.
[8] LIZORKIN D, VELIKHOV P, GRINEV M, et al. Accuracy estimate and optimization techniques for SimRank computation[J]. The VLDB Journal, 2010, 19(1):45-66.
[9] LI C P, HAN J W, HE G M, et al. Fast computation of SimRank for static and dynamic information networks[C]//Proceedings of the 13th International Conference on Extending Database Technology. Lausanne, Switzerland:ACM, 2010:465-476.
[10] YU W R, LIN X M, ZHANG W J. Fast incremental SimRank on link-evolving graphs[C]//Proceedings of IEEE International Conference on Data Engineering. Chicago, USA:IEEE, 2014:304-315.
[11] SHAO Y X, CUI B, CHEN L, et al. An efficient similarity search framework for SimRank over large dynamic graphs[J]. Proceedings of the VLDB Endowment, 2015, 8(8):838-849.
[12] LI R Q, ZHAO X, SHANG H C, et al. Fast top-k similarity join for SimRank[J]. Information Sciences, 2017, 381:1-19.
[13] JIANG M H, FU A W C, WONG R C W. READS:A random walk approach for efficient and accurate dynamic SimRank[J]. Proceedings of the VLDB Endowment, 2017, 10(9):937-948.
[14] FOGARAS D, RÁCZ B. Scaling link-based similarity search[C]//Proceedings of the 14th International Conference on World Wide Web. Chiba, Japan:ACM, 2005:641-650.
[15] JOHNSON R W. An introduction to the bootstrap[J]. Teaching Statistics, 2001, 23(2):49-54.