COLE-DISSERTATION-2018.pdf (1023.32 kB)

An Iterative Spectral Approach to Recovering Planted Partitions

Download (1023.32 kB)
posted on 27.07.2018, 00:00 by Samuel Cole
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 < q < p < 1). In this work, 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 sqrt(n). The 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.



Friedland, Shmuel


Friedland, Shmuel


Mathematics, Statistics, and Computer Science

Degree Grantor

University of Illinois at Chicago

Degree Level


Committee Member

Antieau, Benjamin Lim, Lek-Heng Reyzin, Lev Turan, Gyorgy

Submitted date

May 2018

Issue date


Usage metrics