Community Detection in Networks: SDP Relaxations and Computational Gaps

This talk focuses on the problem of finding the underlying communities within a network using only knowledge of network topology. We consider a generative model for a network, namely the planted cluster model, which is a simple extension of the classical stochastic block model. We derive a semidefinite programming (SDP) relaxation of the maximum likelihood estimator for recovering the planted clusters from the network. If the size of the community is linear in the total number of vertices, the performance guarantee of the SDP exactly matches the necessary information bound. However, if the community size is sub-linear in the total number of vertices, the performance guarantee of the SDP is far from the information limit. Building on average case reductions, we show there exists a significant gap between the information limit and what can be achieved by computationally efficient procedures, conditioned on the assumptions that certain instances of the planted clique problem cannot be solved in randomized polynomial time (based on joint work, available at 1406.6625, 1412.6156 and 1502.07738, with Bruce Hajek (UIUC) and Jiaming Xu (Wharton)).