  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,
\phi)$-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
$\phi$ and the (outer) conductance of each part is at most
$c_{d,k}\varepsilon^4\phi^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}(\phi,k,1/\varepsilon))$ that takes as
input a graph with maximum degree bounded by $d$, parameters $k$, $\phi$,
$\varepsilon$, and with probability at least $\frac23$, accepts the graph if it
is $(k,\phi)$-clusterable and rejects the graph if it is $\varepsilon$-far from
$(k, \phi^*)$-clusterable for $\phi^* = c'_{d,k}\frac{\phi^2
\varepsilon^4}{\log n}$, where $c'_{d,k}$ depends only on $d,k$. By the lower
bound of $\Omega(\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.
