Back to Search
Start Over
Information Limits for Recovering a Hidden Community.
- Source :
- IEEE Transactions on Information Theory; Aug2017, Vol. 63 Issue 8, p4729-4745, 17p
- Publication Year :
- 2017
-
Abstract
- 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]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 63
- Issue :
- 8
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 124147902
- Full Text :
- https://doi.org/10.1109/TIT.2017.2653804