Information Limits for Recovering a Hidden Community

Bruce Hajek, Yihong Wu, Jiaming Xu

Research output: Contribution to journalArticlepeer-review

Abstract

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. If P= Bern(p) and Q= Bern(q) with p>q, it reduces to the problem of finding a densely connected K-subgraph planted in a large Erdös-Rényi graph; if P= N(μ,1) and Q= N(0,1) with μ >0, it corresponds to the problem of locating a K × K principal submatrix of elevated means in a large Gaussian random matrix. We focus on two types of asymptotic recovery guarantees as n to: 1) weak recovery: expected number of classification errors is o(K) and 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, and for the case of bounded log likelihood ratio, including the Bernoulli case whenever (p/q) and (1-p)/(1-q) are bounded away from zero and infinity. Previous work has shown that if weak recovery is achievable; then, exact recovery is achievable in linear additional time by a simple voting procedure. We provide a converse, showing the condition for the voting procedure to succeed is almost necessary for exact recovery.

Original languageEnglish (US)
Article number7820122
Pages (from-to)4729-4745
Number of pages17
JournalIEEE Transactions on Information Theory
Volume63
Issue number8
DOIs
StatePublished - Aug 2017

Keywords

  • Community detection
  • large deviation
  • maximum likelihood
  • rate distortion theory
  • stochastic block model
  • submatrix localization

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Information Limits for Recovering a Hidden Community'. Together they form a unique fingerprint.

Cite this