Aula Rasetti (Dip. di Fisica - Edificio G. Marconi)
Aula Rasetti
Dip. di Fisica - Edificio G. Marconi
Description
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 networks.