ECCC-Report TR15-046https://eccc.weizmann.ac.il/report/2015/046Comments and Revisions published for TR15-046en-usMon, 17 Aug 2015 10:29:06 +0300
Comment 1
| An updated version is available on Arxiv. |
Talya Eden
https://eccc.weizmann.ac.il/report/2015/046#comment1http://arxiv.org/abs/1504.00954Mon, 17 Aug 2015 10:29:06 +0300https://eccc.weizmann.ac.il/report/2015/046#comment1
Paper TR15-046
| Approximately Counting Triangles in Sublinear Time |
Talya Eden,
Dana Ron,
Amit Levi
https://eccc.weizmann.ac.il/report/2015/046We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in two models: Exact counting algorithms, which require reading the entire graph, and streaming algorithms, where the edges are given in a stream and the memory is limited. 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 $\widehat{\Delta}$ such that with high constant probability, $(1-\epsilon)\Delta(G)< \widehat{\Delta}<(1+\epsilon)\Delta(G)$, where $\Delta(G)$ is the number of triangles in the graph $G$. The expected query complexity of the algorithm is $O\left(\frac{n}{\Delta(G)^{1/3}} + \min\left\{m, \frac{m^{3/2}}{\Delta(G)}\right\}\right)\cdot {\rm 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
$O\left(\frac{n}{\Delta(G)^{1/3}} + \frac{m^{3/2}}{\Delta(G)}\right)\cdot {\rm poly}(\log n, 1/\epsilon)$. We also prove that
$\Omega\left(\frac{n}{\Delta(G)^{1/3}} + \min\left\{m, \frac{m^{3/2}}{\Delta(G)}\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$). Thu, 02 Apr 2015 18:15:25 +0300https://eccc.weizmann.ac.il/report/2015/046