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

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

the estimation error of the state-of-the-art method by more than 70%.
Key words: graph stream; triangle counting; approximate algorithm

图是一种用于表示大规模实体和实体之间关联关系的数据形式, 被广泛应用在社交网络, 知识图谱, 电子商务
等领域. 近年来, 随着互联网的不断发展, 图数据的动态性不断提高. 在很多应用中, 图数据被组织为图流的形式.
图流是一个持续到达的数据项组成的序列, 每个数据项表示图中的一条边, 以及边上的时间戳等信息, 这些数据项
组成了一个持续变化的动态图. 例如, 在社交网络中, 用户通信数据便组成了一个持续更新的图流. 其中每一个点
代表一个用户, 而每一条边表示两个用户之间的一次通信, 而边上的时间戳标识了通信发生的时间. 这些通信数据
不断产生, 便组成了一个持续到达的边序列. 再例如, 网络通信中, 每个数据包可以被建模为以源 IP 和目的 IP 为
顶点的一条边, 而这些数据包便组成了一个持续不断的图流. 图流数据具有更新速度快, 数据规模大的特点. 在大
型社交网络, 例如 Twitter 中, 每秒产生的通信数据可以达到 1 万条以上, 而图流数据总规模可以达到数亿甚至数
十亿 [1] , 而在大型数据中心, 每个路由器每秒需要处理数十万的数据包 [2] .
虽然图流数据是持续不断到达的, 实际应用往往只关注最近的数据. 对这些数据的分析有助于跟进最新的热
门话题或者及时发现刚刚发生的异常行为. 因此, 很多应用使用滑动窗口模型 [3] 以抽取最近一段时间的数据, 例如
时间戳在最近 72 h 内的边, 将其视为有效. 而更早的数据则被视为过期. 例如, 根据此前的研究工作 [4] , 阿里巴巴公
司使用滑动窗口模型维护最近 72 h 内的电商交易数据, 在其中执行查询算法以实时检测洗钱行为. 而更早的数据
则被不被纳入分析.
三角形计数是最常见的图数据分析方法之一, 在社区发现 [5] , 话题检测 [6] , 异常检测 [7] 等问题 [8–11] 中都发挥着
重要作用. 在图流场景下, 需要在图流数据不断更新的过程中实时维护三角形数目. 由于图流数据的更新速度很
高, 精确三角形计数的速度难以满足应用需求. 另一方面, 精确算法要求在内存中完整保留图流数据, 在图流规模
达到数亿甚至 10 亿的情况下, 这对服务器是一个沉重的负担. 而且一些应用场景需要在路由器和交换机等嵌入式
设备中进行网络测量 [12] , 这些设备中的内存资源稀缺, 使得精确算法无法部署. 高内存占用也限制了使用 GPU,
ASIC 等新硬件加速的可能性. 此外, 三角形计数的相关应用都可以允许一定的误差, 这使得图流上的近似三角形
计数称为近年来的研究热点之一. 本文将研究滑动窗口模型下的图流上的三角形近似计数算法.
现有的图流三角形近似计数算法 [13–15] 往往基于采样估算, 也就从图流中采样一部分的边组成一个样本图, 基
于样本图中的三角形数目来估算完整图流中的三角形数目, 而没有被采样的边将不被保存. 目前最新的滑动窗口
模型下的三角形近似计数算法是 Gou 等人 [16] 提出的 SWTC 算法, 该算法使用限定大小的存储空间维护一个滑动
窗口中的无偏样本图, 并对滑动窗口中的完整边数进行估算, 之后根据估算出的完整边数和样本图的大小, 将样本
图中的三角形数目按比例放大以估算滑动窗口中的三角形数目.
本文进一步提出将一种“采样前计数”的策略与 SWTC 算法结合以提升其精确度, 提出了新的滑动窗口模型
下的图流估算方法 CBS. 采样前计数策略目前已被广泛应用于全动态模型下的三角形近似计数算法 [17–19] . 与滑动
窗口模型不同, 全动态模型假设图流中包含边添加和边删除两种操作, 前者在图流数据中加入新边, 而后者删除一
条已有的边, 所有未被删除的边均被认为有效. 采样前计数策略根据图流中每一条新加入的边在样本图中形成的
三角形数目, 估算其在完整图流中形成的新三角形的数目, 之后再决定是否采样该边. 通过累计每一条新边产生的
新三角形数目, 算法可以得到完整图流中三角形总数的估算值. 对于图流中的边删除操作, 算法使用类似的方法估
算该次删除导致的图流中三角形减少的数目, 将其从三角形总数中减去. 相比仅使用样本图中三角形数目的估算
方法, 采样前计数策略充分利用了未被采样的边的拓扑信息, 具有更高的估算精度.
然而, 将采样前计数策略从全动态模型迁移到滑动窗口模型时, 会在处理边过期时出现困难. 滑动窗口模型的
边过期和全动态模型的边删除存在差别. 全动态模型中的删除是显式的, 每一次边删除都来自图流中明确的指令
告知. 因此算法可以得知何时删除了哪条边. 而滑动窗口模型中的边过期是隐式的, 算法在图流中只会收到新添加
的边, 而这些边具有自己的时间戳. 随着时间推移, 当一条边的时间戳不再处于滑动窗口中时, 它便会过期. 这样的
过期不会有指令告知. 图流数据是被实时处理的, 一条边到达时若未被采样, 便不会被保存. 对于这样的边, 我们无