Information Limits for Recovering a Hidden Community

DOI10.1109/TIT.2017.2653804MaRDI QIDQ5369834zbMATH OpenOpenAlexFDO

Authors Bruce Hajek, Yihong Wu, Jiaming Xu

Publication date 19 October 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.07859

Mathematics Subject Classification ID

Information theory (general) (94A15) Measures of information, entropy (94A17)

Abstract: We study the problem of recovering a hidden community of cardinality $K$ from an $nimesn$ symmetric data matrix $A$, where for distinct indices $i,j$, $A_{ij}simP$ if $i,j$ both belong to the community and $A_{ij}simQ$ otherwise, for two known probability distributions $P$ and $Q$ depending on $n$. If $P=mBern(p)$ and $Q=mBern(q)$ with $p>q$, it reduces to the problem of finding a densely-connected $K$-subgraph planted in a large Erd"os-R'enyi graph; if $P=mathcalN(mu,1)$ and $Q=mathcalN(0,1)$ with $mu>0$, it corresponds to the problem of locating a $KimesK$ principal submatrix of elevated means in a large Gaussian random matrix. We focus on two types of asymptotic recovery guarantees as $noinfty$: (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, and for the case of bounded log likelihood ratio, including the Bernoulli case whenever $fracpq$ and $frac1-p1-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.

Cited in

(12)

• Convex optimization for the densest subgraph and densest submatrix problems
• Optimal rates for community estimation in the weighted stochastic block model
• Community detection and stochastic block models: recent developments
• Submatrix localization via message passing
• Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
• Distribution-free, size adaptive submatrix detection with acceleration
• Modeling Network Populations via Graph Distances
• A goodness-of-fit test on the number of biclusters in a relational data matrix
• The planted matching problem: sharp threshold and infinite-order phase transition
• Testing common degree-correction parameters of multilayer networks
• Detection of dense subhypergraphs by low-degree polynomials
• Pseudo-maximum likelihood theory for high-dimensional rank one inference

This page was built for publication: Information Limits for Recovering a Hidden Community

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5369834)