Collins Conference Room

This event is by invitation only.

Jiaming Xu (Simons Institute)

Abstract: We study a semidefinite programming (SDP) relaxation of the maximum likelihood estimator for exactly recovering hidden communities under the stochastic block model. It is shown that: when the community size is large comparing to the network size, the SDP relaxation achieves the information-theoretic recovery threshold with sharp constants; when the community size is small, the SDP becomes strictly suboptimal comparing to the maximum likelihood estimator. The effectiveness of SDP for finding communities in real-world networks will be demonstrated.

Research Collaboration
SFI Host: 
Cris Moore