Comparison of algorithms in graph partitioning

 Access to full text

 Full (PDF)

1. [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. [2] G.D. Bader and C.W. Hogue, An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4 (2) (2003) 27. 
3. [3] L. Barabasi, The large-scale organization of metabolic networks. Nature 407 (2000) 651–654. 
4. [4] V. Batagelj and M. Mrvar, Partitioning approach to visualisation of large graphs, Lect. Notes Comput. Sci. 1731, Springer (1999) 90–97. MR1856764
5. [5] V. Batagelj and M. Zaveršnik, An $O\left(m\right)$ algorithm for cores decomposition of networks (2001). 
6. [6] S. Brohée and J. van Helden, Evaluation of clustering algorithms for protein-protein interaction networks. BMC Bioinformatics 7 (2006) 488. 
7. [7] C. Brun, C. Herrmann and A. Guénoche, Clustering proteins from interaction networks for the prediction of cellular functions. BMC Bioinformatics 5 (2004) 95. 
8. [8] I. Charon, L. Denoeud, A. Guénoche, and O. Hudry, Comparing partitions by element transfert. J. Classif. 23 (1) (2006) 103–121. Zbl1244.05023MR2280697
9. [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. [10] W. Day, The complexity of computing metric distances between partitions. Math. Soc. Sci. 1 (1981) 269–287. Zbl0497.62049MR616380
11. [11] S. Van Dongen, Graph Clustering by Flow Simulation. Ph.D. Thesis, University of Utrecht (2000). 
12. [12] J. Duch and A. Arenas, Community detection in complex networks using Extremal Optimization, arXiv:cond-mat/0501368 (2005) 4 p. 
13. [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. [14] M. Girvan and M.E.J. Newman, Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99 (2002) 7821–7826. Zbl1032.91716MR1908073
15. [15] A. Guénoche, Partitions optimisées selon différents critères; Evaluation et comparaison. Math. Sci. Hum. 161 (2003) 41–58. MR2006114
16. [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. MR2113593
17. [17] G.W. Milligan and M.C. Cooper, An examination of procedures for determining the number of clusters in a data set. Psychometrica 50 (1985) 159–179. 
18. [18] J. Moody, Identifying dense clusters in large networks. Social Networks 23 (2001) 261–283. 
19. [19] M.E.J. Newman, Scientific CollaborationNetworks: Shortest paths, weighted networks and centrality. Phys. Rev. (2001) 64. 
20. [20] M.E.J Newman and M. Girvan, Finding and evaluating community structure in networks. Phys. Rev. E 69 (2004) 026113. Zbl1032.91716
21. [21] M.E.J. Newman, Modularity and community structure in networks. arXiv:physics/0602124v1, (2006) 7 p. MR2282139
22. [22] P. Pons and M. Latapy, Computing communities in large networks using random walks. J. Graph Algorithms Appl. 10 (2), (2006) 191–218. Zbl1161.68694MR2302165
23. [23] S. Régnier, Sur quelques aspects mathématiques des problèmes de classification automatique. ICC Bulletin (1964). Zbl0548.62040
24. [24] J. Rougemont and P. Hingamp, DNA microarray data and contextual analysis of correlation graphs. BMC Bioinformatics 4 (2003) 15. 
25. [25] S.B. Seidman, Network structure and minimum degree. Social Networks 5 (1983) 269–287. MR721295
26. [26] D. Wishart, Mode analysis: generalization of nearest neighbor which reduces chaining effects, in Numerical taxonomy, Academic Press (1976) 282–311.