| 摘要: |
| 近年来, 图流分析在研究领域和工业领域都变得愈发重要. 图流是从数据源持续高速到达的边序列, 这些边组成了一个不断变化的动态图. 在图流上可以进行多种不同的分析, 而三角形计数是其中最基础的操作之一. 由于图流数据规模大, 更新速度高, 在图流上进行精确三角形计数效率较低, 而且并不必要. 因为大部分三角形计数应用都允许一定的误差, 所以, 图流上的近似三角形计数一直都是研究热点之一. 研究基于采样的滑动窗口模型下的图流近似三角形计数. 滑动窗口模型只关注最近到达的图流数据, 较早的图流数据被认定为过期. 它被广泛应用于不同的工业场景和研究工作中. 将一种“采样前计数”的方法与该问题场景下最新的算法结合, 并提出一套策略以应对由于边过期产生的困难. 使用真实数据集展开广泛的实验以测试提出的CBS算法. 实验结果表明, CBS相比目前最好的工作, 估算误差降低了70%以上. |
| 关键词: 图流 三角形计数 近似算法 |
| DOI：10.13328/j.cnki.jos.007256 |
| 分类号: |
| 基金项目:国家自然科学基金(61932001, U20A20174); 香港研资局优配研究金 (14205520) |
|
| Approximate Graph Stream Triangle Counting Algorithm Based on Sliding Window Model with High Accuracy |
|
GOU Xiang-Yang1,2, ZOU Lei2, YU Xu1
|
|
1.Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Hong Kong 999077, China;2.Wangxuan Institute of Computer Technology, Peking University, Beijing 100871, China
|
| Abstract: |
| In recent years, graph stream analysis has gained increasing importance in both research and industry. A graph stream is a continuous sequence of edges received from a data source at a high speed. Those edges form a dynamic graph that is continuously changing. Various analyses can be performed on graph streams. Among them, triangle counting is one of the most basic operations. However, the large volume and high update speed of graph streams make it inefficient to count triangles accurately on them. It is also unnecessary, as most applications for triangle counting can tolerate small errors. Therefore, approximate triangle counting in graph streams has been a hot research topic. This study focuses on sample-based approximate triangle counting in graph streams with a sliding window model. Sliding window models focus on the most recent edges in a graph stream and consider older edges as expired. They are widely applied in various industrial scenarios and research. This study combines a count-before-sample strategy with the state-of-the-art approximate triangle counting algorithm and designs a set of novel strategies to deal with the difficulty brought by edge expiration. Extensive experiments are conducted on real-world datasets to evaluate the proposed algorithm. Results prove that the algorithm decreases the estimation error of the state-of-the-art method by more than 70%. |
| Key words: graph stream triangle counting approximate algorithm |
