Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00245
Triangle Sparsifiers
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
|
Journal Supporters
|