Abstract

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.

Video Recording