# Bootstrap clustering for graph partitioning∗

Philippe Gambette; Alain Guénoche

RAIRO - Operations Research (2012)

- 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 45.4 (2012): 339-352. <http://eudml.org/doc/222512>.

@article{Gambette2012,

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

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

language = {eng},

month = {3},

number = {4},

pages = {339-352},

publisher = {EDP Sciences},

title = {Bootstrap clustering for graph partitioning∗},

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

volume = {45},

year = {2012},

}

TY - JOUR

AU - Gambette, Philippe

AU - Guénoche, Alain

TI - Bootstrap clustering for graph partitioning∗

JO - RAIRO - Operations Research

DA - 2012/3//

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; graph partitioning

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

ER -

## References

top- D. Aloise, S. Cafieri, G. Caporossi, P. Hansen, L. Liberti and S. Perron, Column generation algorithms for exact modularity maximization in networks. Phys. Rev. E82 (2010) 046112.
- 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.
- J.P. Barthélemy and B. Leclerc, The median procedure for partitions. DIMACS series in Discrete Mathematics and Theoretical Computer Science19 (1995) 3–34.
- V. Blondel, J.-L. Guillaume, R. Lambiotte and E. Lefebvre, Fast unfolding of communities in large networks. J. Stat. Mech. Theor. Exp. (2008) P10008.
- 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.
- S.V. Dale and C.J. StoeckertJr., Computational modeling of the Plasmodium falciparum interactome reveals protein function on a genome-wide scale. Gen. Res.16 (2006) 542–549.
- A.C. Davison and D.V. Hinkley, Bootstrap methods and their application. Cambridge University Press (1997).
- L.R. Dice, Measures of the amount of ecologic association between species. Ecology26 (1945) 297–302.
- J. Duch and A. Arenas, Community detection in complex networks using extremal optimization. Phys. Rev. E72 (2005) 027104.
- J. Felsenstein, Inferring Phylogenies. Sunderland (MA), Sinauer Associates Inc. (2003).
- S. Fortunato, Community detection in graphs. Phys. Rep.486 (2010) 75–174.
- A. Guénoche, Comparison of algorithms in graph partitioning. RAIRO42 (2008) 469–484.
- A. Guénoche, Consensus of partitions : a constructive approach. Adv. Data Anal. Classif.5 (2011) 215–229.
- L. Hubert and P. Arabie, Comparing partitions, J. Classif.2 (1985) 193–218.
- A.K. Jain and J.V. Moreau, Bootstrap technique in cluster analysis. Pattern Recogn.20 (1987) 547–568.
- M.E.J. Newman, Modularity and community structure in networks. PNAS103 (2006) 8577–8582.
- M.E.J. Newman and M. Girvan, Finding and evaluating community structure in networks. Phys. Rev. E69 (2004) 026133.
- 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.
- S. Régnier, Sur quelques aspects mathématiques des problèmes de classification automatique. I.C.C. Bulletin4 (1965) 175–191. Reprint, Math. Sci. Hum.82 (1983) 13–29.
- C.T. Zahn, Approximating symmetric relations by equivalence relations. SIAM J. Appl. Math.12 (1964) 840–847.

## NotesEmbed ?

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