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

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

*
* ξ(δ ) 都非 的概率需要
里我们做了一定近似, 忽略了样本边被替换的情况). 若 δ 与 δ 有一条公共边 e, 则 ξ(δ) 与 0
*
* ∗ ∗ ∗ ξ(δ ) 都非
s
根据组成 δ 与 δ 的 5 条边的时间顺序而定. 当 e ∈ s 且 e ∈ s 时, 和 s 有交集, s∪ s 中只有 3 条边, 与 0
的充要条件是这 3 条边被采样, 概率为 p(3), 否则, 概率依然为 p(4). 假设边的时间戳与拓扑无关时, e ∈ s 且 e ∈ s ∗
的概率为 8/15, 因此有:


 p(4)
∗
 δ与δ 没有公共边
 ,

 2
 p(2)

∗  (16)
E (χ(δ)χ(δ )) = 
 8× p(3)+7× p(4)


∗
 , δ与δ 有一条公共边

 2
15× p(2)

因此公式 (15) 可以进一步展开为:

( ) ( ) ( )
1 p(4) 8× p(3)+7× p(4)
Var(τ ind ) = ¯ ∆ −1 +2η −1 +2λ −1 (17)

p(2) p(2) 2 15× p(2) 2
¯
其中, |∆| 与 , d +1 个区间内的有效三角形数目, 没有公共边的互异三角形对的数目
¯ η ¯ λ 分别表示与滑动窗口相交的
¯
,
,
和有一条公共边的互异三角形对的数目, 当 d → K 时, 我们有 |∆| ≈ |∆| ¯η ≈ η ¯ λ ≈ λ.

( ) ( ) ( )
( ) 1 p(4) 8× p(3)+7× p(4)
Var(τ cbs ) ⩽ Var(τ ind )+Var τ exp ≈ Var(τ ind ) = |∆| −1 +2η −1 +2λ −1 (18)
p(2) p(2) 2 15× p(2) 2
m
i
r
为了直观对比 CBS 算法和 SWTC 算法的方差, 在 |W| 和 m 足够大的情况下, 将 p(i) 近似为 , 其中 r = , 此时有:
|W|

( ) ( )
1 1
Var(τ swtc ) = |∆| −1 +2λ −1 (19)
r 3 r

( ) ( )
1 1 8
Var(τ cbs ) ≈ |∆| −1 +2λ −1 × (20)
r 2 r 15
对比可以发现 Var(τ cbs ) < Var(τ swtc ). 在第 4 节中的实验也证实了以上分析.

3.3.3 空间复杂度分析
定理 3. 假设图流划分的子流数目为 K, CBS 算法的空间复杂度为 O(K), 而时间复杂度为 O(|E|K), 其中 |E| 为
图流中到达的总边数, 平均在图流中每一条边更新上的均摊复杂度为 O(K).
O(d), 而
证明: 与 SWTC 算法相比, CBS 算法新增的数据结构只有 d +1 个三角形计数器, 其空间占用为
SWTC 算法产生的样本图中的大小为 O(K), 实验设置中, d 是一个小于 K 的常数, 所以合计空间复杂度依然为
O(K). 在时间复杂度上, 每次在新边到达时, 我们需要计数它在样本图中产生的三角形数目, 这一过程需要计算该
O(K). 而仅当该边被采样时, 其过期时会再触发一次
边两个端点的邻居交集, 复杂度与样本图大小成正比, 也就是
三角形计数, 再次引入 O(K) 的代价. 因此, 图流中每条新边产生的时间代价为 O(K), 而图流中边到达的边总数为
|E| 时, 总计时间复杂度为 O(|E|K).

3.4 有向三角形计数
在上文中, 将三角形计数中的边都视为无向边, 这也是大部分现有工作的问题定义方式. 而考虑边方向后, 有
向三角形计数事实上属于一种更广泛的被称为范式计数 (motif counting) 的研究问题. 有向三角形可以被 7 种范
式, 如图 7 所示. 前 2 种范式只包含单向边, 后 5 种则包含单向边和双向边. 注意这里定义的双向边是被标记为双
向的单一边, 并非图流中两条反向边的组合, 否则其组成的范式将为四边范式而非三边的三角形范式. 此定义与之
前的工作相同 [14] . 本文的 CBS 算法和 SWTC 算法均可以扩展到有向三角形计数中, 只需要在算法计数三角形时
计数不同的有向三角形即可, 其他步骤和无向三角形计数相同.

A B C D E F G
图 7 不同的有向三角形范式