Community detection and stochastic block models

Emmanuel Abbe

Research output: Contribution to journalArticle

53 Scopus citations

Abstract

The stochastic block model (SBM) is a random graph model with different group of vertices connecting differently. It is widely employed as a canonical model to study clustering and community detection, and provides a fertile ground to study the information-theoretic and computational tradeoffs that arise in combinatorial statistics and more generally data science. This monograph surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational tradeoffs, and for various recovery requirements such as exact, partial and weak recovery. The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal SNR-mutual information tradeoff for partial recovery, and the gap between information-theoretic and computational thresholds.

Original languageEnglish (US)
Pages (from-to)1-162
Number of pages162
JournalFoundations and Trends in Communications and Information Theory
Volume14
Issue number1-2
DOIs
StatePublished - Jan 1 2018

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Community detection and stochastic block models'. Together they form a unique fingerprint.

  • Cite this