A space efficient streaming algorithm for triangle counting using the birthday paradox
A space efficient streaming algorithm for triangle counting using the birthday paradox
复制标题
DOI：
10.1145/2487575.2487678
复制
发表时间：
2012-12
期刊：
影响因子：
--
通讯作者：
Madhav Jha;Seshadhri Comandur;Ali Pinar
中科院分区：
文献类型：
--
作者：
Madhav Jha;Seshadhri Comandur;Ali Pinar
我们设计了一种空间高效的算法，该算法只需一次通过边流给出的图就可以逼近传递性(全局聚类系数)和总三角形计数。我们的程序是基于经典的概率结果--生日悖论。当传递性不变且边多于楔形(这是社会网络的常见属性)时，我们可以证明我们的算法需要O(√n)空间(n为顶点数)来提供准确的估计。我们在各种真实图上进行了一组详细的实验，并证明了算法的内存需求只占图的一小部分。例如，即使对于一个有2亿条边的图，我们的算法也只存储了6万条边来提供准确的结果。作为一种单遍流传输算法，我们的程序还通过存储极少的边来实时估计图的传递性/三角形的数量。
We design a space efficient algorithm that approximates the transitivity (global clustering coefficient) and total triangle count with only a single pass through a graph given as a stream of edges. Our procedure is based on the classic probabilistic result, the birthday paradox. When the transitivity is constant and there are more edges than wedges (common properties for social networks), we can prove that our algorithm requires O(√n) space (n is the number of vertices) to provide accurate estimates. We run a detailed set of experiments on a variety of real graphs and demonstrate that the memory requirement of the algorithm is a tiny fraction of the graph. For example, even for a graph with 200 million edges, our algorithm stores just 60,000 edges to give accurate results. Being a single pass streaming algorithm, our procedure also maintains a real-time estimate of the transitivity/number of triangles of a graph, by storing a miniscule fraction of edges.