file.pdf (251.64 kB)
Download file

Efficient Triangle Counting in Large Graphs via Degree-based Vertex Partitioning

Download (251.64 kB)
journal contribution
posted on 01.03.2014, 00:00 by Mihail N. Kolountzakis, Gary L. Miller, Richard Peng, Charalampos E. Tsourakakis

In this paper we present an efficient triangle counting algorithm which can be adapted to the semistreaming model [12]. The key idea of our algorithm is to combine the sampling algorithm of [31,32] and the partitioning of the set of vertices into a high degree and a low degree subset respectively as in [1], treating each set appropriately. We obtain a running time O(m+m3/2Δlogntϵ2) and an ε approximation (multiplicative error), where n is the number of vertices, m the number of edges and Δ the maximum number of triangles an edge is contained. Furthermore, we show how this algorithm can be adapted to the semistreaming model with space usage O(m1/2logn+m3/2Δlogntϵ2) and a constant number of passes (three) over the graph stream. We apply our methods in various networks with several millions of edges and we obtain excellent results. Finally, we propose a random projection based method for triangle counting and provide a sufficient condition to obtain an estimate with low variance.

History

Publisher Statement

© ACM, 2014. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published at http://doi.acm.org/10.1145/2628136.2628158

Date

01/03/2014

Usage metrics

Exports