Description
Date depot: 1 janvier 1900
Titre: Coeurs stables de communautés dans les graphes de terrain
Directeur de thèse:
Matthieu LATAPY (LIP6)
Directeur de thèse:
Jean-Loup GUILLAUME (L3I)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Les grands réseaux sont partout dans la science, la société, et la vie quotidienne : dans les transports (ligne aériennes, routes) ; dans les communications (internet, web, échanges de fichiers ou de courriers) ; dans la vie sociale (collaborations, amitié, échanges économiques) ; dans les sciences du vivant (interactions entre protéines et gènes, dépendances entre espèces) ; dans l'analyse des langages (synonymie, cooccurrences de mots) ; etc. Par exemple, l'internet est un ensemble de routeurs avec des liens entre eux ; le web est un ensemble de pages web avec des hyperliens entre elles ; les réseaux sociaux sont en général des ensembles de personnes liées par des relations sociales comme l'amitié ou la collaboration professionnelle ; les réseaux de synonymie sont des ensembles de mots reliés s'ils sont synonymes ; etc.
Dans tous ces contextes, modéliser les objets sous-jacents comme des graphes (ensemble de nœuds et de liens entre eux), appelés graphes de terrain ou complex networks en anglais, s'est montré extrêmement fructueux : cette approche joue un rôle central dans leur modélisation et en simulation ; elle rend possible l'étude de la diffusion d'information, rumeurs et virus ; elle donne également des informations précieuses sur la robustesse des réseaux considérés ; etc.
L’une des approches naturelles pour étudier ces graphes est de les considérer comme constitués de communautés : des groupes de nœuds très denses mais avec peu de liens entre les groupes eux-mêmes. La détection de tels groupes est un problème difficile et de nombreuses méthodes heuristiques ont été proposées dans le cadre des réseaux statiques. Néanmoins il est courant que les données évoluent au cours du temps : nouveaux contacts dans les réseaux sociaux, nouvelles machines ou nouveaux liens entre machines, etc. Il faut donc tenter de prendre en compte ces informations pour analyser plus finement les réseaux.
L’objectif de cette thèse est d’utiliser la structure communautaire multi-échelles pour décrire la dynamique des graphes de terrain. L’une des applications naturelle est d’aider à la visualisation de ces graphes, qui est un but en soi mais qui peut aussi, en réduisant la complexité du graphe, aider à comprendre et analyser ces données.
Doctorant.e: Seifi Massoud