Spring 2015

Fundamental Limit of Community Detection in Stochastic Block Models

Monday, Mar. 16, 2015 2:50 pm3:15 pm PDT

Add to Calendar


Calvin Lab Auditorium

The stochastic block model (SBM) is a popular network model with community structures. It has (re)gained major attention in the past years due to new phase transition phenomena discovered for the two-cluster case. In this talk, we establish the fundamental limit of community recovery in the general SBM. We emphasize the strong analogy with the channel coding theorem, and provide a quasi-linear time algorithm that achieves the limit. Joint work with Colin Sandon.