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

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

2 2 δ 的
更进一步地, 有 Var(χ(δ)) = E(χ(δ) )− E(χ(δ)) . 由于 3 条边均在样本集中的概率为 p(3), 因此 E(χ(δ)) =
1 2 1 1 1
p(3)× = 1, 而 E(χ(δ) ) = p(3)× = , 因此 Var(χ(δ)) = −1.
p(3) p(3) 2 p(3) p(3)
另一方面, Cov(χ(δ),χ(δ )) = E (χ(δ)χ(δ ))− E (χ(δ))E (χ(δ )), 其中 E (χ(δ))E (χ(δ )) = 1. 而对于 E(χ(δ)χ(δ )),
∗
∗
∗
∗
∗
∗ χ(δ ) 都非 ∗
∗
若 δ 与 δ 没有公共边, 则 χ(δ) 与 0 的充要条件是两个三角形的 6 条边都被采样, 概率为 p(6). 若 δ 与 δ
χ(δ ) 都非 0 p(5).
∗
有一条公共边, 则 χ(δ) 与 的充要条件是两个三角形的共 5 条边都被采样, 概率为

 p(6)

∗
 , δ与δ 没有公共边

 2
 p(3)


∗ 
E (χ(δ)χ(δ )) =  (10)

 p(5)


∗
 , δ与δ 有一条公共边

 2
p(3)
因此, 公式 (9) 可以进一步展开为:

( ) ( ) ( )
1 p(6) p(5)
Var(τ swtc ) = |∆| −1 +2η −1 +2λ −1 (11)
p(3) p(3) 2 p(3) 2
其中, |∆| 为滑动窗口中的三角形数目, η 为滑动窗口中没有公共边的互异三角形对的数目 (无序对), λ 为滑动窗口
中有一条公共边的互异三角形对的数目 (无序对).
(2) CBS 方差分析
对于 CBS 算法我们有:

( ) ( ) ( )
Var(τ cbs ) = Var τ ind −τ exp = Var(τ ind )+Var τ exp −2Cov τ ind ,τ exp (12)
其中, τ exp 和 τ ind 正相关, 因为一个三角形被计入 τ exp 的充要条件是它的 3 条边均被采样, 那么它的前两条边也会
别采样, 因此它也会被计入 τ ind . 所以 Cov(τ ind ,τ exp ) 为正数. 所以:

( )
Var(τ cbs ) ⩽ Var(τ ind )+Var τ exp (13)
其中, τ exp 的估算过程和 SWTC 算法相同, 一个三角形被纳入 τ exp 的充要条件是它的 3 条边均被采样, 而这时它会
Var(τ exp ), 并得到相似的结果, 只是需要将公式 (11)
给 τ exp 带来 1/p(3) 的增加量. 因此可以类比 SWTC 的分析来计算
中的滑动窗中口三角形数目以及滑动窗口中互异三角形对的数目改为最旧的区间 I d 中的过期三角形数目以及过
期三角形对的数目. 图流流量稳定时, I d 的长度为滑动窗的中的 1/d, 其中过期三角形数目小于滑动窗口中三角形
1
Var(τ ind ) < Var(τ swtc ). 为了让
数目的 1/d, 过期三角形对的数目也小于滑动窗口中三角形对数目的 1/d. 因此
d
K
对比更加直观, 我们考虑 d → K, 也就是说区间划分的数量 d 足够大, 接近子流数目 , 这时 Var(τ ind ) 只有 Var(τ swtc )
的数万分之一, 相比之下可以忽略不计, 因此有:

( )
Var(τ cbs ) ⩽ Var(τ ind )+Var τ exp ≈ Var(τ ind ) (14)
我们接下来分析 Var(τ ind ), 类比 SWTC, 可以得到:

(∑ ) ∑ ∑ ∑
∗
Var(τ ind ) = Var ξ(δ) = Cov(ξ(δ),ξ(δ )) = Var(ξ(δ))+ Cov(ξ(δ),ξ(δ )) (15)
∗
δ∈ ¯ ∆ δ,δ ∗ ∈ ¯ ∆ δ∈ ¯ ∆ δ,δ ∗ ∈ ¯ ∆,δ,δ ∗
其中, ξ(δ) 的定义如无偏性证明部分所述. ∆ ¯ 表示的是与滑动窗口相交的 d +1 个区间内的有效三角形的集合, 当
1
图流流量稳定时, 该集合中三角形数目为滑动窗口中三角形数目的 1 到 1+ 倍.
d
( )
2
2
进一步的, Var(ξ(δ)) = E ξ(δ) − E(ξ(δ)) . 如第 3.3.1 节分析, ξ(δ) 有 p(2) 的概率取 1/p(2), 其他情况取 0, 因
1 ( 2 ) 1 1 1
此 E (ξ(δ)) = p(2)× = 1, 而 E ξ(δ) = p(2)× 2 = , Var(ξ(δ)) = −1.
p(2) p(2) p(2) p(2)
*
*
*
*
*
而 Cov(ξ(δ),ξ(δ )) = E(ξ(δ)ξ(δ ))− E(ξ(δ))E(ξ(δ )), 其中 E(ξ(δ))E(ξ(δ )) = 1. 下面我们分析 E(ξ(δ)ξ(δ )). 假设 δ
*
s δ 中时间戳较小的两条边组成的集合为 ,
∗
中时间戳较小的两条边组成的集合为 , * s ξ(δ) 与 ξ(δ ) 都非 0 的充要条
件, δ 中的最后一条边到达时, 中的两条边均被采样, 而 δ 中的最后一条边到达时, s 中的两条边也都均被采样.
s
*
∗
* ∗ s∪ s 的 ∗ p(4)(注意这
s
若 δ 和 δ 没有公共边, 则 和 s 也没有交集, 要达成上述条件, 需要 4 条边都被采样, 概率为