Extraction de motifs dans des graphes orientés attribués en présence d'automorphisme

Abstract

Les graphes orientés attribués sont des graphes orientés dans lesquels les nœuds sont associés à un ensemble d'attributs. De nombreuses données, is- sues du monde réel, peuvent être représentées par ce type de structure, mais encore peu d'algorithmes sont capables de les traiter directement. La fouille des graphes attribués est difficile, car elle nécessite de combiner l'exploration de la structure du graphe avec l'identification d'itemsets fréquents. De plus, du fait de l'explosion combinatoire des itemsets, les isomorphismes de sous-graphes, dont la présence impacte énormément les performances des algorithmes de fouille, sont beaucoup plus nombreux que dans les graphes étiquetés. Dans cet article, nous présentons une nouvelle méthode de fouille de données qui permet d'extraire des motifs fréquents à partir d'un ou de plusieurs graphes orientés attribués. Nous montrons comment réduire l'explosion combinatoire provoquée par les isomorphismes de sous-graphes en traitant de manière par- ticulière les motifs automorphes

Publication
14ème Conférence Francophone sur l'Extraction et la Gestion des Connaissances (EGC'14), Revue des Nouvelles Technologies de l'Information, volume E-26

Related