Counting and Sampling Triangles from a Graph Stream
Counting and Sampling Triangles from a Graph Stream
复制标题
DOI：
10.14778/2556549.2556569
复制
发表时间：
2013-09
期刊：
影响因子：
--
通讯作者：
A. Pavan;Kanat Tangwongsan;Srikanta Tirthapura;Kun-Lung Wu
中科院分区：
文献类型：
--
作者：
A. Pavan;Kanat Tangwongsan;Srikanta Tirthapura;Kun-Lung Wu
本文提出了一种新的空间有效的算法计数和采样三角形-更一般地说，恒定大小的团-在一个大规模的图，其边缘作为流到达。与以前的工作相比，我们的算法产生显着的改善，这些基本问题的空间和时间复杂度。该算法实现简单，在大型图上具有很好的实用性能。
This paper presents a new space-efficient algorithm for counting and sampling triangles--and more generally, constant-sized cliques--in a massive graph whose edges arrive as a stream. Compared to prior work, our algorithm yields significant improvements in the space and time complexity for these fundamental problems. Our algorithm is simple to implement and has very good practical performance on large graphs.