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

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

6. for i = 0; i ⩽ min(d,y−1); i++ do
τ i = 0
7.
8. E exp ← G s 中时间戳不大于 T +∆T − N 的边

(⌊ ⌋ )
(T +∆T)d N
9. l = −d ×
N d
10. while E exp , ∅ do
e ← E exp 中时间戳最小的边
11.
12. if e.ts > l then
//计数该过期边组成的三角形
13. v i ,v j ← e 的两个端点
∆ s = ∅
14.
15. for v k ∈ G s .FindNeighbor(v i )∩G s .FindNeighbor(v j ) do
δ = [(v i ,v j ),(v i ,v k ),(v j ,v k )]
16.
17. ∆ s = ∆ s ∪{δ}
|∆ s |
18. τ exp + =
p(3)
19. 从 G s 和 E exp 中删除 e
20. T = T +∆T

与原方法相比, 该方法额外增加了对于 τ exp 计数器的更新. 当前时刻增加 ∆T 时, 首先计算是否会经过路径点
y = ⌊(T +∆T)d/N⌋−⌊Td/N⌋ 大于 τ exp 设置为 0, 因为其中
并产生新的区间. 如果 0, 说明经过了 y 个新区间, 首先将
统计的是旧的 I d 内的过期三角形数目, 现在旧的 I d 已经不再与滑动窗口相交, τ exp 的旧值也不再需要. 之后算法使
用算法 2 相同的流程更新三角形计数器 τ 0 τ d . 之后算法收集 G s 中的过期边集合 E exp , 并计算更新后 I d 的左端点
–
l. 算法按时间戳从小到大的顺序扫描 E exp 中的每条边 e, 当 e > l 时, 计数其在 G s 中形成的三角形数量, 并在除以概
I d 内, 而是在已经不与滑动窗口相交的更早区
率 p(3) 后累加到 τ exp 上. 注意可能出现 e ⩽ l 的情况, 这时说明 e 不在
间内, 它形成的三角形也不在 I d 内, 不需要对其进行计数. 之后算法从 G s 中删除 e. 需要注意的是, 算法按照时间
顺序处理过期边, 是为了避免重复计数 G s 中包含多条过期边的三角形. 最后, 设置 T = T +∆T .
∑ d
改进后的 CBS 算法中, 处理图流新边的方法和算法 1 一致. 而查询时, 需要返回 τ i −τ exp 的值.
i=0
τ exp 时只使用了样本边的信息, 相比采样前计数策略不够精准. 但是
需要注意的是, 估算 I d 内过期三角形数目
由于只用该方法估算不超过一个区间的小范围内的三角形数目, 其估算误差对整个滑动窗口内三角形数目估算的
影响较小. 第 4 节的实验表明, 改进后的 CBS 算法能取得比 SWTC 算法低 70% 的平均误差.

3.3 数学分析
本节我们对 CBS 算法进行数学分析, 包括估算无偏性证明、方差分析和算法复杂度分析.

3.3.1 无偏性分析
定理 2. 结合了 ETM 误差修正之后的 CBS 算法能够提供滑动窗口内三角形数量的无偏估算.
证明: 假设改进后的 CBS 算法的三角形数目估算值为 τ, 则有:

( ) ( )
E (τ) = E τ int −τ exp = E (τ int )− E τ exp (2)
∑ d
其中, τ int = τ i, 也就是 d +1 个与滑动窗口相交区间内的有效三角形数目估算值之和. 而 τ exp 则是 CBS 对区间
i=0
I d 内的过期有效三角形的数目估算值. E(·) 表示变量的期望值. 我们依次对它们的期望进行分析. 首先是 τ int :

)
d d
(∑ ∑
E (τ int ) = E τ i = E(τ i ) (3)
i=0 i=0
本文用 ∆ i 表示时间戳在区间 I i 内的有效三角形集合. 对于每一个三角形 δ ∈ ∆ i , 设置一个变量 ξ(δ). 假设 δ 中