COLE-DISSERTATION-2018.pdf (1023.32 kB)

An Iterative Spectral Approach to Recovering Planted Partitions

Download (1023.32 kB)
thesis
posted on 27.07.2018 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.

History

Advisor

Friedland, Shmuel

Chair

Friedland, Shmuel

Department

Mathematics, Statistics, and Computer Science

Degree Grantor

University of Illinois at Chicago

Degree Level

Doctoral

Committee Member

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

Submitted date

May 2018

Issue date

06/04/2018

Exports

Categories

Exports