, 乔百友, 王一舒, 马玉亮, 王国仁 东北大学 计算机科学与工程学院, 沈阳 110819
收稿日期：2018-07-21
基金项目：国家重点研发计划资助项目（2016YFC1401900）；国家自然科学基金资助项目（61572119，61622202）
作者简介：苗壮(1994-), 男, 硕士研究生
通信作者：袁野, 教授, E-mail: yuanye@ise.neu.edu.cn
摘要：顶点相似度计算在现实生活中具有广泛的应用。当前对相似性计算的研究工作主要集中于静态图上，并且大多相似性计算模型是基于SimRank算法提出的。而现实中的许多场景，需采用时序图进行建模。当前针对静态图的大量SimRank的计算方法无法在时序图中实现，因此该文对大规模时序图中的SimRank计算开展详细研究，并提出一种时序关联的SimRank计算方法（temporal-aware SimRank，TaSimRank）。TaSimRank根据图的拓扑结构和时间约束通过高效的迭代方法计算SimRank。同时，该文提出一种近似算法，通过随机游走方法建立树形索引，使用Monte Carlo方法近似计算顶点的相似度，取得时间和效率的平衡。最后，通过大量真实实验验证了提出算法的有效性和可扩展性。
关键词：时序图相似度随机游走
SimRank calculations for large temporal graphs
MIAO Zhuang, YUAN Ye
, QIAO Baiyou, WANG Yishu, MA Yuliang, WANG GuorenSchool of Computer Science and Engineering, Northeastern University, Shenyang 110819, China
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 graphsimilarityrandom walk
现实世界中许多应用都需要确定对象间的相似性，包括搜索相似文本[1]，同时计算对象间相似性也可以用于对不同对象进行聚类。在使用协同过滤的推荐系统[2]中，计算对象间的相似性显得尤为重要。传统的计算对象间相似性的算法采用静态图对这类应用进行建模，没有考虑到时间因素对于相似性计算的影响。针对这种情况，应采用时序图[3]来建模这一类具有时间信息的图结构。时序图与静态图的不同在于时序图中包含时间信息，表现为在时序图中顶点在特定的时间范围内与其他顶点产生关联。如图 1所示，假设图 1表示一个通信网络，图中顶点表示不同的人。顶点a和顶点c之间的边表示顶点a和顶点c在时刻3进行通信，即边上的权重表示时刻。由于时序图包含时间约束，因此时序图上许多性质与静态图不同。文[4]提出了时序图中路径的定义。文[5]对时序图中顶点可达性进行了相关研究。
 |
| 图 1 时序图 |
| 图选项 |
目前比较流行的在静态图上计算对象相似度的算法主要是SimRank算法[6]。文[6]使用迭代方法计算顶点相似度，该方法得到的结果十分准确，但是不适用于大规模图；文[7—8]使用保存中间结果的策略提高计算效率。文[9]通过Kronecker Product和向量化简化计算，即将迭代方法转化为矩阵乘法近似计算对象相似度；文[10]通过低秩近似的方法计算顶点相似度；文[11]提出了一种称为“one-way-graph”的数据结构保存随机路径计算顶点相似度；文[12]对静态图中每个顶点进行随机游走并保存路径，通过计算顶点相遇概率确定顶点相似度；文[13—14]对静态图建立了相应的树形索引，结合随机游走方法和Monte Carlo方法计算顶点相似度。
由于当前对于顶点相似度计算的研究主要集中在静态图上，这使得一旦图的拓扑结构随着时间发生变化，图中顶点的相似度就需要重新计算。针对这个问题，文[9—11, 13]将静态图上的SimRank算法扩展到动态图上，即在图的拓扑结构发生变化时，只需要计算一部分发生变化的顶点的相似度。虽然动态图相比静态图具有更加丰富的时间信息，但是相比时序图，动态图缺少路径间的时序联系；同时动态图相比静态图只是拓扑结构有变化，仍不包含时间因素。因此，在动态图上计算顶点相似度的方法不适用于时序图。
针对以上问题，本文提出了在时序图上计算顶点相似度的时序关联的SimRank算法(temporal-aware simrank, TaSimRank)算法。在时序图中如果2个对象被相同的对象所引用，那么称这2个对象相似，且被引用对象间的相似度与引用时间有关，被引用对象之间时间差越大，对象的相似度越小。为了使该算法能够适用于大规模时序图，本文提出了一种近似算法来近似计算顶点的相似度，该方法根据随机游走方法建立索引，并通过Monte Carlo方法近似计算顶点相似度, 取得时间和效率上的平衡，使得算法能够在大规模时序图上运行。
1 问题定义1.1 时序图相关知识时序图与静态图的不同在于时序图包含时间信息，对于时序图可以使用G=(V, E, T)表示，其中：V表示时序图中顶点的集合，E表示时序图中边的集合，T表示时序图中边上的时刻集合。图 1为时序图，图 2为相应的静态图，可以看出时序图具有更加丰富的时间信息。对于时序图中任意一条边e∈E，可以表示为(u, v, t)，其中：u表示起始顶点，v表示终点，t表示这条路径有效的时刻。
 |
