Séminaire Donnees et APprentissage Artificiel
Mesurer la similarité de graphes
Jeudi 25 septembre 2008Christine Solnon (LIRIS Lyon)
De nombreuses applications comme, par exemple, la recherche d'information, la reconnaissance de formes ou le raisonnement à partir de cas, nécessitent d'évaluer la similarité d'objets. On s'intéressera dans cet exposé au cas où les objets sont décrits par des graphes. On présentera tout d'abord un certain nombre de mesures ou distances permettant d'évaluer la similarité de graphes : des mesures basées sur des appariements univoques, où chaque sommet est apparié à au plus un sommet de l'autre graphe (isomorphisme de (sous-)graphes, plus grand sous-graphe commun, distance d'édition de graphes), puis des mesures basées sur des appariements multivoques, où un sommet peut être apparié à plusieurs sommets de l'autre graphe. On présentera ensuite différents algorithmes permettant de calculer la similarité de graphes : des algorithmes basés sur une exploration exhaustive combinée à des techniques de filtrage pour des mesures basées sur des appariements univoques, puis des algorithmes basés sur une exploration heuristique (recherche taboue réactive et optimisation par colonies de fourmis) pour des mesures basées sur des appariements multivoques.
Plus d'informations ici …
Thomas.Baerecke (at) nulllip6.fr