News

Organisation d’une compétition internationale sur la distance d’édition sur graphes

Organisation d’une compétition internationale sur la distance d’édition sur graphes

Intervention de Benoit Gaüzère lors de la compétition.Les laboratoire GREYC et LITIS ainsi que le laboratoire LI de Tours ont collaboré pour organiser une compétition sur la distance d’édition sur graphes lors de la conférence international ICPR 2016 à Cancun (Mexique).

En deux mots, la distance d’édition entre deux graphes mesure le nombre de transformations (suppression/insertion/changement de label) de sommets ou d’arêtes à appliquer au premier graphe afin qu’il devienne isomorphe au second. Ce problème est NP-difficile.

La compétition a été décomposée en deux parties:

  • Une sous compétition dévolue exclusivement à l’approximation de la distance d’édition
  • Une autre sous compétition, plus générale évaluant différentes métriques entre graphes

Les exécutables où les codes sources des différentes méthodes ont été soumis par les participants afin d’évaluer à la fois la précision des algorithmes et leurs temps de calcul en les faisant tourner sur une même machine. Les graphes utilisés pour la compétition étaient soit des graphes symboliques soit des graphes avec attributs numériques.

Huit méthodes ont été soumises, évaluées et présentées lors d’une sessions spéciale avant la conférence ICPR 2016. Les résultats de l’évaluation ainsi que le protocole exact sont disponibles sur le site de la compétition. Un article présentant une synthèse de ces résultats signé par l’ensemble des organisateurs est actuellement soumis à Pattern Recognition Letters.


Josep Llados

Josep Llados

Benoit Gaüzère

Zeina

Leave a Comment

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Vous pouvez utiliser ces balises et attributs HTML : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>