User Tools

Site Tools


Sidebar

Practical Information:

Teaching:

Bâtiment Nautibus
43, Bd du 11 Novembre 1918
69622 Villeurbanne Cedex.
☏: +33(0)472 43 16 35
email: marc.plantevit-at-univ-lyon1.fr

Research:

Bureau 501.319
Bâtiment Blaise Pascal
7, Avenue Jean Capelle
69621 Villeurbanne Cedex
☏: +33(0)472 43 84 87
Fax: +33(0)472 43 87 13
email: marc.plantevit-at-liris.cnrs.fr

prim1314triggering

Fouille de graphes dynamiques attribués

Des motifs pour expliquer les changements topologiques

Encadrants : Marc Plantevit (Marc(dot)Plantevit(AT)liris.cnrs.fr) & Mehdi Kaytoue (Mehdi(dot)Kaytoue(AT)liris.cnrs.fr)

Contexte

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.

 Un exemple de graphe dynamique attribué

Existant

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.

Deux exemples du graphe induit par les noeuds supportant un motif extrait à partir de données réelles

Travail Demandé

Tout d'abord, il s'agira de se familiariser avec les notions classiques de fouilles de motifs (séquentiels), et des propriétés de graphes. Il faudra ensuite comprendre l'algorithme, composé de trois étapes : description de chaque noeud par une séquence de variations de valeurs d'attributs, fouille de motifs caractéristiques, et post-traitement de ces motifs. Il sera demandé de programmer les étapes une et deux en C++ (Code java existant dans un certaine mesure) et d'expérimenter l’algorithme sur trois jeu de données existants : un réseau de co-auteurs de publications scientifiques (DBLP), un réseau du trafic aérien aux États-Unis (RITA), et enfin des données issues du site del.ico.us. L'interprétation des résultats d'expérimentation vous pousserons à vous questionner sur les choix faits pour caractériser ce qu'est une “variation de valeur d'attribut”.

Bibliographie

  • Dong, G. et J. Li (1999). Efficient mining of emerging patterns : discovering trends and dif- ferences. In Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’99, New York, NY, USA, pp. 43–52. ACM.
  • Pei, J., J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, et M. Hsu (2001). Prefixspan : Mining sequential patterns by prefix-projected growth. In D. Georgakopoulos et A. Buch- mann (Eds.), ICDE, pp. 215–224. IEEE Computer Society.
  • Yan, X., J. Han, et R. Afshar (2003). Clospan : Mining closed sequential patterns in large databases. In D. Barbará et C. Kamath (Eds.), SDM. SIAM.
  • E. Desmier, M. Plantevit, C. Robardet, and J.-F. Boulicaut. Trend mining in dynamic attributed graphs. In ECML/PKDD, pages 654–669, 2013.
prim1314triggering.txt · Last modified: 2013/10/15 17:15 by mplantev

CNRS INSA de Lyon Université Lyon 1 Université Lyon 2 École centrale de Lyon