Bootstrap clustering for graph partitioning

Philippe Gambette 1 Alain Guénoche 2
2 MMG
IML - Institut de mathématiques de Luminy
Abstract : Given a simple undirected weighted or unweighted graph, we try to cluster the vertex set into communities and also to quantify the robustness of these clusters. For that task, we propose a new method, called bootstrap clustering which consists in (i) defining a new clustering algorithm for graphs, (ii) building a set of graphs similar to the initial one, (iii) applying the clustering method to each of them, making a profile (set) of partitions, (iv) computing a consensus partition for this profile, which is the final graph partitioning. This allows to evaluate the robustness of a cluster as the average percentage of partitions in the profile joining its element pairs ; this notion can be extended to partitions. Doing so, the initial and consensus partitions can be compared. A simulation protocol, based on random graphs structured in communities is designed to evaluate the efficiency of the Bootstrap Clustering approach.
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-00676989
Contributeur : Philippe Gambette <>
Soumis le : mercredi 7 mars 2012 - 00:57:39
Dernière modification le : mercredi 11 avril 2018 - 12:12:03
Document(s) archivé(s) le : vendredi 8 juin 2012 - 02:20:51

Fichier

2011GambetteGuenoche.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Citation

Philippe Gambette, Alain Guénoche. Bootstrap clustering for graph partitioning. RAIRO - Operations Research, EDP Sciences, 2011, 45 (4), pp.339-352. ⟨10.1051/ro/2012001⟩. ⟨hal-00676989⟩

Partager

Métriques

Consultations de la notice

636

Téléchargements de fichiers

422