Nouvelle approche de fouille de graphes AC-réduits fréquents

Résumé : La fouille de graphes est devenue une piste de recherche intéressante et un défi réel en matière de fouille de données. Parmi les différentes familles de motifs de graphes, les graphes fréquents permettent une caractérisation intéressante des groupes de graphes, ainsi qu'une discrimination des différents graphes lors de la classification ou de la segmentation. A cause de la NP-complétude du test d'isomorphisme de sous-graphes et de l'immensité de l'espace de recherche, les algorithmes de fouille de graphes sont exponentiels en temps d'exécution et/ou occupation mémoire. Dans cet article, nous étudions un nouvel opérateur de projection polynomial nommé AC-projection basé sur une propriété clé du domaine de la programmation par contraintes, à savoir l'arc consistance. Cet opérateur est censé remplacer l'utilisation de l'isomorphisme de sous-graphes en établissant un biais sur la projection. Cette étude est suivie d'une évaluation expérimentale du pouvoir discriminant des patterns AC-réduits découverts.
Type de document :
Article dans une revue
Revue des Nouvelles Technologies de l'Information, Hermann, 2011, 20 (vol.RNTI-E-20), pp.473-478
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00818206
Contributeur : Michel Liquiere <>
Soumis le : vendredi 26 avril 2013 - 11:57:52
Dernière modification le : jeudi 11 janvier 2018 - 06:26:23

Identifiants

  • HAL Id : lirmm-00818206, version 1

Collections

Citation

Brahim Douar, Michel Liquière, Chiraz Latiri, Yahya Slimani. Nouvelle approche de fouille de graphes AC-réduits fréquents. Revue des Nouvelles Technologies de l'Information, Hermann, 2011, 20 (vol.RNTI-E-20), pp.473-478. 〈lirmm-00818206〉

Partager

Métriques

Consultations de la notice

195