Séminaire de Mathématiques Discrètes, Optimisation et Décision

Alain Guénoche (IML - CNRS)

Bootstrap Clustering for Graphs

Etant donné un graphe simple non orienté, pondéré ou non pondéré, on cherche à partitionner les sommets du graphe en classes connexes et à mesurer la robustesse des classes. Nous proposons une démarche (appelée Bootstrap Clustering) qui consiste (i) à choisir une méthode de partitionnement adaptée aux graphes, (ii) à construire un certain nombre de graphes similaires au graphe initial, (iii) à appliquer la méthode de partitionnement à chacun de façon à générer un profil de partitions, (iv) à calculer une partition consensus du profil. Ce profil permet de mesurer la robustesse des classes comme le pourcentage moyen de partitions qui classent ensemble les paires réunies. Cette notion s'étend aux partitions et permet de comparer la partition consensus à la partition initiale, généralement la seule calculée. Un protocole de simulations, basé sur des graphes aléatoires structurés en "communautés" plus ou moins marquées, permet de mesurer l'efficacité du Bootstrap Clustering.
 

Retour à la page du séminaire