Community Detection in Networks: Understanding the fundamenental limits of polynomial-time algorithms

Jiaming Xu - Wharton School - Statistics Department
Apr 29 2015 - 3:00pm
Event type: 
110 Fine Hall

This talk focuses on the problem of nding 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 semidef-
inite 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 signi cant gap between the information limit and what
can be achieved by computationally ecient procedures, conditionally on the
assumptions that some instances of the planted clique problem cannot be solved
in randomized polynomial time.
Based on joint work, available at arXiv:1402.1267, 1406.6625, 1412.6156 and
1502.07738, with Yudong Chen at UC Berkeley, and Bruce Hajek, Yihong Wu
from UIUC.

Jiaming Xu received BE degree from Tsinghua University in Beijing (2009), and
MS (2011) from UT-Austin, and PhD (2014) from UIUC, all in ECE. He is a
postdoctoral fellow with the Statistics Department, the Wharton School of the
University of Pennsylvania, under the direction of Professor Elchanan Mossel.
His research interests are in stochastic networks.