Bootstrap clustering for graph partitioning - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue RAIRO - Operations Research Année : 2011

Bootstrap clustering for graph partitioning

Résumé

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.
Fichier principal
Vignette du fichier
2011GambetteGuenoche.pdf (253.73 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-00676989 , version 1 (07-03-2012)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More