SEIFI Massoud

PhD graduated
Team : ComplexNetworks
Departure date : 03/15/2012

Supervision : Matthieu LATAPY

Co-supervision : GUILLAUME Jean-Loup

Cœurs stables de communautés dans les graphes de terrain

In many contexts, sets of related entities can be modeled by graphs, in which entities are represented by nodes and relationships between these entities by edges. These graphs, which we call "complex networks", may be encountered in the real world in various fields such as social science, computer science, biology, transportation, linguistics, etc. Most complex networks are composed of dense subgraphs weakly interconnected called "communities" and many algorithms have been proposed to identify the community structure of complex networks automatically. During this thesis, we focused on the problems of community detection algorithms, especially their non-determinism and the instability that results. We presented a methodology that takes advantage of this non-determinism to improve the results obtained with current community detection techniques. We proposed an approach based on the concept of strong communities, or "community cores", and we showed the improvement made by our approach by applying it to real and artificial graphs. We also studied the structure of cores in random graphs and we showed that unlike classical community detection algorithms which can find communities in graphs with no intrinsic community structure, our approach clearly indicates the absence of community structure in random graphs and, in this way, allows to distinguish between random and real graphs. We also studied the evolution of cores in dynamical networks using a simple and controllable simulated dynamic and a real dynamic. We showed that cores are much more stable than communities obtained by current community detection techniques and our approach can overcome the disadvantages of stabilized methods that have been recently proposed.

Defence : 03/12/2012 - 14h - Site Jussieu 25-26/105

Jury members :

Bertrand Jouve, Professeur Université Lumière Lyon 2 [Rapporteur]
Christine Largeron, Professeur Université Jean Monnet, [Rapporteur]
Christophe Crespelle, MdC, Université Claude Bernard Lyon 1
Marcelo Dias de Amorin, Directeur de Recherche CNRS
Matthieu Latapy, Directeur de Recherche CNRS
Jean-Loup Guillaume, MdC, Uuniversité Pierre et Marie Curie

2010-2013 Publications