Page 455 - 《软件学报》2025年第9期

4366 软件学报 2025 年第 36 卷第 9 期

长度的单位. 如此一来, 滑动窗口的长度也代表了滑动窗口中的平均边数.
T 设置为已经处理的最大时间戳, 算法按时间顺序处理数据集中的边, 此过程
● 测量点设置: 我们把当前时刻
中 T 不断增大, 新边不断被加入滑动窗口, 而旧的边则不断过期, 导致滑动窗口向前持续滑动, 快照图及其中的三
N/50, 也就是每当 T
角形数目不断变化, 算法的估算误差也在不断波动. 我们每间隔 增加滑动窗口长度 N 的 1/50
∗ τ 之
时, 设置一个测量点. 我们在这些测量点测量不同算法对当前时刻快照图中三角形数目的估算值 τ 和真实值
|(τ −τ)/τ|. 之后, 我们计算平均相对误差和最大相对误差作为算法估算误差的评价指标, 分别定义
∗
间的相对误差
如下.
平均相对误差: 所有测量点的相对误差的平均值.
最大相对误差: 所有测量点的相对误差的最大值.
需要注意的是, 我们不会采用数据集中的前 50 个测量点, 这时滑动窗口中的边数过少, 存在大量三角形数目
为 0 的测量点, 导致无法计算相对误差. 在表 1 中, 列出了实验使用的 3 个数据集在默认滑动窗口设置下, 所有测
量点的平均三角形数量. 此外, 每组实验都使用不同的随机数种子跑 10 轮, 取 10 轮的平均值作为最终实验结果.
需要注意的是, 由于 Yahoo 数据集总规模和滑动窗口长度都很大, 在其上的计数, 尤其是计数精确三角形数目, 十
分耗时, 为了保证实验能及时完成, 本文只使用了前 300 个测量点.

表 1 不同数据集的平均三角形数量

数据集及滑动窗口长度 StackOverflow (4M) Wikipedia (10M) Yahoo (20M)
平均三角形数量 61 502 435 42 883 353 53 787 454

● 算法参数设置: CBS 算法与 SWTC 算法都采用了基于子流划分的固定空间采样. 其中的子流数目 K 代表了
算法存储的边数以及样本图的最大大小, 也代表了算法的空间占用大小. 而 CBS 相比 SWTC, 在数据结构上的唯
一区别是增加了 d 个三角形计数器, 而这 d 个三角形计数器只占数十 Byte, 相比算法总空间消耗的数十 MB 可以
K 的情况下是相同的. 为了直观反映样本大小和滑动窗口
忽略, 因此, 我们可以认为两个算法的空间消耗在相同的
总边数的关系, 我们进一步定义了样本比例.
● 样本比例: CBS 和 SWTC 算法中的子流数目 K 和滑动窗口长度 N 的比值, 其中滑动窗口长度以上文所述的
平均时间间隔为单位.
样本比例反映了样本集的最大大小与滑动窗口中的平均边数之间的比值. 下文中, 通过设置采样比例来控制
算法的空间占用. 在第 4.8 节中,本文也会列出样本比例和实际内存占用的对应关系.
此外, 对于 CBS 算法的区间划分数量 d, 设置的默认值为 10, 也就是说每个区间的大小为滑动窗口长度的 1/10.

4.3 误差对比
图 8 和图 9 分别展示了 SWTC 算法和 CBS 算法的平均相对误差和最大相对误差随着采样比率的变化趋势.

20
18 CBS SWTC 25 CBS SWTC 100 CBS SWTC
平均相对误差 (%) 14 8 平均相对误差 (%) 20 平均相对误差 (%) 80
16
12
15
60
10
40
10
4 6 5 20
2
1.0 1.5 2.0 2.5 3.0 3.5 4.0 1.0 1.5 2.0 2.5 3.0 3.5 4.0 1.0 1.5 2.0 2.5 3.0 3.5 4.0
样本比例 (%) 样本比例 (%) 样本比例 (%)
(a) StackOverflow (b) Wikipedia (c) Yahoo
图 8 不同算法的平均相对误差

图 8 和图 9 中 StackOverflow、Wikipedia、Yahoo 这个数据集的滑动窗口长度依次是 4M、10M、20M. 从实
验结果中我们可以看出, 两种算法的误差都会随着采样比例的增加而显著下降, 这是由于快照图大小不变的情况