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.

2010-2013 Publications

• 2013
  • J.‑L. GUILLAUME, R. CAMPIGOTTO, M. Seifi : “The Power of Consensus: Random Graphs Have No Communities”, IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013, Niagara Falls, ON, Canada, pp. 272-276, (IEEE) (2013)
• 2012
  • M. Seifi : “Cœurs stables de communautés dans les graphes de terrain”, thesis, phd defence 03/12/2012, supervision Latapy, Matthieu, co-supervision : Guillaume, Jean-Loup (2012)
  • 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”, 3^rd Workshop on Complex Networks (CompleNet 2012), vol. 424, Studies in Computational Intelligence, Melbourne, Florida, United States, pp. 87-98 (2012)
• 2010
  • M. Seifi, J.‑L. GUILLAUME, M. Latapy, B. Le Grand : “Interactive multiscale visualization of huge graphs: application to a network of weblogs”, 8^th Workshop on Visualization and Knowledge Extraction (EGC 2010), Hammamet, Tunisia (2010)