# Bootstrap clustering for graph partitioning

Philippe Gambette; Alain Guénoche

RAIRO - Operations Research - Recherche Opérationnelle (2011)

- Volume: 45, Issue: 4, page 339-352
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topGambette, Philippe, and Guénoche, Alain. "Bootstrap clustering for graph partitioning." RAIRO - Operations Research - Recherche Opérationnelle 45.4 (2011): 339-352. <http://eudml.org/doc/275085>.

@article{Gambette2011,

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.},

author = {Gambette, Philippe, Guénoche, Alain},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {graph partitioning; clustering; modularity; consensus of partitions; bootstrap},

language = {eng},

number = {4},

pages = {339-352},

publisher = {EDP-Sciences},

title = {Bootstrap clustering for graph partitioning},

url = {http://eudml.org/doc/275085},

volume = {45},

year = {2011},

}

TY - JOUR

AU - Gambette, Philippe

AU - Guénoche, Alain

TI - Bootstrap clustering for graph partitioning

JO - RAIRO - Operations Research - Recherche Opérationnelle

PY - 2011

PB - EDP-Sciences

VL - 45

IS - 4

SP - 339

EP - 352

AB - 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.

LA - eng

KW - graph partitioning; clustering; modularity; consensus of partitions; bootstrap

UR - http://eudml.org/doc/275085

ER -

## References

top- [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. Zbl1146.05019MR2395285
- [3] J.P. Barthélemy and B. Leclerc, The median procedure for partitions. DIMACS series in Discrete Mathematics and Theoretical Computer Science19 (1995) 3–34. Zbl0814.62031MR1326609
- [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. Zbl1141.68519
- [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). Zbl0886.62001MR1478673
- [8] L.R. Dice, Measures of the amount of ecologic association between species. Ecology26 (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. RAIRO42 (2008) 469–484. Zbl1198.90379
- [13] A. Guénoche, Consensus of partitions : a constructive approach. Adv. Data Anal. Classif.5 (2011) 215–229. Zbl1253.68258
- [14] L. Hubert and P. Arabie, Comparing partitions, J. Classif.2 (1985) 193–218. Zbl0587.62128
- [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. PNAS103 (2006) 8577–8582.
- [17] M.E.J. Newman and M. Girvan, Finding and evaluating community structure in networks. Phys. Rev. E 69 (2004) 026133. Zbl1032.91716
- [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. Zbl0548.62040
- [20] C.T. Zahn, Approximating symmetric relations by equivalence relations. SIAM J. Appl. Math.12 (1964) 840–847. Zbl0129.16003MR172276

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.