Indexation de graphes à partir d'une structure d'hypergraphe

Overview & Synopsis

Dans ce papier, nous proposons une nouvelle méthode de clustering de graphes basée sur une modélisation d'hypergraphe. En premier lieu, nous appliquons un algorithme de sélection de prototype dédié aux bases de graphes où le nombre de prototype à sélectionner est déduit automatiquement. En second lieu, nous définissons une méthode de chevauchement des classes pour aboutir à la structure d'hypergraphe, où les hyperarcs sont les classes et les noeuds sont les graphes. Ainsi, un graphe peut être attribué à une ou plusieurs classes. L'originalité de notre approche réside dans la structure d'hypergraphe qui nous permet d'indexer une base de graphes à partir des centroïdes des hyperarcs. En plus, cette nouvelle approche permet de rechercher des graphes similaires à une requête et de naviguer dans une base de graphes en parcourant la structure d'hypergraphe.