Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery

Emmanuel Abbe, Colin Sandon

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

239 Scopus citations

Abstract

New phase transition phenomena have recently been discovered for the stochastic block model, for the special case of two non-overlapping symmetric communities. This gives raise in particular to new algorithmic challenges driven by the thresholds. This paper investigates whether a general phenomenon takes place for multiple communities, without imposing symmetry. In the general stochastic block model SBM (n, p, W), n vertices are split into k communities of relative siz{pi} i∈[k], and vertices in community i and j connect independently with probability {Wij}i,j ∈[k]. This paper investigates the partial and exact recovery of communities in the general SBM (in the constant and logarithmic degree regimes), and uses the generality of the results to tackle overlapping communities. The contributions of the paper are: (i) an explicit characterization of the recovery threshold in the general SBM in terms of a new f-divergence function D+, which generalizes the Hellinger and Chern off divergences, and which provides an operational meaning to a divergence function analog to the KL-divergence in the channel coding theorem, (ii) the development of an algorithm that recovers the communities all the way down to the optimal threshold and runs in quasi-linear time, showing that exact recovery has no information-theoretic to computational gap for multiple communities, (iii) the development of an efficient algorithm that detects communities in the constant degree regime with an explicit accuracy bound that can be made arbitrarily close to 1 when a prescribed signal-to-noise ratio (defined in term of the spectrum of diag(p)W tends to infinity.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PublisherIEEE Computer Society
Pages670-688
Number of pages19
ISBN (Electronic)9781467381918
DOIs
StatePublished - Dec 11 2015
Event56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States
Duration: Oct 17 2015Oct 20 2015

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2015-December
ISSN (Print)0272-5428

Other

Other56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
Country/TerritoryUnited States
CityBerkeley
Period10/17/1510/20/15

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • Community detection
  • clustering algorithms
  • graph-based codes
  • information measures
  • phase transitions
  • stochastic block models

Fingerprint

Dive into the research topics of 'Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery'. Together they form a unique fingerprint.

Cite this