软件学报

作者：苟向阳，邹磊，于旭

单位：苟向阳，香港中文大学 系统工程与工程管理系, 香港 999077;北京大学 王选计算机研究所, 北京 10087111,邹磊，北京大学 王选计算机研究所, 北京 10087102,于旭，香港中文大学 系统工程与工程管理系, 香港 99907703

关键词：图流;三角形计数;近似算法

基金：国家自然科学基金(61932001, U20A20174); 香港研资局优配研究金 (14205520)

近年来, 图流分析在研究领域和工业领域都变得愈发重要. 图流是从数据源持续高速到达的边序列, 这些边组成了一个不断变化的动态图. 在图流上可以进行多种不同的分析, 而三角形计数是其中最基础的操作之一. 由于图流数据规模大, 更新速度高, 在图流上进行精确三角形计数效率较低, 而且并不必要. 因为大部分三角形计数应用都允许一定的误差, 所以, 图流上的近似三角形计数一直都是研究热点之一. 研究基于采样的滑动窗口模型下的图流近似三角形计数. 滑动窗口模型只关注最近到达的图流数据, 较早的图流数据被认定为过期. 它被广泛应用于不同的工业场景和研究工作中. 将一种“采样前计数”的方法与该问题场景下最新的算法结合, 并提出一套策略以应对由于边过期产生的困难. 使用真实数据集展开广泛的实验以测试提出的CBS算法. 实验结果表明, CBS相比目前最好的工作, 估算误差降低了70%以上.

来源：2025年第9期

《软件学报》期刊编辑部

查看软件学报杂志2025年第9期