Bootstrap clustering for graph partitioning
RAIRO - Operations Research - Recherche Opérationnelle, Tome 45 (2011) no. 4, pp. 339-352.

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.

DOI : 10.1051/ro/2012001
Classification : 05C85, 90C35, 62F40
Mots-clés : graph partitioning, clustering, modularity, consensus of partitions, bootstrap 
@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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ro/2012001/

[1] D. Aloise, S. Cafieri, G. Caporossi, P. Hansen, L. Liberti and S. Perron, Column generation algorithms for exact modularity maximization in networks. Phys. Rev. E 82 (2010) 046112.

[2] J.B. Angelelli, A. Baudot, C. Brun and A. Guénoche, Two local dissimilarity measures for weighted graph with application to biological networks. Adv. Data Anal. Classif. 2 (2008) 3-16. | MR | Zbl

[3] J.P. Barthélemy and B. Leclerc, The median procedure for partitions. DIMACS series in Discrete Mathematics and Theoretical Computer Science 19 (1995) 3-34. | MR | Zbl

[4] V. Blondel, J.-L. Guillaume, R. Lambiotte and E. Lefebvre, Fast unfolding of communities in large networks. J. Stat. Mech. Theor. Exp. (2008) P10008.

[5] U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski and D. Wagner, On modularity - NP-completeness and beyond. Proceedings of WG 2007. Lett. Notes Comput. Sci. 4769 (2007) 121-132. | Zbl

[6] S.V. Dale and C.J. Stoeckert Jr., Computational modeling of the Plasmodium falciparum interactome reveals protein function on a genome-wide scale. Gen. Res. 16 (2006) 542-549.

[7] A.C. Davison and D.V. Hinkley, Bootstrap methods and their application. Cambridge University Press (1997). | MR | Zbl

[8] L.R. Dice, Measures of the amount of ecologic association between species. Ecology 26 (1945) 297-302.

[9] J. Duch and A. Arenas, Community detection in complex networks using extremal optimization. Phys. Rev. E 72 (2005) 027104.

[10] J. Felsenstein, Inferring Phylogenies. Sunderland (MA), Sinauer Associates Inc. (2003).

[11] S. Fortunato, Community detection in graphs. Phys. Rep. 486 (2010) 75-174.

[12] A. Guénoche, Comparison of algorithms in graph partitioning. RAIRO 42 (2008) 469-484. | Zbl

[13] A. Guénoche, Consensus of partitions : a constructive approach. Adv. Data Anal. Classif. 5 (2011) 215-229. | Zbl

[14] L. Hubert and P. Arabie, Comparing partitions, J. Classif. 2 (1985) 193-218. | Zbl

[15] A.K. Jain and J.V. Moreau, Bootstrap technique in cluster analysis. Pattern Recogn. 20 (1987) 547-568.

[16] M.E.J. Newman, Modularity and community structure in networks. PNAS 103 (2006) 8577-8582.

[17] M.E.J. Newman and M. Girvan, Finding and evaluating community structure in networks. Phys. Rev. E 69 (2004) 026133.

[18] A. Noack and R. Rotta, Multi-level algorithms for modularity clustering, Proceedings of SEA'2009, edited by J. Vahrenhold. Lett. Notes Comput. Sci. 5526 (2009) 257-268.

[19] S. Régnier, Sur quelques aspects mathématiques des problèmes de classification automatique. I.C.C. Bulletin 4 (1965) 175-191. Reprint, Math. Sci. Hum. 82 (1983) 13-29.

[20] C.T. Zahn, Approximating symmetric relations by equivalence relations. SIAM J. Appl. Math. 12 (1964) 840-847. | MR | Zbl

Cité par Sources :