Triangle Sparsifiers
Triangle Sparsifiers
复制标题
三角形稀疏器
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
G. Miller
中科院分区：
文献类型：
--
作者：
Charalampos E. Tsourakakis;M. N. Kolountzakis;G. Miller
在这项工作中，我们引入了三角形稀疏器的概念，即在三角形数量方面与原始图大致相同的稀疏图。这产生了一种具有强有力理论保证的实用三角形计数方法。例如，对于未加权图，我们展示了一种用于近似计算图 G 中三角形数量的随机算法，其过程如下：以概率 p 保持每条边独立，枚举 spar-sified 图 G (cid:48) 中的三角形，并返回在 G (cid:48) 中找到的三角形数量乘以 p − 3 。我们证明，在 G 和 p 的温和假设下，我们的算法以高概率返回三角形数量的良好近似值。具体来说，我们证明，如果 p ≥ max ( polylog( n )Δ t , polylog( n ) t 1 / 3 )，其中 n 、 t 、 Δ 和 T 分别表示 G 中的顶点数量、G 中三角形的数量、G 的边包含的三角形的最大数量以及我们的三角形计数估计，则 T 强烈集中在 t 周围：
In this work, we introduce the notion of triangle sparsifiers , i.e., sparse graphs which are approximately the same to the original graph with respect to the triangle count. This results in a practical triangle counting method with strong theoretical guarantees. For instance, for unweighted graphs we show a randomized algorithm for approximately counting the number of triangles in a graph G , which proceeds as follows: keep each edge independently with probability p , enumerate the triangles in the spar-sified graph G (cid:48) and return the number of triangles found in G (cid:48) multiplied by p − 3 . We prove that under mild assumptions on G and p our algorithm returns a good approximation for the number of triangles with high probability. Specifically, we show that if p ≥ max ( polylog( n )∆ t , polylog( n ) t 1 / 3 ), where n , t , ∆, and T denote the number of vertices in G , the number of triangles in G , the maximum number of triangles an edge of G is contained and our triangle count estimate respectively, then T is strongly concentrated around t :