Abstract : A central problem in analyzing networks is partitioning them
into modules or communities, clusters with a statistically homogeneous
pattern of links 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 is, however, intractable exactly. In
this talk we discuss application of belief propagation algorithm to
module detection. In the first part we present an asymptotically exact
analysis of the stochastic block model. We quantify properties of the
detectability/undetectability phase transition and the easy/hard phase
transition for the module detection problem. In a second part of the
talk we discuss applications of the algorithm to real large scale data,
and related issues such as parameter learning, selection among different
stochastic block models, and comparison to existing approaches.

Cet exposé se tiendra en salle C20-13, 20ème étage, Université
Paris 1, Centre Pierre Mendès-France, 90 rue de Tolbiac, 75013 Paris
(métro : Olympiades).