Exact recovery in the stochastic block model with the relaxed K-means

Paris-Saclay Junior Conference on Data Science and Engineering, September 2017.

• Manuscript

• Code

• Talk

In many fields of science, we observe interactions between entities or individuals and we would like to recover the underlying community structure. The stochastic block model is a natural and canonical model for networks with communities. This paper proposes a new semidefinite program to recover communities in the stochastic block model, based on a convex relaxation of K-Means and leading to the so-called PECOK algorithm. The PECOK algorithm is very general and flexible, and can work with a broad class of community models. It achieves exact recovery with high probability - as the number of observations tends to infinity - in the stochastick block model, when a simple variance-gap condition is satisfied.