# A simple spectral algorithm for recovering planted partitions

Special Matrices (2017)

• Volume: 5, Issue: 1, page 139-157
• ISSN: 2300-7451

top

## Abstract

top
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 in the same cluster and different clusters are included with constant probability p and q, respectively (where 0 ≤ q < p ≤ 1). We give an efficient algorithm that, with high probability, recovers the clusters as long as the cluster sizes are are least (√n). Informally, our algorithm constructs the projection operator onto the dominant k-dimensional eigenspace of the graph’s adjacency matrix and uses it to recover one cluster at a time. To our knowledge, our algorithm is the first purely spectral algorithm which runs in polynomial time and works even when s = Θ (√n), though there have been several non-spectral algorithms which accomplish this. Our algorithm is also among the simplest of these spectral algorithms, and its proof of correctness illustrates the usefulness of the Cauchy integral formula in this domain.

## How to cite

top

Sam Cole, Shmuel Friedland, and Lev Reyzin. "A simple spectral algorithm for recovering planted partitions." Special Matrices 5.1 (2017): 139-157. <http://eudml.org/doc/288505>.

@article{SamCole2017,
abstract = {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 in the same cluster and different clusters are included with constant probability p and q, respectively (where 0 ≤ q < p ≤ 1). We give an efficient algorithm that, with high probability, recovers the clusters as long as the cluster sizes are are least (√n). Informally, our algorithm constructs the projection operator onto the dominant k-dimensional eigenspace of the graph’s adjacency matrix and uses it to recover one cluster at a time. To our knowledge, our algorithm is the first purely spectral algorithm which runs in polynomial time and works even when s = Θ (√n), though there have been several non-spectral algorithms which accomplish this. Our algorithm is also among the simplest of these spectral algorithms, and its proof of correctness illustrates the usefulness of the Cauchy integral formula in this domain.},
author = {Sam Cole, Shmuel Friedland, Lev Reyzin},
journal = {Special Matrices},
language = {eng},
number = {1},
pages = {139-157},
title = {A simple spectral algorithm for recovering planted partitions},
url = {http://eudml.org/doc/288505},
volume = {5},
year = {2017},
}

TY - JOUR
AU - Sam Cole
AU - Shmuel Friedland
AU - Lev Reyzin
TI - A simple spectral algorithm for recovering planted partitions
JO - Special Matrices
PY - 2017
VL - 5
IS - 1
SP - 139
EP - 157
AB - 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 in the same cluster and different clusters are included with constant probability p and q, respectively (where 0 ≤ q < p ≤ 1). We give an efficient algorithm that, with high probability, recovers the clusters as long as the cluster sizes are are least (√n). Informally, our algorithm constructs the projection operator onto the dominant k-dimensional eigenspace of the graph’s adjacency matrix and uses it to recover one cluster at a time. To our knowledge, our algorithm is the first purely spectral algorithm which runs in polynomial time and works even when s = Θ (√n), though there have been several non-spectral algorithms which accomplish this. Our algorithm is also among the simplest of these spectral algorithms, and its proof of correctness illustrates the usefulness of the Cauchy integral formula in this domain.
LA - eng
UR - http://eudml.org/doc/288505
ER -

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.