Bootstrap clustering for graph partitioning∗

Philippe Gambette; Alain Guénoche

RAIRO - Operations Research (2012)

  • 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 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
  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. E82 (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.  
  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.  
  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.  
  6. 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.  
  7. A.C. Davison and D.V. Hinkley, Bootstrap methods and their application. Cambridge University Press (1997).  
  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. E72 (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.  
  13. A. Guénoche, Consensus of partitions : a constructive approach. Adv. Data Anal. Classif.5 (2011) 215–229.  
  14. L. Hubert and P. Arabie, Comparing partitions, J. Classif.2 (1985) 193–218.  
  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. E69 (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. Bulletin4 (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.  

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.