|
Mesurer la similarité de graphes| old_uid | 5294 |
|---|
| title | Mesurer la similarité de graphes |
|---|
| start_date | 2008/09/25 |
|---|
| schedule | 10h |
|---|
| online | no |
|---|
| location_info | salle 549 |
|---|
| summary | De nombreuses applications comme, par exemple, la recherche d'information, la reconnaissance de formes ou le raisonnement a partir de cas, necessitent d'evaluer la similarite d'objets. On s'interessera dans cet expose au cas ou les objets sont decrits par des graphes.
On presentera tout d'abord un certain nombre de mesures ou distances permettant d'evaluer la similarite de graphes : des mesures basees sur des appariements univoques, ou chaque sommet est apparie a au plus un sommet de l'autre graphe (isomorphisme de (sous-)graphes, plus grand sous-graphe commun, distance d'edition de graphes), puis des mesures basees sur des appariements multivoques, ou un sommet peut etre apparie a plusieurs sommets de l'autre graphe.
On presentera ensuite differents algorithmes permettant de calculer la similarite de graphes : des algorithmes bases sur une exploration exhaustive combinee a des techniques de filtrage pour des mesures basees sur des appariements univoques, puis des algorithmes bases sur une exploration heuristique (recherche taboue reactive et optimisation par colonies de fourmis) pour des mesures basees sur des appariements multivoques. |
|---|
| responsibles | Bouchon-Meunier, Diaz, Gallinari |
|---|
| |
|