A Simple Spectral Algorithm for Recovering Planted Partitions

Sam Cole, Shmuel Friedland, Lev Reyzin

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 i…