Page 165 - 《软件学报》2020年第12期

潘敏佳 等:面向时序图数据的快速环枚举算法 3831

(1) Wiki-talk 数据集.该数据集记录了 Wikipedia 用户修改其他用户的讨论页的行为;
(2) CollegeMsg 数据集.该数据记录了加州大学欧文分校在线社交网络中的信息发送情况;
(3) Higgs-twitter 数据集.该数据集记录了 twitter 上用户的信息往来行为;
(4) Stack-overflow 数据集.该数据集记录了 stackoverflow 网站上的用户往来行为.
Table 1 Experiment datasets
表 1 实验数据集
数据集 点数 边数 持续时间(天)
Wiki-talk 1 140 149 7 833 140 2 320
CollegeMsg 1 899 20 296 193 000
Higgs 304 691 563 069 7
Stackoverflow 2 464 606 17 823 525 2 774

4.1.3 实验设计
由于朴素的搜索算法效率过低且目前没有类似的约束时序环搜索算法,我们以 2SCENT 算法为基准来进
行对比.2SCENT 算法在搜索到环路后可以舍弃不符合要求的环路,最终达到本算法所要的输出结果.实验将以
时间窗口以及限制长度作为变量,针对算法运行所需要的时间(包括获得五元组时间和深度优先搜索时间)、内
存等方面进行比较.为了保证其他变量不对实验造成影响,在设置布隆过滤器时,我们使用统一的参数:我们设
置布隆过滤器的单边错误发生率为 0.01%,设置一个布隆过滤器中可能存的数为 1 000 个.

4.2 元组数量比较
在算法中,我们通过候选节点集合先对五元组进行了初步筛选(2SCENT 算法获得的其实为四元组,为了叙
述方便,之后不再特意指出),去掉了只有两个候选点(即最多形成二元环路)的五元组.从表 2 可以看出:通过最小
跳数值进行筛选,通过这些数据集获得的元组数量都有所减少,但是缩减的程度根据图的不同有较大的变化,最
小的变化量只有几十,大的缩减可以上千.这也可以侧面说明,在不同结构的图中,同一长度的环数量差别较大.

Table 2 Comparison between number of tuples
表 2 元组数量比较表
数据集 窗口及最大长度 2SCENT 本文
24h 4 159 313 158 109
Wiki-talk
36h 4 174 354 171 465
40h 5 5 147 4 870
CollegeMsg
50h 5 5 663 5 221
10h 4 2 526 2 496
Higgs
20h 4 2 800 2 742
8day 4 4 578 3 486
Stackoverflow
10day 4 5 756 4 176

4.3 运行时间比较
4.3.1 获取五元组时间
表 3 列出了 2SCENT 算法和本文算法的两种获取元组方式的大致运行时间.首先,我们横向比较同一算法
的两种获取五元组方式的运行时间.从表中可见:对于大多数图,使用布隆过滤器的方式更加耗时.产生这个现
象主要原因是:使用布隆过滤器的方式需要对原图进行正反两次遍历,毫无疑问,这增加了算法运行所需时间.
但是并不是所有图都有这样的现象.对于一些图而言,若图本身较小,或者图中需要继承的三元组过多,则布隆
过滤器会更优,这是因为布隆过滤器进行的是位向量的并操作,运行速度快.
另一方面,我们纵向比较不同数据集,同一方式之间的时间.由于在 2SCENT 算法中无法预知环路的长度,
因此想获得某一长度的环路也必须先对所有元组进行查找.但是由于 hop 的存在,我们的算法在查找小于某一
长度的时序环时显然更占优势.
从表格里可以看到:使用 hop 进行筛选有时,可以节约原时间的 70%以上.时间的减少主要来自两方面:第 1