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 authored 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