| 图 2 静态图 |
| 图选项 |
对于时序图中任意顶点u∈V，指向顶点u的邻顶点集合可以表示为Γin(u, G)=v: (v, u, t)∈E。顶点u指向的邻顶点集合可以表示为Γout(u, G)=v: (u, v, t)∈E。在时序图中由于存在时间约束，不同顶点之间的边可能不止一条，对于时序图中任意顶点u, v∈V，顶点u和顶点v之间边的集合用Π(u, v)来表示。使用π(u, v)表示顶点u和顶点v之间边的数量，因此有π(u, v)=Π(u, v)。以图 1为例，顶点a和顶点b之间有2条边，所以有Π(u, v)=(a, b, 1), (a, b, 5)，π(u, v)=Π(u, v)=2。对于时序图中任意顶点u∈V，顶点u的入度可以表示为
定义1??时序路径：对于时序图G=(V, E, T)，有顶点序列p=(v1, v2, …, vk, vk+1)，其中对于任意1≤i≤k满足条件(vi, vi+1, ti)∈E且ti＜ti+1，则称p为时序图G中的一条路径。
定义2??顶点相遇：时序图G=(V, E, T)中，对于任意顶点u, v∈V，存在长度为t的路径pu=(u1, u2, …, ut)和pv=(v1, v2, …, vt)，对于任意1≤i≤k，有ui=vi，则说明顶点u和v在路径长度为i是首次相遇，记为first(pu, pv)=i。
1.2 时序图相似度定义根据以上定义，给出时序图上相似度计算问题的形式化定义。
输入：时序图G=(V, E, T)，目标顶点u, v。
输出：目标顶点u与顶点v的相似度。
以图 1和2为例，s(b, c)表示顶点b，c的相似度。对于时序图，计算相似度时需要考虑边(a, b, 1)，(a, b, 5)和(a, c, 3)，以及相应的时间因素。对于静态图，计算相似度时仅需要考虑边(a, b)和(a, c)。与时序图相比，在计算顶点相似度的过程中，静态图不考虑时间因素。
2 TaSimRank基本方法TaSimRank-base算法的基本思想是：依据时序图的拓扑结构信息和时序图中的时间约束来计算图中顶点的相似度。不同于静态图上的SimRank算法，本文提出的TaSimRank-base算法具有时间约束，因此顶点的相似度受到顶点所在时刻的影响，在时序图G=(V, E, T)中，存在顶点a, b∈V，本文提出的算法可以表示如下：
| ${s^0}\left( {a, b} \right) = \left\{ \begin{array}{l}0, \;\;a \ne b;\\1, \;\;\;a = b.\end{array} \right.$ | (1) |
| $\begin{array}{l}{s^{k + 1}}\left( {a, b} \right) = \frac{c}{{\left| {{d_{{\rm{in}}}}\left( a \right)} \right|\left| {{d_{{\rm{in}}}}\left( b \right)} \right|}} \cdot \\\sum\limits_{i = 1}^{\left| {{d_{{\rm{in}}}}\left( a \right)} \right|} {\sum\limits_{j = 1}^{\left| {{d_{{\rm{in}}}}\left( b \right)} \right|} {\frac{{{s^k}\left( {{\mathit{\Gamma }_{{\rm{i}}{{\rm{n}}_i}}}\left( a \right), {\mathit{\Gamma }_{{\rm{i}}{{\rm{n}}_j}}}\left( b \right)} \right)}}{{\left| {{t_{{\mathit{\Gamma }_{{\rm{i}}{{\rm{n}}_i}}}}}\left( a \right) - {t_{{\mathit{\Gamma }_{{\rm{i}}{{\rm{n}}_j}}}}}\left( b \right)} \right|}}} } \end{array}$ | (2) |
3 TaSimRank近似计算方法本文提出一种两阶段的基于随机游走的TaSimRank-R算法，该算法运行速度较快，适用于大规模时序图。TaSimRank-R算法的第一阶段包括使用随机游走方法建立索引，使用Bootstrap方法[15]对顶点的时间进行分层抽样并估计不同路径长度上的时刻差的期望；第二阶段根据前一阶段建立的索引以及估计的时间差结合Monte Carlo方法计算目标顶点与其他顶点的相似度，该方法是一种近似算法，因此精确度相对较低。
3.1 建立索引方法TaSimRank基本计算方法采用基于迭代的方法计算时序图上顶点相似度。该方法具有较高的时间复杂度，因此不适用于大规模时序图。
为了在大规模时序图上计算顶点相似度，本文提出了一种新颖的树形索引结构，同时使用随机游走方法和Monte Carlo方法来近似计算顶点的相似度。为了更加方便地理解建立索引的过程，简单介绍路径融合的概念。在时序图中对于两条长度为t的反向随机游走路径pu=(u0, u1, …ut)和pv=(v0, v1, …vt)，对于1≤i≤t如果有ui=vi，则路径pu和pv是可融合的。路径融合后2条路径沿着相同的路径继续进行随机游走。路径融合不仅能够防止在随机游走过程中出现重复路径的问题，同时路径融合也能确保时序图中任意顶点在索引中具有的公共祖先是它们首次相遇的顶点。
以图 3为例，在图 3a中选择2条反向随机游走路径，选取路径如图 3b所示，进行路径融合后的结果如图 3c所示，2条路径进行融合之后沿着同一条路径继续进行随机游走到达顶点v0。
 |
| 图 3 路径融合 |
| 图选项 |
本文提出了一种新颖的使用随机游走方法建立树形索引的算法。建立索引算法的思路是：对顶点进行反向随机游走，同时使用路径融合的方法自下而上的建立树形索引。给定时序图G=(V, E, T)，将对时序图G建立索引，采用自下而上的树形索引建立方法。对时序图中任意顶点u∈V，创建一棵以u为叶节点的单节点树，并记level(u)=0，通过对每个叶节点进行反向随机游走生成具有更高level的顶点，在进行反向随机游走的过程中，如果有任意2个节点的祖先节点相同，那么对这2条随机游走路径进行融合；直到图中顶点入度为0，或者指向当前顶点的边不满足顶点上的时间约束，此时停止随机游走过程。
以图 4为例，图 4是以图 1为基础的一个索引建立过程，首先建立索引如图 4a所示，对图 1中每个顶点建立单节点树；后通过反向随机游走找到该节点的祖先节点，若有相同的祖先节点则进行路径融合。图 4b中对于节点b、c存在路径pb=(b, a)和路径pc=(c, a)，说明节点b、c在节点a处相遇即节点b和c有相同的祖先节点，因此进行路径融合。同理，在图 4c中，节点b和d具有相同的祖先顶点，因此可以进行路径融合。
 |
| 图 4 根据路径融合建立索引 |
| 图选项 |
本文提出的索引生成流程如图 5所示。
 |
| 图 5 索引生成算法 |
| 图选项 |
3.2 近似计算方法本文提出了在时序图上近似计算顶点相似度的算法TaSimRank-R算法。
TaSimRank-R算法思路是：结合随机游走方法和Monte Carlo方法近似计算时序图中顶点相似度，首先对时序图建立r个树形索引，在索引建立完成后，算法找到目标顶点所在的树，计算目标顶点和树中其他叶子顶点的相似度，并依据Monte Carlo方法计算最终结果。在时序图中计算顶点相似度需要考虑到顶点的时间因素，根据问题定义可知，顶点时间的差值越大，其相似度越小。具体流程如图 6所示。
 |
| 图 6 基于随机游走的SimRank近似计算方法 |
| 图选项 |
算法时间复杂度为O(r|V|)，其中：r为索引数量，|V|为时序图中顶点的数量。可以看出相比于TaSimRank-base算法，TaSimRank-R算法的时间复杂度有很大的降低。
由于使用抽样的方法建立索引，因此索引中顶点的时刻并不能很好地表达时序图中顶点的时刻。针对这个问题，可以使用Bootstrap方法[15]对索引中每一层的时刻进行抽样。Bootstrap抽样的基本思想是在全部样本未知的情况下，借助部分样本的有放回多次抽样，构建某个估计的置信区间。本文借助该方法来近似计算时序图中顶点的时刻差，近似计算时序图中顶点相似度。
在此简单介绍Monte Carlo方法在近似计算顶点相似度中的作用。文[6]中给出了基于随机游走方法近似计算顶点相似度的方法，主要思想是将顶点的相似度近似为顶点在图中进行随机游走第一次相遇的概率，即需要计算pr(first(pu, pv)=i)。然而要枚举出顶点在图中的全部路径是十分困难的事情。一个简单的方法是使用Monte Carlo方法进行近似计算。给定图G顶点u和顶点v，分别从顶点u和顶点v生成长度为t的反向随机游走路径pu=(u0, u1, …, ut)和pv=(v0, v1, …, vt)。对于任意1≤i≤t，路径pu和pv第一次相遇的路径长度记为first(pu, pv)=i，因此根据生成的r条路径，通过式(3)，使用Monte Carlo方法近似计算顶点的相遇概率pr(first(pu, pv)=i)。在计算出相遇概率后，就可以计算顶点的相似度。
| $\begin{array}{l}\overline {{\rm{pr}}} \left( {{\rm{first}}\left( {{p_u}, {p_v}} \right) = i} \right) = \\\frac{{\left| {\left\{ {j \in \left[ {1, r} \right]\left| {{\rm{first}}\left( {{p_u}, {p_v}} \right) = i} \right.} \right\}\left. {} \right|} \right.}}{r}.\end{array}$ | (3) |
| $s\left( {u, v} \right) = \sum\limits_{i = 1}^k {\overline {{\rm{pr}}} } \left( {{\rm{first}}\left( {{p_u}, {p_v}} \right) = i} \right) \times \prod\limits_{j = 1}^i {\frac{c}{{{t_j}}}} .$ | (4) |
4 实验为了验证本文算法具有有效性和可扩展性，选取了来自真实世界的数据集作为输入数据。实现了在时序图上计算顶点相似度的TaSimRank-bsae算法，以及该算法的近似算法TaSimRank-R算法。
4.1 实验环境和数据集实验环境：本文实验的使用Java语言编写，运行在2.4 GHz CPU和12 GB内存的Ubuntu 16.04的机器上。
实验算法：实验对本文提出的2种算法进行了对比，分别是TaSimRank-base算法和TaSimRank-R算法。其中TaSimRank-base算法可以精确计算时序图上顶点的相似度，TaSimRank-R算法可以近似计算时序图上顶点的相似度。
参数设置：对于TaSimRank-base算法，参数c设定为0.8，迭代2次。对于TaSimRank-R算法，参数c设定为0.8，路径长度设定为2，建立的索引数量设定为100。
数据集选取：本实验所选用的数据集规模从小到大，都是实际应用中采集的数据，这些数据都来自Stanford Large Network Dataset Collection。实验中选择了来自Temporal networks的3个数据集，分别为：sx-askubuntu-c2a、sx-superuser-c2a、sx-askubuntu。这3个数据集均是有向时序图。实验数据集的相关信息如表 1所示。
表 1 实验数据集
| 数据集 | 顶点数 | 时序边 | 静态边 | 时间/s |
| sx-askubuntu-c2a | 75 555 | 356 822 | 178 210 | 2 418 |
| sx-superuser-c2a | 101 052 | 534 239 | 289 487 | 2 735 |
| sx-askubuntu | 159 316 | 964 437 | 596 933 | 2 613 |
表选项
4.2 精确度在top-k查询中，通过测量真实数据中top-k个顶点和近似数据中top-k个顶点，并计算其中相同的顶点数量在k个顶点中的比例作为精度来评估不同算法的质量，具体如下：
| ${\rm{precision}} = \frac{{\left| {{\rm{approximated}}\_{\rm{set}} \cap {\rm{exact}}\_{\rm{set}}} \right|}}{k}$ | (5) |
 |
| 图 7 算法准确度 |
| 图选项 |
4.3 运行时间比较算法运行时间的实验结果如图 8所示。通过对TaSimRank-base算法和TaSimRank-R算法在不同数据集上的运行时间进行比较，可以看出TaSimRank-R算法在数据集sx-askubuntu-c2a、sx-superuser-c2a和sx-asubuntu上的运行时间均优于TaSimRank-base算法，同时随着数据集规模的增大，TaSimRank-base算法随着数据集规模的增大，所用时间明显增多，而TaSimRank-R算法随着数据集规模的增大，所用时间没有显著增加。实验结果表明，本文提出的近似计算方法确实可以提高算法运行效率。
 |
| 图 8 查询时间 |
| 图选项 |
4.4 索引建立代价通过对顶点进行反向随机游走和路径融合来建立索引，图 9给出了实验中对不同数据集建立索引的大小。对每个数据集建立100个索引，可以看出，索引的大小随着数据集规模的增大而增大。表明索引的大小只与数据集的规模有关。图 10给出了针对不同数据集建立索引所需要的时间，随着数据集规模的增大，建立索引的时间增加。建立索引的时间主要与数据集中顶点的数量有关。
 |
| 图 9 索引建立时间 |
| 图选项 |
 |
| 图 10 索引大小 |
| 图选项 |
5 结论本文针对时序图上顶点相似度计算问题，提出了TaSimRank算法，一种时序关联的SimRank算法。本文首先提出了算法基于迭代方法的实现形式TaSimRank-base算法，然后为了解决TaSimRank-base算法无法应用于大规模时序图的问题，提出了一种两阶段的相似度近似计算方法TaSimRank-R算法。实验结果表明：该算法具有良好的可行性和有效性。通过实验可以观察到，在顶点相似度top-k查询中，该算法在k值较小时，具有较大的误差。同时建立索引需要消耗大量时间，下一步工作是研究如何提高算法的准确度，并且研究如何更有效的建立索引。
参考文献
| [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. DOI:10.1016/j.physrep.2012.03.001 |
| [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. DOI:10.14778/2732939 |
| [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. DOI:10.1007/s00778-009-0168-8 |
| [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. DOI:10.14778/2757807 |
| [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. DOI:10.1016/j.ins.2016.10.042 |
| [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. DOI:10.14778/3099622 |
| [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. DOI:10.1111/test.2001.23.issue-2 |
