|
|
- 2018
面向大规模时序图SimRank的计算方法
|
Abstract:
顶点相似度计算在现实生活中具有广泛的应用。当前对相似性计算的研究工作主要集中于静态图上，并且大多相似性计算模型是基于SimRank算法提出的。而现实中的许多场景，需采用时序图进行建模。当前针对静态图的大量SimRank的计算方法无法在时序图中实现，因此该文对大规模时序图中的SimRank计算开展详细研究，并提出一种时序关联的SimRank计算方法（temporal-aware SimRank，TaSimRank）。TaSimRank根据图的拓扑结构和时间约束通过高效的迭代方法计算SimRank。同时，该文提出一种近似算法，通过随机游走方法建立树形索引，使用Monte Carlo方法近似计算顶点的相似度，取得时间和效率的平衡。最后，通过大量真实实验验证了提出算法的有效性和可扩展性。
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.
| [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] | 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. |
| [5] | 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. |
| [6] | LI R Q, ZHAO X, SHANG H C, et al. Fast top-k similarity join for SimRank[J]. Information Sciences, 2017, 381:1-19. |
| [7] | 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. |
| [8] | 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. |
| [9] | JOHNSON R W. An introduction to the bootstrap[J]. Teaching Statistics, 2001, 23(2):49-54. |
| [10] | 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. |
| [11] | 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. |
| [12] | 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. |
| [13] | 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. |
| [14] | 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. |
| [15] | 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. |
