Triangle counting in streamed graphs via small vertex covers
Triangle counting in streamed graphs via small vertex covers
复制标题
通过小顶点覆盖在流图中进行三角形计数
DOI：
10.1137/1.9781611973440.40
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Konstantin Kutzkov
中科院分区：
文献类型：
--
作者：
David García;Konstantin Kutzkov
我们提出了一个新的随机算法估计的三角形的数量在大规模的图形显示为一个流的边缘在任意顺序。它利用了这样一个事实，即从不同领域产生的图往往有小的顶点覆盖，这使我们能够减少三角形计数算法的空间使用和样本复杂度。该算法在边缘集上运行四次，并使用常数处理
We present a new randomized algorithm for estimating the number of triangles in massive graphs revealed as a stream of edges in arbitrary order. It exploits the fact that graphs arising from various domains often have small vertex covers, which enables us to reduce the space usage and sample complexity of triangle counting algorithms. The algorithm runs in four passes over the edge set and uses constant processing