Supervision : Matthieu LATAPY

Co-supervision : GUILLAUME Jean-Loup

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

Most complex networks have a particular structure made up of communities. The nodes are arranged in groups called communities with many internal links but only a few between them. The identification of communities gives insights on the structure of the graph and is important in many contexts. It has, for example, been used for visualization of graphs and to study different types of networks like social networks or biological networks. We will study this structure in the case of dynamic networks. We will follow two approaches. The first approach consists in tracking communities over time by detecting them at every timestep and following their evolution. We will see that although very natural, this approach raises many questions of stability: the algorithms tend to change their results a lot even if the network changes only a little. This implies that the observed changes in the communities are in fact related to the algorithm and not to real transformations in network structure. We therefore propose an analysis of the instability of three algorithms and validate our solution on several complex networks. The second approach consists in detecting the community structure not just for a moment but for a period of time called the time window. The length of the time window is then a crucial problem and we propose a time segmentation method in time windows. The result is a hierarchical clustering: time windows can themselves contain other time windows. Moreover, the time windows do not have to be contiguous allowing for example to detect a repeating structure. Finally, we conclude with applications to event detection on the Internet and segmentation of videos. We will show that we can detect events by finding the times when the structure changes abruptly and show that we detect both new events and events already identified by other methods. For the segmentation of videos, we also had stability issues and thus we have developed a more stable tracking and detection algorithm based on community detection.

2010-2013 Publications

• 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”, thesis, phd defence 11/30/2011, supervision Latapy, Matthieu, co-supervision : 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)