Tata Institute of Fundamental Research
Community Detection in Networks: SDP Relaxations and Computational Gaps
STCS Seminar
Speaker:
Yihong Wu (University of Illinois at Urbana-Champaign
129, Coordinated Science Lab MC 228
1308 W. Main Street
Urbana Illinois 61801
United States of America)
Organiser:
Vinod M. Prabhakaran
Date:
Tuesday, 28 Jul 2015, 14:30 to 15:30
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: 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)).
| Speaker: | Yihong Wu (University of Illinois at Urbana-Champaign 129, Coordinated Science Lab MC 228 1308 W. Main Street Urbana Illinois 61801 United States of America) |
| Organiser: | Vinod M. Prabhakaran |
| Date: | Tuesday, 28 Jul 2015, 14:30 to 15:30 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: 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)).