Approximately Counting Triangles in Sublinear Time

Abstract

We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a {\em sublinear-time\/} algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex-pair queries and neighbor queries. We show that for any given approximation parameter $0<\epsilon <1$, the algorithm provides an estimate $\hat{t}$ such that with high constant probability, $(1-\epsilon )\cdot t<\hat{t}<(1+\epsilon )\cdot t$, where $t$ is the number of triangles in the graph $G$. The expected query complexity of the algorithm is $\left(\frac{n}{t^{1/3}}+\min \left\{m,\frac{m^{3/2}}{t}\right\}\right)\cdot \mathrm{poly}(\log n,1/\epsilon )$, where $n$ is the number of vertices in the graph and $m$ is the number of edges, and the expected running time is $\left(\frac{n}{t^{1/3}}+\frac{m^{3/2}}{t}\right)\cdot \mathrm{poly}(\log n,1/\epsilon )$. We also prove that $\Omega \left(\frac{n}{t^{1/3}}+\min \left\{m,\frac{m^{3/2}}{t}\right\}\right)$ queries are necessary, thus establishing that the query complexity of this algorithm is optimal up to polylogarithmic factors in $n$ (and the dependence on $1/\epsilon$).

To appear in the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015)

References in corpus (1)

• Community structure and scale-free collections of Erdös-Rényi graphs

Cited by in corpus (1)

• A Comparative Study on Exact Triangle Counting Algorithms on the GPU