大规模时序图SimRank计算方法研究与应用

“面向大规模时序图SimRank的计算方法，苗壮，袁野，乔百友，王一舒，马玉亮，王国仁，东北大学计算机科学与工程学院，国家重点研发计划资助项目，国家自然科学基金资助项目，顶点相似度，时序图，SimRank，Temporal-aware SimRank，TASimRank，随机游走，Monte Carlo，时间约束，图的拓扑结构，近似算法，实验验证，可扩展性” 本文主要探讨的是在大规模时序图中SimRank计算方法的问题。SimRank是一种衡量图中两个顶点之间相似性的算法，常用于社交网络、推荐系统和信息检索等领域。在静态图的研究中，SimRank被广泛应用于顶点相似度的计算。然而，现实世界的许多复杂系统，如交通网络、动态社交关系等，更适于用时序图来建模，这就需要对SimRank进行扩展以适应时序数据。 作者们指出，现有的SimRank计算方法无法直接应用到时序图中，因此他们提出了一个新的算法——时序关联的SimRank（Temporal-aware SimRank，简称TASimRank）。TASimRank算法考虑了图的拓扑结构以及时间约束，通过迭代方法有效地计算顶点间的SimRank值。这一方法能够捕捉到时序图中时间序列的影响，使得相似度计算更加准确。 为了提高计算效率，文中还介绍了一种近似算法。该算法利用随机游走策略构建树形索引，并采用Monte Carlo模拟方法来近似计算顶点相似度。这种近似方法能够在保持计算准确性的同时，降低计算复杂度，实现了时间和效率的平衡。 为了验证所提算法的可行性和性能，作者们进行了大量真实数据的实验。实验结果表明，TASimRank算法不仅能够有效计算时序图中的SimRank值，而且具有良好的可扩展性，适用于大规模数据集。 这篇文章为时序图的相似度计算提供了一种新的解决方案，对于理解动态网络中的顶点关系和相似性分析有着重要的理论和实践价值。同时，提出的近似算法也为实际应用中的高效计算提供了可能。