A semidefinite program for unbalanced multisection in the stochastic block model
This addresses community detection in network analysis, offering robustness and generalization, but is incremental as it builds on existing SDP methods.
The authors tackled community detection in networks with latent structure by proposing a semidefinite programming algorithm that achieves exact recovery of communities up to information-theoretic limits, extending prior approaches to handle many communities of different sizes.
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.