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
M. Seifi, J.‑L. GUILLAUME : “Community Cores in Evolving Networks”, Mining Social Network Dynamic 2012 Workshop (MSND), In conjunction with the international conference World Wide Web WWW 2012, Lyon, France, pp. 1173-1180 (2012)
M. Seifi, J.‑L. GUILLAUME, I. Junier, J.‑B. Rouquier, S. Iskrov : “Stable community cores in complex networks”, 3rd Workshop on Complex Networks (CompleNet 2012), vol. 424, Studies in Computational Intelligence, Melbourne, Florida, United States, pp. 87-98 (2012)