Approximately Counting Triangles in Sublinear Time

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<ϵ<1$, the algorithm provides an estimate $\widehat{t}$ such that with high constant probability, $(1-ϵ)\cdot t<\widehat{t}<(1+ϵ)\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 {\rm poly}(\log n, 1/\epsilon)$,where$n$isthenumberofverticesinthegraphand$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 {\rm 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\mathrm{/}ϵ$).