  In this paper, we consider the planted partition model, in which $n = ks$
vertices of a random graph are partitioned into $k$ "clusters," each of size
$s$. Edges between vertices in the same cluster and different clusters are
included with constant probability $p$ and $q$, respectively (where $0 \le q <
p \le 1$). We give an efficient algorithm that, with high probability, recovers
the clusters as long as the cluster sizes are are least $\Omega(\sqrt{n})$.
Informally, our algorithm constructs the projection operator onto the dominant
$k$-dimensional eigenspace of the graph's adjacency matrix and uses it to
recover one cluster at a time. To our knowledge, our algorithm is the first
purely spectral algorithm which runs in polynomial time and works even when $s
= \Theta(\sqrt n)$, though there have been several non-spectral algorithms
which accomplish this. Our algorithm is also among the simplest of these
spectral algorithms, and its proof of correctness illustrates the usefulness of
the Cauchy integral formula in this domain.
