- No file added yet -

# An Iterative Spectral Approach to Recovering Planted Partitions

thesis

posted on 2018-07-27, 00:00 authored by Samuel ColeIn 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

2018-04-06## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC