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

Abstract

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

How to cite

top

Gambette, 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. [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. [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. [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. [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. [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. [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. [7] A.C. Davison and D.V. Hinkley, Bootstrap methods and their application. Cambridge University Press (1997). Zbl0886.62001MR1478673
  8. [8] L.R. Dice, Measures of the amount of ecologic association between species. Ecology26 (1945) 297–302. 
  9. [9] J. Duch and A. Arenas, Community detection in complex networks using extremal optimization. Phys. Rev. E 72 (2005) 027104. 
  10. [10] J. Felsenstein, Inferring Phylogenies. Sunderland (MA), Sinauer Associates Inc. (2003). 
  11. [11] S. Fortunato, Community detection in graphs. Phys. Rep.486 (2010) 75–174. 
  12. [12] A. Guénoche, Comparison of algorithms in graph partitioning. RAIRO42 (2008) 469–484. Zbl1198.90379
  13. [13] A. Guénoche, Consensus of partitions : a constructive approach. Adv. Data Anal. Classif.5 (2011) 215–229. Zbl1253.68258
  14. [14] L. Hubert and P. Arabie, Comparing partitions, J. Classif.2 (1985) 193–218. Zbl0587.62128
  15. [15] A.K. Jain and J.V. Moreau, Bootstrap technique in cluster analysis. Pattern Recogn.20 (1987) 547–568. 
  16. [16] M.E.J. Newman, Modularity and community structure in networks. PNAS103 (2006) 8577–8582. 
  17. [17] M.E.J. Newman and M. Girvan, Finding and evaluating community structure in networks. Phys. Rev. E 69 (2004) 026133. Zbl1032.91716
  18. [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. [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. [20] C.T. Zahn, Approximating symmetric relations by equivalence relations. SIAM J. Appl. Math.12 (1964) 840–847. Zbl0129.16003MR172276

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.