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

苟向阳 等: 高精度滑动窗口模型下的图流三角形近似计数算法 4365

3.5 CBS-FP 算法
CBS 算法使用的采样方法为 SWTC 算法中的优先级采样方案, 也可以将其替换为固定概率采样方案, 也就是
对于图流中的每一条新边, 运行一个满足概率为 r 的伯努利分布的随机函数, 当函数返回值为 1 时, 将新边加入样
本集合, 否则便丢弃该边. 当使用固定概率采样时, 在估算三角形数目时, 需要把计算公式中的 p(2) 和 p(3), 也就是
任意 2 条, 或 3 条边被加入样本集的概率, 替换为 r 和 , 其他步骤和原版的 CBS 算法相, 称该变体为 CBS-FP 算
2
3
r
法. 与 CBS 算法相比, CBS-FP 算法的优点在于采样算法简单, 因此运行速度很高. 而缺点有两点. 首先, CBS-FP 算
法的样本集大小为 r|W|, 其中 |W| 为滑动窗口内的边数, 该值随着图流的流量, 也就是单位时间内到达的边数而变
化. 因此, 其内存占用随着图流流量而变化, 难以预估其内存占用峰值并在系统中预留足够内存. 其次, 即使能够预
估其内存占用峰值并预留出来, 这部分内存在平时无法被充分利用, 导致算法在占用相同的预留内存的情况下, 平
均误差低于 CBS 算法. 我们会在第 4 节对 CBS 和 CBS-FP 算法进行更详细的对比.

4 实验分析

在本节, 对 CBS 算法进行实验分析. 在第 4.1 和第 4.2 节, 会分别介绍实验使用的数据集和设置. 由于 SWTC
算法是目前已知的唯一一个滑动窗口上具有固定空间消耗的三角形数目估算算法, 因此主要将 CBS 算法与
SWTC 算法进行对比. 在第 4.3 节, 会对比 CBS 算法和 SWTC 算法的估算误差. 在第 4.4 节中, 分析 CBS 算法的估
算效果随着滑动窗口大小的变化趋势, 并与 SWTC 算法对比. 而在第 4.5 节中, 进一步将 CBS 算法和固定概率采
样算法对比, 后者被多种经典三角形近似计数算法如 MASCOT [28] 采用, 但是这些经典算法没有考虑滑动窗口模
型, 将其进行一定调整以适应滑动窗口模型, 具体细节如第 2.1 节所述. 此外, 也比较了 CBS 算法使用固定概率采
样时的变体 CBS-FP, 以及基于全动态模型的 WRS [19] 和 ThinkD [18] 算法. 需要注意的是, 为了将全动态模型的算法
迁移到滑动窗口模型, 需要保存滑动窗口中的所有边及其时间戳, 以判断每一条边何时过期. 在第 4.6 节中, 对
CBS 算法进行消融实验, 分析误差修正算法 ETM 的影响, 以及区间划分数量 d 的影响. 在第 4.7 节中, 对 CBS 和
SWTC 在有向三角形计数中的效果进行对比分析. 最后, 第 4.8 节将对不同算法的运行速度和内存消耗进行分析.
所有的实验均在一台具有 18 核 CPU (Intel Xeon CPU E5-2697 v4@2.3 GHz, 每核 2 线程) 和 192 GB 内存的
服务器上进行, 服务器运行 CentOS 系统, 代码采用 C++ 编写并使用 GCC 4.8.5 编译, 运行时采用 O3 优化. 所有代
码均已在 https://github.com/StreamingTriangle/CBS 上开源.

4.1 实验数据
实验采用如下 3 个源自真实世界的数据集,
StackOverflow [39] : 该数据集是技术交流社区 StackOverflow 上的用户交互数据. 数据集中的点代表用户, 边代
表用户间的交互, 每条边具有时间戳, 表示交互发生的时间. 该数据集共有 63 497 050 条边, 2 601 977 个点. 该数据
集存在重复边, 代表两个用户之间发生了多次交互. 数据集下载自图数据开源网站 Konect [40] .
Wikipedia [41] : 该数据集描述了法语区维基百科的网页超链接关系, 数据集中的点代表网页, 而边代表网页之
间的超链接关系. 该数据集共有 123 709 902 条边和 3 333 397 个点. 数据集中不含重复边. 数据集下载自图数据开
源网站 Konect [40] .
Yahoo [42] : 来自 Yahoo 公司的开源网络流数据集, 我们把 IP 地址作为点, IP 之间的通信作为边, 数据集包含
561 754 369 条边和 33 635 059 个点, 数据集中含重复边.
Wikipedia 数据集没有边上的时间戳, 因此我们随机为边生成了均匀分布的时间戳. 而 StackOverflow 和 Yahoo
数据集则采用了原始时间戳. 我们使用不同算法按照时间顺序处理数据集中的边, 以此来模拟真实图流场景. 此
外, 对于含重复边的前两个数据集, 我们采用第 1 节所述的带权计数语义.

4.2 实验设置
● 滑动窗口设置: 为了让滑动窗口长度更加直观, 我们计算数据集中相邻两条边的平均时间间隔, 也就是用数
据集中最大时间戳和最小时间戳之间的差值, 除以数据集内的总边数. 我们以这样的平均时间间隔作为滑动窗口