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

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

法在它过期时及时发现. 采样前计数策略要求在每次边删除时估算该边导致的三角形数目减少值, 无论被删除的
边是否被采样, 这一点在滑动窗口模型下难以实现.
为了处理这一问题, 本文设计了基于时间区间划分的策略来处理数据过期. 本文为图流中的每一个三角形赋
予一个时间戳, 其被定义为三角形 3 条边中的最小值. 此外, 本文定义 3 条边时间戳的最小值和最大值相差不超过
N 的三角形为有效三角形, 其中 N 为滑动窗口的长度. 本文证明了在任意时刻, 滑动窗口中的边组成的三角形集合
N/d 的区间, 在图流更新的过程中使
等同于时间戳落入滑动窗口的有效三角形集合. 本文将时间轴划分为长度为
用采样前计数策略估算时间戳落入每一个区间内的有效三角形数目. 之后将与滑动窗口相交的区间中的有效三角
形数目之和 τ 作为滑动窗口中的三角形的数目的估算值. 这一策略通过区间切换实现了的过期处理. 每当时间推
移到一个区间分割点时, 就会有一个旧的区间不再与滑动窗口相交, 而时间戳在该区间中的有效三角形全部已经
过期, 其数目将被从估算值中减去. 由于与滑动窗口相交的区间的并集是滑动窗口的超集, τ 的期望值大于滑动窗
口内三角形数目的真实值. 为了实现无偏估算, 我们又提出误差修正策略 ETM (expired triangle-count modification).
τ 和滑动窗口中的三角形的数目的差值, 将其从 中减
该策略根据这些区间内的过期样本边的拓扑信息, 估算出 τ
去以保持估算的无偏性. 最终 CBS 算法在保证无偏估算的基础上, 达到比现有算法 SWTC 更高的精确度. 实验证
明, CBS 算法的估算误差比 SWTC 下降了 70% 以上.
总结来说, 本文有以下贡献点.
(1) 提出滑动窗口上固定空间消耗的三角形近似计数算法 CBS, CBS 将现有的 SWTC 算法和采样前计数策略
结合, 并且设计基于时间区间划分的策略来解决采样前计数不支持数据过期的问题.
(2) 进一步设计误差修正策略 ETM, 该策略针对 CBS 算法的估算期望值和滑动窗口内三角形数目真实值之
间的偏差进行进一步修正, 使得 CBS 算法成为无偏估算算法.
(3) 在真实数据集对 CBS 算法进行实验评估, 实验结果表明 CBS 算法相比现有算法在相同空间消耗下误差
降低 70% 以上.
本文的第 1 节将给出研究问题的正式定义. 第 2 节将介绍图流三角形近似计数的相关工作. 第 3 节将具体介
绍 CBS 算法. 第 4 节中将给通过实验对比 CBS 算法与现有工作以验证其优势. 最后在第 5 节总结全文.

1 研究问题定义

● 图流 (graph stream): 图流是一个从数据源持续不断到达的数据项组成的序列 S = {e 1 ,e 2 ,e 3 ,...}, 每一个数据
(v i ,v j ) 以及该数据项到达的时间戳 t.
项包含一条边
图流中的边可以为有向边或者无向边, 在三角形计数问题中一般不考虑边的方向, 所以本文假定图流中的边
都是无向的. 在第 3.4 节中会讨论有向三角形计数问题. 需要注意的是, 图流的流量不是稳定不变的, 在有些时间
点可能有多条边到达, 在有些时间点则可能没有任何边到达. 由于图流数据是持续到达的, 算法无法对完整的图流
数据进行分析. 此外, 实际应用中一般更关注最新的数据. 因此, 大部分图流应用都使用滑动窗口模型划分出近期
的图流数据, 将其视为有效, 而滑动窗口之外的数据被视为过期. 滑动窗口的具体定义如下.

● 滑动窗口 (sliding window): 假设当前时间为 T , 一个长度为 N 的滑动窗口 是图流中时间戳在 (T − N,T] 区
间内的边组成的集合.
滑动窗口内的边被称为有效边, 而滑动窗口之外的边被称为过期边. 此外, 我们称 T 时刻滑动窗口中的边组成
的图为快照图 (snapshot graph). 随着时间推移, 图流中不断有新边被加入滑动窗口, 而滑动窗口中的旧边则因为过
期而被删除, 导致快照图不断发生变化. 本文和之前的图流算法研究一样, 不考虑图流数据的乱序和延迟等问题.
也就是说, 假设图流中每条新边到达时, 其时间戳等于当前时刻 T , 且不小于之前到达的边的时间戳. 此外, 在下文
中, 出于论述简单考虑, 使用正整数来表示图流中每条边的时间戳和滑动窗口的长度. 本文关注快照图上的三角形
计数问题.
● 三角形计数 (triangle counting): 滑动窗口模型下的三角形计数要求在图流更新的过程中实时维护快照图中