Description
Date depot: 1 janvier 1900
Titre: Caractérisation de la dynamique des graphes de terrain : description des invariants
Directrice de thèse:
Clémence MAGNIEN (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Les graphes dynamiques apparaissent dans de nombreux contextes :
réseaux informatiques dans lesquels des machines ou des liens peuvent
subir des pannes, réseaux sociaux dans lesquels des connexions entre
individus apparaissent et disparaissent au cours du temps, graphes du
web dans lesquels des pages sont créées ou supprimées, etc. Jusqu'à
récemment ces objets étaient principalement étudiés sous un angle
statique, c'est-à-dire comme des instantanés du graphe à un instant donné.
Un grand nombre de résultats de ces 10 dernières années ont introduit
un ensemble d'outils pour l'analyse et la description des graphes
statiques, mais peu a été fait pour l'étude de leur dynamique.
Deux problèmes en particulier
se posent pour la caractérisation de la dynamique d'un graphe.
Tout d'abord, plusieurs contraintes sur le processus de capture de la dynamique
(connaître quels nœuds et quels liens sont présents et à quels moments)
font que l'on ne peut pas espérer observer tous les événements,
ce qui induit un biais dans les propriétés observées.
Ensuite, l'étude de la dynamique fait apparaître des disparités à la fois temporelles
et structurelles :
les propriétés observées dépendent du moment où l'on observe le graphe
et de la partie du graphe que l'on étudie (différents nœuds auront des comportements
différents au cours du temps).
Ces deux problématiques se rejoignent dans la notion d'{invariant} :
l'expérience montre que malgré les biais induits par la mesure et
les disparités temporelles et/ou structurelles,
certaines tendances générales émergent.
Un invariant est alors une propriété de la dynamique qui ne dépend pas du moment où l'on
observe le graphe, de la durée pendant laquelle on l'observe,
et qui décrit l'ensemble de la dynamique et non pas le comportement d'un groupe
de nœuds particuliers.
Une propriété invariante est donc une propriété à la fois bien évaluée et représentative
de la dynamique du graphe.
Doctorant.e: Benamara Lamia