logo EDITE Sujets de doctorat

Caractérisation de la dynamique des réseaux : analyse et modélisation

Sujet proposé par
Directeur de thèse:
Encadré par
Doctorant: Marwan Tarek GHANEM ABDELMOTAAL
Unité de recherche UMR 7606 Laboratoire d'informatique de Paris 6

Domaine: Sciences et technologies de l'information et de la communication

Projet

Beaucoup de réseaux qui nous entourent se prêtent naturellement à la formalisation sous forme de graphes pour analyser et modéliser leur structure. Habituellement, les sommets du graphe représentent les noeuds du réseau et les arcs entre les sommets représentent les (possibles) interactions entre les noeuds du réseau ou encore leur dépendance. On peut par exemple citer les réseaux de transports, les infrastructures de communications, les réseaux d'interaction biologiques, les réseaux sociaux, etc. Cette représentation s'est déjà révélée utile pour un grand nombre de graphes de terrains, en fournissant outils et concepts permettant d'analyser leur structure et en faisant ressortir des propriétés particulières.

Mais si les approches permettant de prendre en compte leurs aspects statiques sont intensément étudiées, il n'en est pas de même pour leurs aspects dynamiques. Cette dynamique se traduit notamment par le fait que la structure du réseau est modifiée, les liens apparaissant et disparaissant au cours du temps, mais aussi par le fait qu'une information peut se propager à travers le réseau, les deux aspects étant fortement liés.

L'objectif de cette thèse est de participer à cet effort de caractérisation des aspect dynamiques des réseaux réels. Pour ce faire, le projet entend se concentrer sur les propriétés des graphes qui mettent en avant l'importance des noeuds en terme de diffusion d'information. Une étape importante dans cette démarche repose alors sur le choix de bonnes propriétés statistiques permettant de synthétiser la dynamique et de mettre en évidence le rôles que les entités jouent en terme de relais.

Dans ce contexte, un certain nombre de propriétés classiques de la théorie des graphes demandent à être reconsidérées dans le cadre dynamique. Parmi celles-ci, on peut citer les propriétés de centralités qui tentent de capturer l'importance d'un noeud au regard de sa position dans le graphe. En effet, les mesures habituelles, comme la centralité d'intermédiarité ou la centralités de proximité, ne s'étendent pas naturellement au cas des graphes dynamiques et aucune proposition ne fait consensus à l'heure actuelle. L'objectif de ce projet est de pallier à ce manque en proposant des métriques pertinentes et en validant les propositions sur des jeux de données réels.

Par ailleurs, cet question de l'identification de propriétés non triviales dans les graphes dynamiques amène à se poser la question des modèles à même de capturer ces propriétés. La problématique consiste à proposer des mécanismes de génération aléatoire de structures qui sont proches des structures réelles. Il s'agit donc ici de proposer des algorithmes de génération aléatoires de graphes dynamiques qui respectent les propriétés de centralités identifiées précédemment.

Enjeux

Le cœur de la thèse consiste à proposer et valider de nouvelles métriques pour caractériser l'importance des noeuds dans les graphes dynamiques ainsi qu'à proposer des modèles qui capturent ces propriétés. Il répond donc à des questions qui se posent en théorie des graphes et amène à renouveler un certains nombres de propriétés définies pour les graphes classiques.

Le projet aura à coeur de valider la pertinence des métriques proposées en exploitant des jeux de données réels et de grande ampleur. À ce titre, le sujet de thèse amène à des enjeux algorithmiques puisque se pose la question du calcul effectif des métriques proposées. La gestion à la fois en temps et en espace devient alors cruciale et amène à l'élaboration d'algorithmes capables de calculer les propriétés à partir d'une connaissance partielle des graphes.

Enfin, la relation entre les propriétés de centralité dynamique et les modèles de génération aléatoire amène également à s'interroger sur les propriétés attendues dans les structures générées aléatoirement, ce afin de renforcer l'intérêt de ces modèles en terme de résultats formels.