Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
Charalampos E. Tsourakakis, Mihail N. Kolountzakis, and Gary L. Miller
Vol. 15, no. 6, pp. 703-726, 2011. Regular paper.
Abstract 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 sparsified graph G′ and return the number of triangles found in G′ 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))/(t1/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:
Submitted: January 2011.
Reviewed: July 2011.
Revised: September 2011.
Accepted: October 2011.
Final: October 2011.
Published: October 2011.
Communicated by Dorothea Wagner