---

Detecting community structure from network topology is a well known problem with many possible applications. A large number of studies was conducted over the last decade, but a principal approach that would for instance output that a random graph does not have any community structure is still missing. Based on a random graph model for a community structure I will first show the existence of a phase transition between possible and impossible community inference. This phase transition is related to some known results from statistical physics of spin glasses, for optimal inference the partition function of a corresponding spin glass model needs to be computed. Then I will turn to real-world networks and inspired by the theoretical results I Introduce a new message passing algorithm which is able to learn parameters of the community structure (number of communities, ...), and to infer the most likely community assignment. As an application I will present some results on real-world net.

---

Aurelin Decelle, LPTMS, Universite Paris-Sud
Institute of Theoretical Physics, Zülpicher Str. 77, Seminar Room
Contact: not specified