Luidmila Prokhorenkova

Community detection through likelihood optimization: in search of a sound model

Community detection has recently became one of the most important problems in network analysis and many algorithms have been proposed to solve this problem. Among others, methods based on statistical inference are of particular interest: such algorithms are mathematically sound and were shown to provide partitions of good quality. The main ingredient of statistical inference methods is to assume some underlying random graph model (a.k.a. “null model”) and then fit this model to the observed graph by maximizing the likelihood.

In this talk, I will overview the field of statistical inference in community detection and I will mostly focus on the choice of a proper null model. In particular, I will present several widely used models together with a new one and discuss their properties. I am also going to discuss and compare empirically some likelihood optimization algorithms suitable for the null models under consideration.