Title: Recovering Nonuniform Planted Partitions via Iterated Projection,
Abstract: In the planted partition problem, the $n$ vertices of a random graph are
partitioned into $k$ "clusters," and 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 spectral
algorithm that recovers the clusters with high probability, provided that the
sizes of any two clusters are either very close or separated by $\geq
\Omega(\sqrt n)$. We also discuss a generalization of planted partition in
which the algorithm's input is not a random graph, but a random real symmetric
matrix with independent above-diagonal entries.
Our algorithm is an adaptation of a previous algorithm for the uniform case,
i.e., when all clusters are size $n / k \geq \Omega(\sqrt n)$. The original
algorithm recovers the clusters one by one via iterated projection: it
constructs the orthogonal projection operator onto the dominant $k$-dimensional
eigenspace of the random graph's adjacency matrix, uses it to recover one of
the clusters, then deletes it and recurses on the remaining vertices. We show
herein that a similar algorithm works in the nonuniform case.