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

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

的三角形数目.
图 1 展示了一个图流、滑动窗口和快照图的示例, 其中滑动窗口长度为 6, 当前时刻为 13, 因此只有时间戳在
(7,13] 内的边会被包含在滑动窗口中. 在快照图中也标注了每条边的时间戳. 下文中, 在不引起歧义的情况下混合
使用“滑动窗口中的三角形数目”与“快照图中的三角形数目”.

滑动窗口

t=1 t=3 t=5 t=6 t=7 t=8 t=10 t=11 t=12 t=13 t=13
(v 1 , v 4 ) (v 2 , v 3 ) (v 5 , v 6 ) (v 3 , v 5 ) (v 6 , v 8 ) (v 1 , v 7 ) (v 7 , v 8 ) (v 1 , v 8 ) (v 1 , v 6 ) (v 2 , v 8 ) (v 1 , v 2 ) 图流
13
v 2 v 8
13 11 10 快照图
12 8
v 6 v 1 v 7
图 1 图流示例

在图流中, 同一条边 (v i ,v j ) 可能在不同时刻多次出现, 这种情况被称为重复边 (duplicate edge). 在三角形计数
问题中, 有二项计数 (binary counting) 和带权计数 (weighted counting) 两种处理重复边的方法, 定义如下.
● 二项计数 (binary counting): 计数由不同边组成的互异三角形的数目, 相同两点间的多条重复边不会重复参
与计数.
● 带权计数 (weighted counting): 计数包含重复边的所有三角形的数目, 相同两点间的重复边会被视为独立边,
可以组成不同的三角形.
图 2 展示了一个含重复边的快照图, 图中边 (v 1 ,v 8 ) 在滑动窗口中出现两次, 时间戳分别为 9 和 12. 边 (v 7 ,v 8 )
也出现两次, 时间戳分别为 8 和 10. 若使用二项计数, 图中只有一个三角形. 而使用带权计数, 则有 4 个三角形, 分别为
,
,
1 1 1 2 2 1 2 2 1
[(v 1 ,v 8 ) ,(v 7 ,v 8 ) ,(v 1 ,v 7 )] [(v 1 ,v 8 ) ,(v 7 ,v 8 ) ,(v 1 ,v 7 )] [(v 1 ,v 8 ) ,(v 7 ,v 8 ) ,(v 1 ,v 7 )] 和 [(v 1 ,v 8 ) ,(v 7 ,v 8 ) ,(v 1 ,v 7 )], 其中 (v 1 ,v 8 )
1
2
2
和 (v 1 ,v 8 ) 分别表示和间两条不同的重复边, (v 7 ,v 8 ) 和 (v 7 ,v 8 ) 同理.

v 7
13 8, 10
11 9, 12
v 6 v 1 v 8
图 2 含重复边的快照图

本文使用带权计数方法. 一方面, 采样前计数策略不能与二项计数结合. 二项计数要求在计数三角形时过滤掉
重复边, 而采样前计数策略需要对图流中每条新边进行三角形计数. 而我们无法判断这条新边是否为重复边. 使用
采样前计数策略的现有工作也都采用了带权计数 [17–19] . 另一方面, 带权计数在应用中也更加常见. 例如在社交网络
中进行社区检测时, 用户之间重复通信的次数显然是寻找活跃社区的重要指标, 因此在计数三角形时, 应当采用考
虑了重复通信 (重复边) 的带权计数.
由于带权计数不需要过滤重复边, 无论图流中是否存在重复边, 算法都不需要做出改变. 出于论述简单考虑,
下文不再考虑重复边问题, 假设图流中的边都是互异的. 但是在实验中, 也测试了算法在带有重复边的数据集上的
效果.
此外, 本文中使用的采样前计数策略之前主要被使用于全动态模型. 在此也给出全动态模型的定义, 以便和滑
动窗口模型进行区分.
● 全动态模型 (fully dynamic model): 在全动态模型中, 图流上的每一个数据项除了包含边 (v i ,v j ) 以及时间戳
t 外, 还包含一个操作 ( −), 用于区分该数据项为边添加或者边删除. 当 o = + 时, 表示加入一条新边, 而
o o = + 或
当 o = − 时, 表示删除之前图流中出现的一条边. 在全动态模型中, 快照图中包含图流中目前所有未被删除的边.
全动态模型中的边删除是由新数据项触发的, 这样的删除被称为显式删除 (explicit deletion), 而滑动窗口中的