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

I. Lemhadri, Y. Emin

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

Best Talk Award.

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.

Back to research page.