Information Limits for Recovering a Hidden Community.

We study the problem of recovering a hidden community of cardinality K from an n \times n symmetric data matrix A , where for distinct indices i,j if i, j both belong to the community and Aij \sim Q otherwise, for two known probability distributions P and Q depending on n . If P=\mathrm Bern(p) and Q=\mathrm 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=\mathcal N(\mu ,1) and Q=\mathcal N(0,1) with $\mu >0$ , it corresponds to the problem of locating a K \times K$ principal submatrix of elevated means in a large Gaussian random matrix. We focus on two types of asymptotic recovery guarantees as n \to \infty $ : 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 ({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. [ABSTRACT FROM AUTHOR]