A semidefinite program for unbalanced multisection in the stochastic block model

Abstract: We propose a semidefinite programming (SDP) algorithm for community detection in the stochastic block model, a popular model for networks with latent community structure. We prove that our algorithm achieves exact recovery of the latent communities, up to the information-theoretic limits determined by Abbe and Sandon (2015). Our result extends prior SDP approaches by allowing for many communities of different sizes. By virtue of a semidefinite approach, our algorithms succeed against a semirandom variant of the stochastic block model, guaranteeing a form of robustness and generalization. We further explore how semirandom models can lend insight into both the strengths and limitations of SDPs in this setting.

This page was built for publication: A semidefinite program for unbalanced multisection in the stochastic block model

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