LogoLogo

Cazabet, Rémy. Détection de communautés dynamiques dans des réseaux temporels

Cazabet, Rémy (2013). Détection de communautés dynamiques dans des réseaux temporels.

[img]PDF - nécessite un logiciel de visualisation PDF comme GSview, Xpdf or Adobe Acrobat Reader
5Mb

Résumé en francais

La détection de communauté dans les réseaux est aujourd'hui un domaine ayant donné lieu à une abondante littérature. Depuis les travaux de Girvan et Newman en 2002, des centaines de travaux ont été menés sur le sujet, notamment la proposition d'un nombre important d'algorithmes de plus en plus élaborés. Si, au départ, le découpage était un partitionnement -chaque nœud appartenait à une et une seule communauté, unique et statique- les méthodes ultérieures ont montré l'intérêt de communautés imbriquées, ou décomposées hiérarchiquement. Encore plus récemment, certains travaux ont commencé à s'intéresser aux communautés dans des réseaux temporels, c'est à dire à des communautés qui évoluent au cours du temps, selon les modifications du réseau. C'est à ce nouveau problème que j'ai consacré cette thèse. Mon état de l'art, après avoir présenté les méthodes statiques les plus connues, est consacré à l'étude des quelques méthodes déjà proposées pour la détection de communautés dynamiques - dont beaucoup ont été publiées au cours des années durant lesquelles j'ai fait ma thèse- ainsi qu'à leurs forces et faiblesses. Dans une seconde partie, je propose un framework (iLCD) permettant de détecter des communautés persistantes dans des réseaux évoluant fortement, représentés sous la forme de graphes d'intervalles (chaque lien existe pour une ou plusieurs périodes données). Ce framework est conçu pour traiter de grands graphes, éventuellement en temps réel. Je propose ensuite deux implémentations de ce framework, la première étant limitée à des réseaux sans disparition de liens (de type réseaux de citation). La dernière partie de ce chapitre est consacrée aux aspects pratiques de la détection de communautés dynamiques, en particulier comment manipuler les données en entrée (réseaux temporels) et en sortie (communautés dynamique), qui sont plus complexes que dans le cas statique. Deux outils de visualisation de communautés dynamiques sont proposés, leur nécessité étant apparue au cours ma thèse. Le problème de tout algorithme de détection de communautés est de prouver la pertinence des résultats qu'il trouve. J'ai donc consacré la troisième partie de la thèse à ce problème. Cela m'a conduit à m'interroger sur la définition de ce qu'est une bonne communauté, et j'ai en particulier distingué ce que j'ai appelé les communautés intrinsèques des communautés définies relativement au réseau. Afin de valider la pertinence des résultats trouvés, j'ai ensuite essayé de comparer les communautés données par ma méthode avec celles données par les algorithmes statiques les plus connus. Étant particulièrement intéressé par l'application à des graphes réels, et la comparaison aux autre algorithmes se faisant généralement sur des graphes générés, j'ai ensuite proposé deux approches originales pour comparer des communautés sur des graphes réels : l'une, basée sur l'expérimentation, demande à des utilisateurs de Facebook de comparer les communautés trouvées dans leur réseau personnel par différentes solutions. L'autre propose, via deux métriques complémentaires, de comparer les solutions fournies par des algorithmes différents sur un même réseau. Enfin, dans la dernière partie, je présente deux applications de cet algorithme à des réseaux réels dynamiques. Le but de ces applications est double : d'une part, montrer l'intérêt pratique de l'approche dynamique, et, d'autre part, valider l'applicabilité de l'algorithme proposé sur des réseaux réels. Le premier réseau, de petite taille, concerne l'évolution des groupes au sein d'une population animale ayant un comportement social, étudiée sur une période de plus de quinze ans. Ce travail a été fait en concertation avec des éthologues, ayant déjà travaillé sur ces données de manière statique. La deuxième application est menée sur un réseau de beaucoup plus grande taille, concernant le réseau complet d'une plateforme de partage de vidéo japonaise de type Youtube, appelée Nico Nico Douga. Dans les deux cas, une analyse détaillée des résultats obtenus est fournie, qui permet de se rendre compte de l'intérêt de mon approche.

Sous la direction du :
Directeur de thèse
Hanachi, Chihab
Amblard, Frédéric
Ecole doctorale:Mathématiques, informatique, télécommunications de Toulouse (MITT)
laboratoire/Unité de recherche :Institut de Recherche en Informatique de Toulouse (IRIT), UMR 5505
Mots-clés libres :Détection de communautés - Analyse de réseaux sociaux - Réseaux temporels - Fouille de données - Réseaux dynamique - Grands réseaux de terrains
Sujets :Informatique
Déposé le :20 Jan 2014 11:01