Revisiting Wedge Sampling for Triangle Counting
Revisiting Wedge Sampling for Triangle Counting
复制标题
DOI：
10.1145/3308558.3313534
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Ata Turk;Duru Türkoglu
中科院分区：
文献类型：
--
作者：
Ata Turk;Duru Türkoglu
大量图的三角形计数可以提供关于这些图模型的网络结构的重要信息。精确的三角形计数可能是昂贵的，因此研究人员提出了许多近似方法。最先进的三角形计数近似技术依赖于楔形（双路径）采样。在本文中，我们提供了一种机制，显着提高三角形计数的楔形采样。我们通过消除不太可能参与三角形的楔形来缩小采样空间。在大规模真实世界图上的实验表明，该机制提供了五到几百倍的采样空间减少。与最先进的方法相比，它需要低至100倍的采样才能提供相同的精度，或者在使用相同的采样率时，误差低至8倍。
Triangle counts of massive graphs can provide important information regarding the structure of the networks these graphs model. Exact triangle counting can be expensive and thus researchers have proposed a number of approximation approaches. The state-of-the-art triangle count approximation techniques depend on wedge (two-path) sampling. In this paper we offer a mechanism to significantly improve wedge sampling for triangle counting. We shrink the sampling space by eliminating wedges that are less likely to participate in triangles. Experiments over large-scale real-world graphs show that proposed mechanism provides five- to a few hundred-folds sampling space reduction. When compared against the state-of-the-art approaches, it requires as low as ~ 100 × less sampling to provide the same accuracy, or makes as low as ~ 8 × less error when used with the same sampling ratio.