Co-evolution pattern mining in dynamic attributed graphs

Fouille de motifs de co-evolution dans des graphes dynamiques attribués Cette thèse s'est déroulée dans le cadre du projet ANR FOSTER, "FOuille de données Spatio-Temporelles : application à la compréhension et à la surveillance de l'ERosion" (ANR-2010-COSI-012-02, 2011-2014). Dans ce contexte, nous nous sommes intéressés à la modélisation de données spatio-temporelles dans des graphes enrichis de sorte que des calculs de motifs sur de telles données permettent de formuler des hypothèses intéressantes sur les phénomènes à comprendre. Plus précisément, nous travaillons sur la fouille de motifs dans des graphes relationnels (chaque noeud est identifié de fa\c con unique), attribués (chaque noeud du graphe est décrit par des attributs qui sont ici numériques), et dynamiques (les valeurs des attributs et les relations entre les noeuds peuvent évoluer dans le temps). Nous proposons un nouveau domaine de motifs nommé motifs de co-évolution. Ce sont des triplets d'ensembles de noeuds, d'ensembles de pas de temps et d'ensembles d'attributs signés, c'est à dire des attributs associés à une tendance (croissance,décroissance). L'intérêt de ces motifs est de décrire un sous-ensemble des données qui possède un comportement spécifique et a priori intéressant pour conduire des analyses non triviales. Dans ce but, nous définissons deux types de contraintes, une contrainte sur la structure du graphe et une contrainte sur la co-évolution de la valeur des attributs portés par les noeuds. Pour confirmer la spécificité du motif par rapport au reste des données, nous définissons trois mesures de densité qui tendent à répondre à trois questions. À quel point le comportement des noeuds en dehors du motif est similaire à celui des noeuds du motif ? Quel est le comportement du motif dans le temps, est-ce qu'il apparaît soudainement ? Est-ce que les noeuds du motif ont un comportement similaire seulement sur les attributs du motif ou aussi en dehors ? Nous proposons l'utilisation d'une hiérarchie sur les attributs comme connaissance à priori de l'utilisateur afin d'obtenir des motifs plus généraux et adaptons l'ensemble des contraintes à l'utilisation de cette hiérarchie. Finalement, pour simplifier l'utilisation de l'algorithme par l'utilisateur en réduisant le nombre de seuils à fixer et pour extraire uniquement l'ensemble des motifs les plus intéressants, nous utilisons le concept de ``skyline'' réintroduit récemment dans le domaine de la fouille de données. Nous proposons ainsi trois algorithmes MINTAG, H-MINTAG et Sky-H-MINTAG qui sont complets pour extraire l'ensemble de tous les motifs qui respectent les différentes contraintes. L'étude des propriétés des contraintes (anti-monotonie, monotonie/anti-monotonie par parties) nous permet de les pousser efficacement dans les algorithmes proposés et d'obtenir ainsi des extractions sur des données réelles dans des temps raisonnables.