Comparison of algorithms in graph partitioning

Alain Guénoche

RAIRO - Operations Research (2009)

  • Volume: 42, Issue: 4, page 469-484
  • ISSN: 0399-0559

Abstract

top
We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them.

How to cite

top

Guénoche, Alain. "Comparison of algorithms in graph partitioning." RAIRO - Operations Research 42.4 (2009): 469-484. <http://eudml.org/doc/105415>.

@article{Guénoche2009,
abstract = { We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them. },
author = {Guénoche, Alain},
journal = {RAIRO - Operations Research},
keywords = {Graph partitioning; partition comparison; simulation.; graph partitioning; simulation},
language = {eng},
month = {4},
number = {4},
pages = {469-484},
publisher = {EDP Sciences},
title = {Comparison of algorithms in graph partitioning},
url = {http://eudml.org/doc/105415},
volume = {42},
year = {2009},
}

TY - JOUR
AU - Guénoche, Alain
TI - Comparison of algorithms in graph partitioning
JO - RAIRO - Operations Research
DA - 2009/4//
PB - EDP Sciences
VL - 42
IS - 4
SP - 469
EP - 484
AB - We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them.
LA - eng
KW - Graph partitioning; partition comparison; simulation.; graph partitioning; simulation
UR - http://eudml.org/doc/105415
ER -

References

top
  1. C.J. Alpert and A. Kang, Recent direction in netlist partitioning: a survey, Integration. VLSI J.19 (1-2) (1995) 1–81.  Zbl0876.94063
  2. G.D. Bader and C.W. Hogue, An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics4 (2) (2003) 27.  
  3. L. Barabasi, The large-scale organization of metabolic networks. Nature407 (2000) 651–654.  
  4. V. Batagelj and M. Mrvar, Partitioning approach to visualisation of large graphs, Lect. Notes Comput. Sci. 1731, Springer (1999) 90–97.  
  5. V. Batagelj and M. Zaveršnik, An O ( m ) algorithm for cores decomposition of networks (2001).  Zbl1284.05252
  6. S. Brohée and J. van Helden, Evaluation of clustering algorithms for protein-protein interaction networks. BMC Bioinformatics7 (2006) 488.  
  7. C. Brun, C. Herrmann and A. Guénoche, Clustering proteins from interaction networks for the prediction of cellular functions. BMC Bioinformatics5 (2004) 95.  
  8. I. Charon, L. Denoeud, A. Guénoche, and O. Hudry, Comparing partitions by element transfert. J. Classif.23 (1) (2006) 103–121.  Zbl1244.05023
  9. T. Colombo, A. Guénoche, and Y. Quentin, Looking for high density areas in graph: Application to orthologous genes, Actes des Journées Informatiques de Metz, 2003, pp. 203–212.  
  10. W. Day, The complexity of computing metric distances between partitions. Math. Soc. Sci.1 (1981) 269–287.  Zbl0497.62049
  11. S. Van Dongen, Graph Clustering by Flow Simulation. Ph.D. Thesis, University of Utrecht (2000).  
  12. J. Duch and A. Arenas, Community detection in complex networks using Extremal Optimization, (2005) 4 p.  URIarXiv:cond-mat/0501368
  13. A.J. Enright, S. van Dongen and L.A. Ouzounis, An efficient algorithm for large-scale detection of protein families. Nucleic Acids Res.30 (2002) 1575–1584.  
  14. M. Girvan and M.E.J. Newman, Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA99 (2002) 7821–7826.  Zbl1032.91716
  15. A. Guénoche, Partitions optimisées selon différents critères; Evaluation et comparaison. Math. Sci. Hum.161 (2003) 41–58.  
  16. A. Guénoche, Clustering by vertex density in a graph, in Proceedings of IFCS congress. Classification, Clustering and Data Mining Applications, edited by D. Banks et al., Springer (2004) 15–24.  
  17. G.W. Milligan and M.C. Cooper, An examination of procedures for determining the number of clusters in a data set. Psychometrica50 (1985) 159–179.  
  18. J. Moody, Identifying dense clusters in large networks. Social Networks23 (2001) 261–283.  
  19. M.E.J. Newman, Scientific Collaboration Networks: Shortest paths, weighted networks and centrality. Phys. Rev. (2001) 64.  
  20. M.E.J Newman and M. Girvan, Finding and evaluating community structure in networks. Phys. Rev. E69 (2004) 026113.  Zbl1032.91716
  21. M.E.J. Newman, Modularity and community structure in networks. v1, (2006) 7 p.  URIarXiv:physics/0602124
  22. P. Pons and M. Latapy, Computing communities in large networks using random walks. J. Graph Algorithms Appl.10 (2), (2006) 191–218.  Zbl1161.68694
  23. S. Régnier, Sur quelques aspects mathématiques des problèmes de classification automatique. ICC Bulletin (1964).  Zbl0548.62040
  24. J. Rougemont and P. Hingamp, DNA microarray data and contextual analysis of correlation graphs. BMC Bioinformatics4 (2003) 15.  
  25. S.B. Seidman, Network structure and minimum degree. Social Networks5 (1983) 269–287.  
  26. D. Wishart, Mode analysis: generalization of nearest neighbor which reduces chaining effects, in Numerical taxonomy, Academic Press (1976) 282–311.  

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.