Collins Conference Room
Seminar
US Mountain Time
Our campus is closed to the public for this event.
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.