Recovering a hidden community beyond the Kesten-Stigum threshold in O(|E|log|V|) time

Bruce Hajek, Yihong Wu, Jiaming Xu

Research output: Contribution to journalArticlepeer-review


Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on weak recovery of the community based on the graph G, with o(K) misclassified vertices on average, in the sublinear regime n1-o(1) ≤ K ≤ o(n). A critical parameter is the effective signal-to-noise ratio λ = K2(p - q)2 / ((n - K)q), with λ = 1 corresponding to the Kesten-Stigum threshold. We show that a belief propagation (BP) algorithm achieves weak recovery if λ > 1 / e, beyond the Kesten-Stigum threshold by a factor of 1 / e. The BP algorithm only needs to run for logn + O(1) iterations, with the total time complexity O(|E|logn), where logn is the iterated logarithm of n. Conversely, if λ ≤ 1 / e, no local algorithm can asymptotically outperform trivial random guessing. Furthermore, a linear message-passing algorithm that corresponds to applying a power iteration to the nonbacktracking matrix of the graph is shown to attain weak recovery if and only if λ > 1. In addition, the BP algorithm can be combined with a linear-time voting procedure to achieve the information limit of exact recovery (correctly classify all vertices with high probability) for all K ≥ (n / logn) (ρBP + o(1)), where ρBP is a function of p / q.

Original languageEnglish (US)
Pages (from-to)325-352
Number of pages28
JournalJournal of Applied Probability
Issue number2
StatePublished - Jun 1 2018
Externally publishedYes


  • Hidden community
  • belief propagation
  • high-dimensional statistics
  • message passing
  • spectral algorithms

ASJC Scopus subject areas

  • Statistics and Probability
  • General Mathematics
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Recovering a hidden community beyond the Kesten-Stigum threshold in O(|E|log|V|) time'. Together they form a unique fingerprint.

Cite this