Approximate Graph Stream Triangle Counting Algorithm Based on Sliding Window Model with High Accuracy
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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%.

    Reference
    Related
    Cited by
Get Citation

苟向阳,邹磊,于旭.高精度滑动窗口模型下的图流三角形近似计数算法.软件学报,2025,36(9):4349-4372

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:January 30,2024
  • Revised:May 05,2024
  • Adopted:
  • Online: December 31,2024
  • Published: September 06,2025
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063