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

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

为了解决这一问题, SWTC 采用了图流切片的策略. 它选择一系列的路径点 (landmark), 将图流切分为长度为
N 的定长片段. 在任意时刻 , 滑动窗口至多与最近的两个片段相交. 图 4 展示了一个示例. 当前时刻为 13, 滑动
T
(7,13], 和片段 (6,12] 以及片段 (12,18] 相交. 注意片段 3 是一个仍未结束的片段, 后续新到达的
窗口为 2, 即 3, 即
边仍会被加入该片段. 而等到 18 时刻, 滑动窗口将只与片段 3 相交.

滑动窗口

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 )
片段 1 片段 2 片段 3
图 4 SWTC 图流切片示例

β 和 . 例如在图 4
ϵ
在任意时刻, SWTC 记录在每个子流中记录最近两个片段 SL old 和 SL new 中优先级最高的边
中, 它保存片段 2 中优先级最高的边和片段 3 中目前优先级最高的边. 由于片段的起点和终点都是固定的, 在寻找
其中优先级最高的边时不需要处理边过期, 只需要从片段起点开始使用变量 ϵ 记录目前优先级最高的边, 在每次
ϵ
ϵ
ϵ
新边 e 到达时对比 e 和 的优先级, 并在 e 优先级更高时使用它替换 , 持续此操作直到片段终点. 对于 β 和 , 存在
下述 3 种情况, 如图 5 所示.

滑动窗口
情况 1 β ϵ
SL old SL new T
滑动窗口

情况 2 β ϵ
T
SL old SL new
滑动窗口
情况 3 β ϵ
T
SL old SL new
图 5 SWTC 子流采样的不同情况

情况 1: 滑动窗口与 SL old 和 SL new 同时相交, 且 β 和 同时在滑动窗口中, 这时选择二者中优先级较高的边,
ϵ
它一定是滑动窗口中优先级最高的边, SWTC 算法将其作为该子流中的样本边.
情况 2: 滑动窗口依然与 SL old 和 SL new 同时相交, 但是 β 已经过期. 若 G(β) > G(ϵ), SWTC 放弃在该子流中选择
G(β) > G(e) > G(ϵ) e 应当被选为样本边, 但是没有被保
.
样本边. 因为片段 SL old 中可能存在边 e, 其没有过期, 而且
ϵ
ϵ G(ϵ). 而 又
存. 若 G(β) ⩽ G(ϵ), SWTC 选择 作为样本边, 因为片段 SL old 中的边优先级都低于 G(β), 因此也低于
是片段 SL new 中优先级最高的边, 因此它是最近两个片段中优先级最高的边, 自然也是滑动窗口中优先级最高的
边. SWTC 将其选为样本边.
情况 3: 时间推移到路径点, 滑动窗口只和片段 SL new 相交. 这时 为滑动窗口中优先级最高的边, 算法将其选
ϵ
为样本边.
在情况 3 之后, 滑动窗口与新的片段相交, 当前的 SL new 变为 SL old , 情况返回第 1 种, 3 种情况交替出现.

作者证明了在任意时刻, 一个子流中获得有效样本的概率为 p = |W|/|SL new +SL old |. 其中 |W| 和 SL old +SL new | 分
别表示滑动窗口以及最近两个片段中的边数. 而 K 个子流中获取的样本边的总数期望值则为 pK.
● 三角形采样概率的计算: 由于 SWTC 算法维护的样本集是滑动窗口的无偏样本集, 作者证明了在任意时刻 T ,
( )/( )
m |W|
滑动窗口中任意 i 条边被加入样本集的概率为 p(i) = . 其中 m 表示 T 时刻样本边的数目. 因此, 滑动
i i