Direction de recherche : Matthieu LATAPY

Co-encadrement : GUILLAUME Jean-Loup

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

Dans de nombreux contextes, des ensembles d'entités en relation peuvent être modélisés par des graphes, dans lesquels les entités individuelles sont représentées par des sommets et les relations entre ces entités par des liens. Ces graphes, que nous appellerons "graphes de terrain", peuvent être rencontrés dans le monde réel dans différents domaines tels que les sciences sociales, l'informatique, la biologie, le transport, la linguistique, etc. La plupart des graphes de terrain sont composés de sous-graphes denses faiblement inter-connectés appelés "communautés" et de nombreux algorithmes ont été proposés afin d'identifier cette structure communautaire automatiquement. Nous nous sommes intéressés dans cette thèse aux problèmes des algorithmes de détection de communatés, notamment leur non-déterminisme et l'instabilité qui en découle. Nous avons présenté une méthodologie qui tire parti de ce non-déterminisme afin d'améliorer les résultats obtenus avec les techniques actuelles de détection de communautés. Nous avons proposé une approche basée sur le concept de communautés fortes ou "cœurs de communautés" et nous avons montré l'amélioration apportée par notre approche en l'appliquant à des graphes réels et artificiels. Nous avons aussi étudié la structure des cœurs des graphes aléatoires et nous avons montré qu'à la différence des algorithmes classiques de détection de communautés qui peuvent trouver des partitions en communautés dans des graphes n'ayant pourtant aucune structure communautaire intrinsèque, notre approche indique clairement l'absence de structure communautaire dans les graphes aléatoires et permet en ce sens de distinguer les graphes aléatoires des graphes réels. Nous avons étudié également l'évolution des cœurs dans des réseaux dynamiques via une dynamique simulée simple et contrôlable ainsi qu'une dynamique réelle. Nous avons montré que les cœurs sont beaucoup plus stables que les communautés obtenues par les techniques actuelles de détection de communautés et que notre approche peut donc pallier les défauts des méthodes stabilisées qui ont été proposées récemment.

Publications 2010-2013

• 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”, soutenance de thèse, soutenance 12/03/2012, direction de recherche Latapy, Matthieu, co-encadrement : 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)