Description
Date depot: 1 janvier 1900
Titre: Caractérisation de la dynamique des réseaux : analyse et modélisation
Directrice de thèse:
Clémence MAGNIEN (LIP6)
Encadrant :
Fabien TARISSAN (ISP)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
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.
Doctorant.e: Ghanem Abdelmotaal Marwan Tarek