Clustering of networks : From phase transitions to optimal algorithms

Lenka Zdeborova (IPhT Saclay)

A central problem in analyzing networks or graphs is partitioning them into modules or communities, i.e. groups with a statistically homogeneous pattern of connections to each other or to the rest of the network. A principled approach to address this problem is to fit the network on a stochastic block model. This task, however, belongs to the class of very hard algorithmic problems. Still it can be reformulated as the equilibrium statistical mechanics of a particular mean field spin glass model. We apply the cavity method that is standard in studies of spin glasses and structural glasses and compute the associated phase diagram of the problem. We describe consequences of this result for algorithmic resolvability of the clustering problem. Further, we take advantage of the insight gained by the analysis to introduce a new class of spectral algorithms based on a non-backtracking walk on the directed edges of the graph. We show that the algorithm is optimal for graphs generated by the stochastic block model, detecting communities all the way down to the theoretical limit.

Lenka Zdeborova is a CNRS researcher in the Institute for theoretical physics (IPhT) of CEA in Saclay, France. She obtained her PhD in statistical physics in 2008 from the University Paris-XI, and spend two years as a director’s postdoctoral fellow in the Los Alamos National Laboratory. In 2014 she was awarded the bronze medal of CNRS. Her main research interest are applications of methods from statistical mechanics and theoretical physics to problems in computer science, information theory, signal processing and machine learning.

You can also watch this video on the multimedia site ENS : savoirs.ens.fr