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

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

(T − N,T] 之内的有效三角形, 其 3 条边的时间戳都在区
在 (T − N,T] 之内的有效三角形. 反之, 对于一个时间戳在
间 (T − N,T] 内, 也就是在滑动窗口中, 因此这 3 条边都在快照图中, 该三角形也一定在快照图中.
(T − N,T] 之内的有效三角形的数目. 为实现这一目标, CBS 使
为计算快照图中的三角形, 需要计数时间戳在
用 SWTC 算法维护滑动窗口内的无偏样本集合, 同时使用采样前计数策略估算时间戳落在每一个区间内的有效
三角形的数目. 之后将与滑动窗口相交的区间内的有效三角形数目加和, 这些三角形是时间戳在 (⌊Td/N⌋× N/d − N,T]
(T − N,T] 内的有效三角形数目的近似值. 由于每个区间的起点和终点是
内的有效三角形. 使用它来作为时间戳在
固定的, 计数区间内的有效三角形数目时不需要处理数据过期.
在图 6 中, 时间戳在区间 3, 即 (6,9] 中的有效三角形有 2 个, 分别是 [(v 6 ,v 8 ),(v 1 ,v 8 ),(v 1 ,v 6 )] 和 [(v 1 ,v 7 ),(v 1 ,v 8 ),
(9,12] 中的有效三角形有 1 [(v 1 ,v 8 ),(v 1 ,v 2 ),(v 2 ,v 8 )]. 目前还没有时间戳在区
(v 7 ,v 8 )], 时间戳在区间 4, 即 个, 也就是
间 5 中的三角形, 但是需要注意的是, 时间戳在一个区间内的有效三角形不一定只包含该区间内的边, 例如三角形
[(v 6 ,v 8 ),(v 1 ,v 8 ),(v 1 ,v 6 )] 中, 边 (v 1 ,v 8 ) 和边 (v 1 ,v 6 ) 在区间 4 中, 但是由于边 (v 6 ,v 8 ) 在区间 3 中且其时间戳最小, 所以
该三角形的时间戳依然在区间 3 中.
算法 1 给出了 CBS 算法处理图流中一条新边的流程.

算法 1. CBS 处理图流新边.
输入: 图流中的新边 e = (v i ,v j ), 样本图 G s , 三角形计数器 τ 0 τ d ;
–
输出: 更新后的样本图和三角形计数器.

//计数新边在样本图中构成的三角形
1. ∆ s = ∅
2. for v k ∈ G s .FindNeighbor(v i )∩G s .FindNeighbor(v j ) do
3. δ = [(v i ,v j ),(v i ,v k ),(v j ,v k )]
4. δ.ts = min{(v i ,v j ).ts,(v i ,v k ).ts,(v j ,v k ).ts}
5. ∆ s = ∆ s ∪{δ}
//增加每个三角形所在区间内的三角形计数器
6. for each δ ∈ ∆ s do
⌊ ⌋
Td N
7. l = ×
N d
8. if δ.ts > l then
9. x = 0
10. else
⌊ ⌋
(l−δ.ts)d
11. x = +1
N
1
12. τ x + =
p(2)
13. Gs.TrySample(e) //对新边运行采样算法
CBS 维护 d +1 个三角形计数器 τ 0 τ d , 分别记录与滑动窗口相交的 d +1 个区间内的有效三角形数量的估算
–
值, 初始值全部为 0. 其中最新的区间编号为 I 0 , 其三角形数目估算值保存在计数器 , 而倒数第 2 个区间则编号
τ 0
e
为 I 1 , 其三角形数目估算值保存在计数器 , 依次类推. 对于图流中的一条新边 e = (v i ,v j ), CBS 算法首先查找 在
τ 1
样本图 G s 中形成的三角形集合, 如算法 1 的第 1–5 行所示. 算法寻找点 v i 和 v j 在 G s 中的每一个共同邻居 , 也就
v k
是满足 (v i ,v k ) ∈ G s 且 (v j ,v k ) ∈ G s 的点 , 算法将三角形 [(v i ,v j ),(v i ,v k ),(v j ,v k )] 加入样本图中形成的三角形集合 ,
v k
∆ s
并将其时间戳设置为 3 条边时间戳的最小值. 需要注意的是, 算法虽然查找了 e 可以在 G s 中产生的三角形, 但是
并不把 e 加入 G s , e 是否能成为样本图中的样本边, 需要在进行三角形计数之后再由采样算法来决定. 然后, 算法