Information limits for recovering a hidden community

Bruce Hajek, Yihong Wu, Jiaming Xu

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


We study the problem of recovering a hidden community of cardinality K from an n × n symmetric data matrix A, where for distinct indices i; j, Aij ∼ P if i; j both belong to the community and Aij ∼ Q otherwise, for two known probability distributions P and Q depending on n. We focus on two types of asymptotic recovery guarantees as n → ∞: (1) weak recovery: expected number of classification errors is o(K); (2) exact recovery: probability of classifying all indices correctly converges to one. Under mild assumptions on P and Q, and allowing the community size to scale sublinearly with n, we derive a set of sufficient conditions and a set of necessary conditions for recovery, which are asymptotically tight with sharp constants. The results hold in particular for the Gaussian case (P = N(μ, 1) and Q = N(0; 1)), and for the case of bounded log likelihood ratio, including the Bernoulli case (P = Bern(p) and Q = Bern(q)) whenever p/q and 1-p/1-q are bounded away from zero and infinity. An important algorithmic implication is that, whenever exact recovery is information theoretically possible, any algorithm that provides weak recovery when the community size is concentrated near K can be upgraded to achieve exact recovery in linear additional time by a simple voting procedure.

Original languageEnglish (US)
Title of host publicationProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)9781509018062
StatePublished - Aug 10 2016
Event2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain
Duration: Jul 10 2016Jul 15 2016

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Other2016 IEEE International Symposium on Information Theory, ISIT 2016

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Information limits for recovering a hidden community'. Together they form a unique fingerprint.

Cite this