标题： DTC：完全动态图流中的实时准确分布式三角形计数 显示英文标题

标题： DTC: Real-Time and Accurate Distributed Triangle Counting in Fully Dynamic Graph Streams

摘要： 三角计数是图挖掘中的基础问题，对于分析任意边顺序的图流至关重要。 然而，由于现实世界图流的规模庞大，精确计数变得不切实际。 为了解决这个问题，已经开发了近似算法，但现有的分布式流算法缺乏适应性，并且在处理边删除时遇到困难。 在本文中，我们提出了DTC，一种新型的单次遍历分布式流算法家族，用于完全动态图流中的全局和局部三角形计数。 我们的DTC-AR算法在无需预先了解图大小的情况下准确估计三角形数量，利用多机资源。 此外，我们引入了DTC-FD，一种专为完全动态图流设计的算法，结合了边的插入和删除。 通过随机配对和未来边插入补偿，DTC-FD在多台机器上实现了无偏且准确的近似。 实验结果表明，相比基线方法有显著改进。 DTC-AR最多提高了$2029.4\times$和$27.1\times$的准确性，同时保持了准确性和存储空间之间的最佳平衡。 DTC-FD将估计误差减少了最多$32.5\times$和$19.3\times$，并与图流大小成线性比例扩展。 这些发现突显了我们所提出算法在解决现实场景中三角形计数问题上的有效性。 源代码和数据集已发布并可在\href{https://github.com/wayne4s/srds-dtc.git}{https://github.com/wayne4s/srds-dtc.git}获取。 显示英文摘要

摘要： 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}.