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.
Defence : 11/30/2011 - 14h - Site Jussieu 25-26/105 Jury members : Éric FLEURY, École normale supérieure de Lyon [Rapporteur]
Nicolas HANUSSE, Université de Bordeaux 1 [Rapporteur]
Vincent BLONDEL, Université Catholique de Louvain
Franck PETIT, Université Pierre et Marie Curie
Matthieu LATAPY, Université Pierre et Marie Curie
Jean-Loup GUILLAUME, Université Pierre et Marie Curie