{"ID":2878136,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.19057","arxiv_id":"2508.19057","title":"DTC: Real-Time and Accurate Distributed Triangle Counting in Fully Dynamic Graph Streams","abstract":"Triangle counting is a fundamental problem in graph mining, essential for analyzing graph streams with arbitrary edge orders. However, exact counting becomes impractical due to the massive size of real-world graph streams. To address this, approximate algorithms have been developed, but existing distributed streaming algorithms lack adaptability and struggle with edge deletions. In this article, we propose DTC, a novel family of single-pass distributed streaming algorithms for global and local triangle counting in fully dynamic graph streams. Our DTC-AR algorithm accurately estimates triangle counts without prior knowledge of graph size, leveraging multi-machine resources. Additionally, we introduce DTC-FD, an algorithm tailored for fully dynamic graph streams, incorporating edge insertions and deletions. Using Random Pairing and future edge insertion compensation, DTC-FD achieves unbiased and accurate approximations across multiple machines. Experimental results demonstrate significant improvements over baselines. DTC-AR achieves up to $2029.4\\times$ and $27.1\\times$ more accuracy, while maintaining the best trade-off between accuracy and storage space. DTC-FD reduces estimation errors by up to $32.5\\times$ and $19.3\\times$, scaling linearly with graph stream size. These findings highlight the effectiveness of our proposed algorithms in tackling triangle counting in real-world scenarios. The source code and datasets are released and available at \\href{https://github.com/wayne4s/srds-dtc.git}{https://github.com/wayne4s/srds-dtc.git}.","short_abstract":"Triangle counting is a fundamental problem in graph mining, essential for analyzing graph streams with arbitrary edge orders. However, exact counting becomes impractical due to the massive size of real-world graph streams. To address this, approximate algorithms have been developed, but existing distributed streaming a...","url_abs":"https://arxiv.org/abs/2508.19057","url_pdf":"https://arxiv.org/pdf/2508.19057v2","authors":"[\"Wei Xuan\",\"Yan Liang\",\"Huawei Cao\",\"Ning Lin\",\"Xiaochun Ye\",\"Dongrui Fan\"]","published":"2025-08-26T14:16:43Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false,"code_links":[{"ID":610453,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_id":2878136,"paper_url":"https://arxiv.org/abs/2508.19057","paper_title":"DTC: Real-Time and Accurate Distributed Triangle Counting in Fully Dynamic Graph Streams","repo_url":"https://github.com/wayne4s/srds-dtc.git","is_official":false,"mentioned_in_paper":false,"mentioned_in_github":true,"github_stars":0}]}