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

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

边过期则是随着时间推移自发发生的, 是一种隐式删除 (implicit deletion). 这导致在全动态模型中, 算法总是能够
知晓所有边删除, 而滑动窗口模型中, 若算法没有保存一条边, 则无法发现该边的过期. 这也导致了将采样前计数
策略用于滑动窗口模型时的困难.
本文使用采样算法进行三角形数目估算, 首先给出采样算法中的几个重要概念: 样本边、样本集和样本图.
● 样本边: 图流中的每条新边到达时, 采样算法会判断是否保存该边, 如果该边被保存, 便被称为样本边. 反之,
如果这条边没有被采样算法保存下来, 则被称为非样本边. 由于图流是实时处理的, 到达时未被保存的非样本边后
续无法再次被获取.
需要注意的是, 样本边也不是始终被保存的. 一方面, 样本边过期时会被算法删除, 另一方面, 近年来的三角形
近似计数算法, 例如 SWTC, TRIEST 和本文 CBS 等, 是固定空间消耗的, 它们的采样算法会限制样本边的总数. 因
此当一条新边被采样时, 另一条旧的样本边可能会被删除, 或者说旧样本边被新样本边替换了. 我们会在第 2.2 节
中详细介绍 SWTC 算法如何替换样本边.
● 样本集: 任意时刻, 所有样本边组成的集合被称为样本集.
● 样本图: 任意时刻, 所有样本边组成的图被称为样本图.

2 相关工作

大规模图数据上的三角形计数问题已经被研究了数十年. 相比精确计数算法 [20–24] , 近似估算算法 [25–28] 在时间
和空间上更加高效. 近年来在大规模图流数据上的三角形近似计数算法包括 Ahmed 等人 [13] 的通用图流采样和估
算框架, Pavan 等人 [14] 基于邻居采样的估算算法, Jha 等人 [29] 基于双边 (wedge) 采样的估算算法以及 Tsourakakis
等人提出的基于固定概率采样的三角形估算算法 [30] . 上述工作的一个主要缺陷是无法控制算法的空间占用, 也就
是说算法消耗的内存会随着图流更新变化, 且无法给出上限预测. 而之后由 De Stefani 等人 [17] 提出的 TRIEST 算法
可以将算法的空间占用控制在一个给定的阈值之内. TRIEST 使用了固定上限的蓄水池采样 (reservoir sampling),
并使用了随机配对 (random pairing) [31] 策略来在蓄水池采样中支持边删除, 因此 TRIEST 适用于全动态模型. 然而,
由于随机配对策略需要知晓每一次边删除, TRIEST 不适用于滑动窗口模型. 因为滑动窗口模型下算法无法知晓非
样本边的过期. 在该工作中, De Stefani 等人也首次提出了采样前计数策略, 但他们只将该策略运用在了不含边删
除的场景下, 作为 TRIEST 的一种更加精确但是应用场景受限的变体. 后续的工作 ThinkD [18] 进一步提出了将采样
前计数应用于含删除场景的方法, 提出了基于采样前计数且能够支持全动态模型的三角形估算算法. 后续工作如
WRS 等 [19,32] 则进一步对其进行了改进. 但是出于和 TRIEST 相同的原因, 这些算法都不适用于滑动窗口模型, 且
这些算法只能处理带权计数. Wang 等人 [15] 提出具有固定空间占用且适用于二项计数的三角形估算算法 PartitionCT,
但是他们的方法既不能处理全动态模型中的显式删除也不能处理滑动窗口模型中的边过期. Gou 等人 [16] 提出的
SWTC 算法则提出了适用于滑动窗口模型的三角形估算算法, 该算法基于权重采样方法, 具有固定空间占用, 且既
能处理带权计数又能处理二项计数. 近年来的最新工作也在研究了更多场景下的三角形近似计数问题, 例如,
Zhang 等人 [33] 研究了超图图流上的三角形近似计数问题, 超图是传统结构的一种变体, 其中的每条边可以包含多
个顶点. Yang 等人 [34] 研究了 Master-Worker-Aggregator 架构下的分布式场景下的三角形近似计数问题, 后续他们
又进一步研究了云计算场景下的分布式三角形近似计算问题 [35] . 此外, Wang 等人 [36] 将强化学习融入了采样算法
中, 提出了用于图流上的子图计数的近似算法, 该算法也适用于三角形计数. 他们使用强化学习为图流中每条边赋
予权重, 根据边权重进行带权采样, 权重越高的边在子图计数中的重要性越高, 被采样概率也越高. 之后他们根据
采样出的样本集进行子图计数. 然而, 该研究工作不能处理边过期, 无法应用于本文研究的滑动窗口模型. 下文将

对和本文密切相关的 SWTC 算法和采样前计数策略进行更详细的介绍. 此外, 我们也将介绍固定概率采样方法,
该方法是一种适用于滑动窗口模型的简单采样算法, 在多种已有工作中得到了应用. 但是其与最近几年的工作如
TRIEST 和 SWTC 相比, 具有无法控制空间占用的缺陷, 在空间紧张的情况下不易适用. 但是由于采样机制简单,
更新速度更高, 所以在空间较为宽裕的情况下可以作为替代方案. 在第 3.5 节中, 本文也将提出基于固定概率采样