Partial Recovery Bounds for the Sparse Stochastic Block Model
In this paper, we study the information-theoretic limits of community detection in the symmetric two-community stochastic block model, with intra-community and inter-community edge probabilities $\frac{a}{n}$ and $\frac{b}{n}$ respectively. We consider the sparse setting, in which $a$ and $b$ do not scale with $n$, and provide upper and lower bounds on the proportion of community labels recovered on average. We provide a numerical example for which the bounds are near-matching for moderate values of $a - b$, and matching in the limit as $a-b$ grows large.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionStochastic Block ModelSimilar Papers 제목 키워드 기반
Partial recovery bounds for clustering with the relaxed $K$means
We investigate the clustering performances of the relaxed $K$means in the setting of sub-Gaussian Mixture Model (sGMM) and Stochastic Block Model (SBM). After identifying the appropriate signal-to-noise ratio (SNR), we p…
ClusteringStochastic Block ModelSparse recovery by reduced variance stochastic approximation
In this paper, we discuss application of iterative Stochastic Optimization routines to the problem of sparse signal recovery from noisy observation. Using Stochastic Mirror Descent algorithm as a building block, we devel…
Stochastic OptimizationExponential error rates of SDP for block models: Beyond Grothendieck's inequality
In this paper we consider the cluster estimation problem under the Stochastic Block Model. We show that the semidefinite programming (SDP) formulation for this problem achieves an error rate that decays exponentially in …
Stochastic Block ModelOn the accuracy of l1-filtering of signals with block-sparse structure
We discuss new methods for the recovery of signals with block-sparse structure, based on l1-minimization. Our emphasis is on the efficiently computable error bounds for the recovery routines. We optimize these bounds wit…
A Semidefinite Program for Structured Blockmodels
Semidefinite programs have recently been developed for the problem of community detection, which may be viewed as a special case of the stochastic blockmodel. Here, we develop a semidefinite program that can be tailored …
Community Detection