Consistency thresholds for the planted bisection model

Elchanan Mossel, Joe Neeman, Allan Sly

Research output: Chapter in Book/Report/Conference proceedingConference contribution

41 Scopus citations

Abstract

The planted bisection model is a random graph model in which the nodes are divided into two equal-sized communities and then edges are added randomly in a way that depends on the community membership. We establish necessary and sufficient conditions for the asymptotic recover-ability of the planted bisection in this model. When the bisection is asymptotically recoverable, we give an efficient algorithm that successfully recovers it. We also show that the planted bisection is recoverable asymptotically if and only if with high probability every node belongs to the same community as the majority of its neighbors. Our algorithm for finding the planted bisection runs in time almost linear in the number of edges. It has three stages: spectral clustering to compute an initial guess, a "replica" stage to get almost every vertex correct, and then some simple local moves to finish the job. An independent work by Abbe, Bandeira, and Hall establishes similar (slightly weaker) results but only in the sparse case where pn, qn = T(log n/n).

Original languageEnglish (US)
Title of host publicationSTOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages69-75
Number of pages7
ISBN (Electronic)9781450335362
DOIs
StatePublished - Jun 14 2015
Externally publishedYes
Event47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States
Duration: Jun 14 2015Jun 17 2015

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume14-17-June-2015
ISSN (Print)0737-8017

Other

Other47th Annual ACM Symposium on Theory of Computing, STOC 2015
CountryUnited States
CityPortland
Period6/14/156/17/15

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Graph clustering
  • Min-bisection
  • Planted bisection model
  • Random graph
  • Stochastic block model

Cite this

Mossel, E., Neeman, J., & Sly, A. (2015). Consistency thresholds for the planted bisection model. In STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing (pp. 69-75). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 14-17-June-2015). Association for Computing Machinery. https://doi.org/10.1145/2746539.2746603