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

TitreExtraction de motifs dans des graphes orientés attribués en présence d'automorphisme
Publication TypeConference Proceedings
Year of Publication2014
AuthorsPasquier, C, Flouvat, F, Sanhes, J, Selmaoui-Folcher, N
Conference Name14èmes Journées Francophones "Extraction et Gestion des Connaissances" (EGC'2014)
VolumeE-26
EditionHermes - RNTI
Pagination371-382
Date Published01/2014
PublisherRevue des Nouvelles Technologie de l'Information
Conference Location28 au 31 Janvier 2014 à Rennes, France.
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 la combinatoire sur les 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-graphe en traitant de manière parti- culière les motifs automorphes.