Voir la notice de l'article provenant de la source Numdam
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.
@article{RO_2011__45_4_339_0,
author = {Gambette, Philippe and Gu\'enoche, Alain},
title = {Bootstrap clustering for graph partitioning},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {339--352},
publisher = {EDP-Sciences},
volume = {45},
number = {4},
year = {2011},
doi = {10.1051/ro/2012001},
mrnumber = {2935706},
zbl = {1238.05116},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2012001/}
}
TY - JOUR AU - Gambette, Philippe AU - Guénoche, Alain TI - Bootstrap clustering for graph partitioning JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2011 SP - 339 EP - 352 VL - 45 IS - 4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2012001/ DO - 10.1051/ro/2012001 LA - en ID - RO_2011__45_4_339_0 ER -
%0 Journal Article %A Gambette, Philippe %A Guénoche, Alain %T Bootstrap clustering for graph partitioning %J RAIRO - Operations Research - Recherche Opérationnelle %D 2011 %P 339-352 %V 45 %N 4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2012001/ %R 10.1051/ro/2012001 %G en %F RO_2011__45_4_339_0
Gambette, Philippe; Guénoche, Alain. Bootstrap clustering for graph partitioning. RAIRO - Operations Research - Recherche Opérationnelle, Tome 45 (2011) no. 4, pp. 339-352. doi: 10.1051/ro/2012001
Cité par Sources :