Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
arXiv:1412.6156
Abstract
The binary symmetric stochastic block model deals with a random graph of vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability within clusters and across clusters. In the asymptotic regime of and for fixed and , we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. \cite{Abbe14}. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to .
arXiv commentThis paper was accepted to IEEE Transactions on Information Theory on January 3, 2016
References in corpus (6)
- Finding and evaluating community structure in networks
- Community detection in graphs
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
- Computational Lower Bounds for Community Detection on Random Graphs