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

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

枚举 ∆ s 中的每一个三角形, 根据其时间戳计算它所在的区间. 根据时间戳计算所属区间的方法如算法 1 的第
7–11 行所示. 假设三角形时间戳为 ts, 可以计算出最新的路径点为 l = ⌊Td/N⌋× N/d, 而该三角形所在的区间编号
则是:

 x = 0, ts > l


 ⌊ ⌋
 (l−ts)d (1)

 x = +1, ts ⩽ l

N

l
l
当 ts > l 时, 说明该时间戳在最新的区间, x = 0. 否则, 根据 ts 和 之间的距离计算, 当 ts ⩽ l 且和 之间的距离
l
不满一个区间长度, 也就是 N/d 时, 其在倒数第 2 个区间, x = 1. 而 ts 和 之间的距离在 1–2 倍的区间长度之间时,
其在倒数第 3 个区间, x = 2. 依次类推. 因此得到公式 (1).
此时, 该三角形所在的区间便是 I x , 将 τ x 增加 1/p(2), 其中 p(2) 表示滑动窗口中任意两条边被加入样本图的
( )/( )
m |W| m(m−1)
概率, 对于 SWTC 采样算法, 该值为 p(2) = = , 其中 |W| 和 m 分别为滑动窗口中的边数
2 2 |W|(|W|−1)
以及样本图中的边数, 前者可以通过 SWTC 算法估算. e 在快照图中产生的三角形被加入 ∆ s 的概率, 便是该三角
形除了 e 之外的两条边均被采样的概率, 也就是 p(2). 因此, 对于 ∆ s 中的每一个三角形, 需要将其所在区间的三角
1/p(2), 以此估算 的加入在该区间内产生的有效三角形的数量. 这也是采样前计数的基本思想. 我
e
形计数器增加
们会在第 3.3 节对此估算方法的无偏性进行详细证明. 最后, CBS 算法再调用 SWTC 算法的采样流程, 来尝试对 e
进行采样. 此采样过程中, e 可能会替换掉样本图中的一条原有样本边, 但不需要根据被替换出的样本边对三角形
计数器进行任何修改. 因为 CBS 的三角形计数器是通过估算每条新边到达时在快照图中增加的三角形数目来更
新的, 而不是像 SWTC 一样根据样本图中三角形数目更新, 样本边的换出不会对其造成影响.
算法 2 则给出了当时刻从 T 增加 ∆T 时处理过期数据的流程.
算法 2. CBS 处理过期数据.
–
输入: 当前时刻 T , 时间增量 ∆T , 样本图 G s , 三角形计数器 τ 0 τ d ;
输出: 删除过期数据后的样本图和三角形计数器.
⌊ ⌋ ⌊ ⌋
(T +∆T)d Td
1. y = −
N N
2. if y > 0 then
//经历了 y 个新区间, 后移旧区间的计数器
3. for i = d −y; i ⩾ 0; i−− do
4. τ i+y = τ i
//初始化前 y 个计数器, 用于计数新区间的三角形
5. for i = 0; i ⩽ min(d,y−1); i++ do
6. τ i = 0
7. 删除 G s 中时间戳不大于 T +∆T − N 的边
8. T = T +∆T

⌊(T +∆T)d/N⌋−⌊Td/N⌋ 的值, 如果其为 且大于 0, 则说明时间又经过了 y 个区间, 抛弃最
CBS 算法首先检查 y
早的 y 个区间 τ d−y+1 τ d 的三角形计数器, 并将其余的三角形计数器向后移动 y 位, 空出来的计数器 τ 0 τ y−1 则用
–
–
于在后续计数新增的 y 个区间的有效三角形数目, 将其初始化为 0. 之后算法查找样本图中所有的过期边, 也就是
T = T +∆T . 实际应用中, 该流程一般
时间戳不在 (T +∆T − N,T +∆T] 内的边, 将其删除. 最后算法更新当前时刻
T 并触发一次数据过期. 而在第 4 节的实验中, 由于本
由系统时钟触发, 每当时钟向前推进一个时间单元时, 更新
文使用的是历史图流数据集而非实时数据, 选择由数据驱动更新而非由系统时钟驱动. 具体来说, 按照时间戳顺序
T
处理图流数据, 并将当前时刻 T 设置为处理为已经处理的最大时间戳. 每当有新边读入时, 首先更新当前时刻 ,