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.

Dans ce contexte, l'équipe Data Mining and Machine Learning (DM2L, LIRIS) s'intéresse à expliquer les changements des valeurs de mesures topologiques d'un noeud dans un graphe dynamique par la variation des valeurs de ses attributs dans le passé. En d'autre termes, on cherche à répondre à la question suivante “Quels sont les changements des propriétés d'un noeud qui vont, plus tard, changer aussi son rôle dans le graphe ?”. Pour cela, un algorithme a été défini afin d'extraire des motifs gâchettes illustrés dans la figure 1. On note a+ la variation positive (supérieure à 2) des valeurs de l'attribut a entre deux pas de temps consécutifs. On observe alors le motif [ {a+,b+},{c-},{deg+} ] qui se lit “La variation positive forte de la valeur de a et b est suivie d'une variation négative forte de c, finalement suivie par une variation positive forte du degré du noeud considéré. Sur la figure, on voit que ce motif est supporté par 2 noeuds. Etant donnée un graphe dynamique attribué, l'objectif de l'algorithme est alors d'extraire tous les motifs gâchettes respectant certaines propriétés bien définies.