Direction de recherche : Matthieu LATAPY

Co-encadrement : GUILLAUME Jean-Loup

Détection de communautés dans les réseaux dynamiques

La plupart des graphes de terrain ont une structure particulière constituée de communautés. Les noeuds sont organisés suivant des groupes appelés des communautés avec beaucoup de connexions internes mais peu entre eux. L'identification des communautés apporte un éclairage nouveau sur la structure du graphe et est importante dans de nombreux contextes. Elle a, par exemple, déjà été utilisée pour la visualisation de graphes et pour étudier différents types de réseaux comme des réseaux sociaux ou biologiques. Nous allons étudier cette structure dans le cas des réseaux dynamiques. Pour cela, nous allons suivre deux approches. La première consiste à suivre des communautés au cours du temps en les détectant à chaque instant et en suivant leur évolution. Nous verrons que bien que très naturelle, cette approche pose de nombreuses questions de stabilité : les algorithmes ont tendance à modifier beaucoup leur résultat même si le réseau change peu. Cela implique que les transformations observées dans les communautés sont en fait liées à l'algorithme et non à l'évolution de la structure du réseau. Nous proposerons donc une analyse de l'instabilité de trois algorithmes et une solution que nous validerons sur plusieurs graphes de terrain. La deuxième approche consiste à détecter la structure communautaire non pas juste pour un instant mais pour une période donnée appelée la fenêtre de temps. La durée de la période est alors un problème crucial et nous proposons une méthode de décomposition en fenêtres de temps dans un graphe dynamique. Une particularité de la méthode est que le résultat est un regroupement hiérarchique : les fenêtres de temps sont elles-mêmes susceptibles d'en contenir. En outre, les fenêtres n'ont pas besoin d'être contiguës ce qui permet par exemple de détecter une structure se répétant. Enfin, nous conclurons par des applications à la détection d'événements sur Internet et la segmentation de vidéos. Nous montrerons que l'on peut détecter des événements en trouvant les moments où la structure change brutalement et montrerons que nous détectons à la fois de nouveaux événements et des événements déjà identifiés par d'autres méthodes. Pour la segmentation de vidéos, nous avons aussi eu des problème de stabilité et nous avons donc développé une méthode plus stable de suivi et de détection.

Publications 2010-2013

• 2013
  • Th. Aynaud, E. Fleury, J.‑L. GUILLAUME, Q. Wang : “Communities in evolving networks: definitions, detection and analysis techniques”, chapter in Dynamics On and Of Complex Networks, vol. 2, pp. 159-200, (Springer) (2013)
• 2011
  • Th. Aynaud : “Détection de communautés dans les réseaux dynamiques”, soutenance de thèse, soutenance 30/11/2011, direction de recherche Latapy, Matthieu, co-encadrement : Guillaume, Jean-Loup (2011)
  • Th. Aynaud, J.‑L. GUILLAUME : “Extraction hiérarchique de fenêtres de temps basée sur la structure communautaire”, MARAMI 2011, Grenoble, France (2011)
  • Th. Aynaud, J.‑L. GUILLAUME : “Multi-Step Community Detection and Hierarchical Time Segmentation in Evolving Networks”, Fifth SNA-KDD Workshop Social Network Mining and Analysis, in conjunction with the 17^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2011), San Diego, CA, United States (2011)
  • Th. Aynaud, Vincent D. Blondel, J.‑L. GUILLAUME, R. Lambiotte : “Optimisation locale multi-niveaux de la modularité”, chapitre de Partitionnement de graphe : optimisation et applications, Traité IC2, pp. 14, (Hermes-Lavoisier) (2011)
  • Th. Aynaud, J.‑L. GUILLAUME : “Structure multi-échelle de grands graphes de terrain”, Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques, vol. 30 (2), pp. 137-154, (Lavoisier) (2011)
• 2010
  • Th. Aynaud, J.‑L. GUILLAUME : “Détection de communautés à long terme dans les graphes dynamiques”, Journée thématique : Fouille de grands graphes, Toulouse, France (2010)
  • Th. Aynaud, J.‑L. GUILLAUME : “Long range community detection”, LAWDN - Latin-American Workshop on Dynamic Networks, Buenos Aires, Argentina, pp. 4 p. (2010)
  • Th. Aynaud, J.‑L. GUILLAUME : “Static community detection algorithms for evolving networks”, WiOpt'10: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, Avignon, France, pp. 508-514 (2010)