Encadrants : Marc Plantevit & Mehdi Kaytoue

On se place dans le cadre de l'étude des graphes attribués. Un réseau social est un exemple de graphe attribué, où les noeuds sont les individus, les attributs caractérisent ces individus (âge, nombre de messages, …) et les liens représentent des relations d'amitié partagée. Chaque noeud est aussi décrit par plusieurs mesures topologiques dans le graphes, comme le degré qui compte le nombre de voisins directement connectés, ou la centralité qui mesure son importance dans le graphe. Un graphe dynamique est alors une collection de graphes, chacun pour un temps donné. On observe alors l'évolution d'un graphe par l'apparition ou la disparition de nouveaux noeuds et de nouvelles arêtes, ou encore par des changements de valeurs d’attributs et de mesures topologiques (voir Figure 1). L'étude de graphes dynamiques attribués est importante dans de nombreux domaines d'application, impliquant l'étude d'interactions entre individus, ou encore l'étude de données scientifiques (e.g. sciences du vivant), et extraire des motifs ou régularités afin d'exhiber des phénomènes observés dans cette dynamique est un enjeu important.