%0 Journal Article
%T 面向大规模时序图SimRank的计算方法<br>SimRank calculations for large temporal graphs
%A 苗壮
%A 袁野
%A 乔百友
%A 王一舒
%A 马玉亮
%A 王国仁
%J 清华大学学报（自然科学版）
%D 2018
%R 10.16511/j.cnki.qhdxxb.2018.26.050
%X 顶点相似度计算在现实生活中具有广泛的应用。当前对相似性计算的研究工作主要集中于静态图上，并且大多相似性计算模型是基于SimRank算法提出的。而现实中的许多场景，需采用时序图进行建模。当前针对静态图的大量SimRank的计算方法无法在时序图中实现，因此该文对大规模时序图中的SimRank计算开展详细研究，并提出一种时序关联的SimRank计算方法（temporal-aware SimRank，TaSimRank）。TaSimRank根据图的拓扑结构和时间约束通过高效的迭代方法计算SimRank。同时，该文提出一种近似算法，通过随机游走方法建立树形索引，使用Monte Carlo方法近似计算顶点的相似度，取得时间和效率的平衡。最后，通过大量真实实验验证了提出算法的有效性和可扩展性。<br>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.
%K 时序图
%K 相似度
%K 随机游走
%K &lt
%K br&gt
%K temporal graph
%K similarity
%K random walk
%U http://jst.tsinghuajournals.com/CN/Y2018/V58/I12/1066