Testing Cluster Structure of Graphs

Abstract

We study the problem of recognizing the cluster structure of a graph in the framework of property testing in the bounded degree model. Given a parameter $\varepsilon$, a $d$-bounded degree graph is defined to be $(k, ϕ)$-clusterable, if it can be partitioned into no more than $k$ parts, such that the (inner) conductance of the induced subgraph on each part is at least $ϕ$ and the (outer) conductance of each part is at most $c_{d,k}\varepsilon^4ϕ^2$, where $c_{d,k}$ depends only on $d,k$. Our main result is a sublinear algorithm with the running time $\widetilde{O}(\sqrt{n}\cdot\mathrm{poly}(ϕ,k,1/\varepsilon))$ that takes as input a graph with maximum degree bounded by $d$, parameters $k$, $ϕ$, $\varepsilon$, and with probability at least $\frac23$, accepts the graph if it is $(k,ϕ)$-clusterable and rejects the graph if it is $\varepsilon$-far from $(k, ϕ^*)$-clusterable for $ϕ^* = c'_{d,k}\frac{ϕ^2 \varepsilon^4}{\log n}$, where $c'_{d,k}$ depends only on $d,k$. By the lower bound of $Ω(\sqrt{n})$ on the number of queries needed for testing graph expansion, which corresponds to $k=1$ in our problem, our algorithm is asymptotically optimal up to polylogarithmic factors.

Full version of STOC 2015