Détection de communautés dans les réseaux dynamiques
Institution:
Paris 6Disciplines:
Directors:
Abstract EN:
Most complex networks have a particular structure in which 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. We will study this structure in the case of dynamic networks using two different 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 a solution to the instability. 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 hierachical time segmentation method in 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. For the segmentation of videos, we also had stability issues and thus we have developed a more stable tracking and detection algorithm.
Abstract FR:
La plupart des graphes de terrain ont une structure particulière dans laquelle les noeuds sont organisés suivant des groupes, appelés 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. Nous allons étudier cette structure dans le cas des réseaux dynamiques afin de comprendre comment évoluent les groupes. 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. 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. Nous proposerons donc une analyse de l'instabilité de trois algorithmes et une solution à cette instabilité. La deuxième approche consiste à détecter la structure communautaire non pas juste pour un instant mais pour une période donnée. La durée de celle-ci est alors un problème crucial et nous proposons une méthode de décomposition hiérarchique en fenêtres de temps permettant de détecter des structures 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. Pour la segmentation de vidéos, nous avons aussi eu des problème de stabilité et nous avons développé une méthode plus stable de suivi.