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

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

e
时间戳最大的边为 e, 其时间戳为 mt(δ). 若 到达时, 其他两条边均在样本图中, 则 ξ(δ) 取 1/p(2) mt(δ) , 否则取 0. 注
意由于滑动窗口中边数和样本图的大小随着时间在不断变化, 所以滑动窗口中任意两条边被加入样本图的概率
p(2) 也在不断变化, 而 p(2) mt(δ) 则表示 mt(δ) 时刻 p(2) 的值. ξ(δ) 变量代表了 CBS 算法中三角形 δ 给计数器 带来
τ i
δ
e
的增量. ξ(δ) 非 0 的充要条件是三角形 δ 的最后一条边 到达时, 其他两条边已在样本图中, 这时 会被 CBS 算法
的三角形搜索流程搜索到 (算法 1 的第 1–5 行), 而 ξ(δ) 的取值 1/p(2) mt(δ) 则是在 δ 被搜索到之后, CBS 算法对于 δ
的时间戳所在区间内的计数器的增量 (算法 1 第 7–11 行, 注意算法 1 中省略了 p(2) 的时间上标, 事实上使用的正
是边 e 到达时刻的 p(2) 值, 也就是 p(2) mt(δ) ). 综上所述, ξ(δ) 表明了 CBS 算法运行时是否会搜索到三角形 δ, 以及搜
∑
索到的情况下对于计数器 τ i 的增加值. 因此可以得出 τ i = ξ(δ). 由于 CBS 算法保证了样本图是滑动窗口内
δ∈∆ i
边的无偏样本, 因此可知 ξ(δ) 取 1/p(2) mt(δ) 的概率, 也就是 δ 的前两条边被采样的概率, 正是 p(2) mt(δ) . 所以有:

)
(∑ ∑ ∑ 1
E(τ i ) = E ξ(δ) = E (ξ(δ)) = × p(2) mt(δ) = |∆ i | (4)
δ∈∆ i δ∈∆ i δ∈∆ i p(2) mt(δ)
因此:

∑ d ∑ d
E (τ int ) = E(τ i ) = |∆ i | = |∆ ind | (5)
i=0 i=0
其中, ∆ ind 表示与滑动窗口相交的区间内的有效三角形集合.
然后分析 τ exp . 类似上文方法, 假设 ∆ exp 表示区间 I d 内的过期有效三角形的集合. 对于每一个三角形 δ ∈ ∆ exp ,
设置一个变量 ξ(δ). 假设 δ 中时间戳最小的边为 e, 结合有效三角形时间戳的定义, 可知 e 的时间戳就是 δ.ts. 若 e 恰
好过期时 (也就是 δ.ts+ N 时刻), δ 中的所有 3 条边均在样本图中, 则 ξ(δ) 取 1/p(3) δ.ts+N , 否则取 0, 其中 p(3) δ.ts+N 表
δ.ts+ N 时刻滑动窗口中任意 3 ξ(δ) 取
示 条边被加入样本图的概率. 由于样本图是滑动窗口内边的无偏样本, 可知
∑
1/p(3) δ.ts+N 的概率即为 p(3) δ.ts+N . 而结合 ETM 算法的流程, 可知 ξ(δ) 代表的是 τ exp = ξ(δ). 所以:

δ∈∆ exp
(∑ ) ∑ ∑ 1
E(τ exp ) = E ξ(δ) = E (ξ(δ)) = × p(3) δ.ts+N = ∆ exp (6)

δ∈∆ exp δ∈∆ exp δ∈∆ exp p(3) δ.ts+N
因此, 有:

( )

E (τ) = E (τ int )− E τ exp = |∆ ind |− ∆ exp (7)

而 |∆ ind |− ∆ exp 即为滑动窗口中的三角形数量 |∆|. 因此 E (τ) = |∆|, CBS 算法是无偏估算.

3.3.2 方差分析
接下来分析 CBS 算法的方差并和 SWTC 算法对比. 滑动窗口中的边数是随着图流流量而不断变化的, CBS
算法的方差不仅受到当前滑动窗口中的边数和快照图的拓扑结构的影响, 还会受到图流流量历史变化的积累影
响. 这导致在真实场景下难以给出 CBS 方差的分析结果. 因此, 在这里考虑一种简化的场景: 图流的流量是稳定
的, 不会随着时间而改变, 这种情况下, 滑动窗口中的边数 |W|, CBS 和 SWTC 算法采样出的样本边的数目 m, 以及
( )/( )
m |W|
滑动窗口中任意 i 条边被加入样本集的概率 p(i) = 都是稳定值.
i i
(1) SWTC 方差分析
首先分析 SWTC 算法的方差. 类比上文的无偏性分析部分, 给滑动窗口中的每个三角形 δ 赋予一个变量
χ(δ), 该变量表示的是 SWTC 算法中, 三角形 δ 为 SWTC 中三角形总数估算值带来的增量. 若查询时刻, δ 的 3
条边均在样本集中时, χ(δ) = 1/p(3). 这时 δ 会被统计为样本图中的三角形, 而 SWTC 算法最终以样本图中的三
角形数目除以 p(3) 作为滑动窗口中三角形总数的估算值, 所以 δ 给三角形总数估算值带来了 1/p(3) 的增加量.
而反之, 若 δ 任意一条边不在样本集中, 则 χ(δ) = 0, 因此可知 SWTC 对于滑动窗口内三角形数目的估算值为:

∑
τ swtc = χ(δ) (8)
δ∈∆
其中, ∆ 为滑动窗口中三角形的集合. 因此其方差可以如下分析:

(∑ ) ∑ ∑ ∑
∗
∗
Var(τ swtc ) = Var χ(δ) = Cov(χ(δ),χ(δ )) = Var(χ(δ))+ Cov(χ(δ),χ(δ )) (9)
δ∈∆ δ,δ ∗ ∈∆ δ∈∆ δ,δ ∗ ∈∆,δ,δ ∗