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.
Mots-clés : graph partitioning, partition comparison, simulation
@article{RO_2008__42_4_469_0,
author = {Gu\'enoche, Alain},
title = {Comparison of algorithms in graph partitioning},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {469--484},
publisher = {EDP-Sciences},
volume = {42},
number = {4},
year = {2008},
doi = {10.1051/ro:2008029},
mrnumber = {2469107},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro:2008029/}
}
TY - JOUR AU - Guénoche, Alain TI - Comparison of algorithms in graph partitioning JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2008 SP - 469 EP - 484 VL - 42 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro:2008029/ DO - 10.1051/ro:2008029 LA - en ID - RO_2008__42_4_469_0 ER -
%0 Journal Article %A Guénoche, Alain %T Comparison of algorithms in graph partitioning %J RAIRO - Operations Research - Recherche Opérationnelle %D 2008 %P 469-484 %V 42 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro:2008029/ %R 10.1051/ro:2008029 %G en %F RO_2008__42_4_469_0
Guénoche, Alain. Comparison of algorithms in graph partitioning. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 4, pp. 469-484. doi : 10.1051/ro:2008029. http://archive.numdam.org/articles/10.1051/ro:2008029/
[1] and , Recent direction in netlist partitioning: a survey, Integration. VLSI J. 19 (1-2) (1995) 1-81. | Zbl
[2] and , An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4 (2) (2003) 27.
[3] , The large-scale organization of metabolic networks. Nature 407 (2000) 651-654.
[4] and , Partitioning approach to visualisation of large graphs, Lect. Notes Comput. Sci. 1731, Springer (1999) 90-97. | MR
[5] and , An algorithm for cores decomposition of networks (2001).
[6] and , Evaluation of clustering algorithms for protein-protein interaction networks. BMC Bioinformatics 7 (2006) 488.
[7] , and , Clustering proteins from interaction networks for the prediction of cellular functions. BMC Bioinformatics 5 (2004) 95.
[8] , , , and , Comparing partitions by element transfert. J. Classif. 23 (1) (2006) 103-121. | MR
[9] , , and , Looking for high density areas in graph: Application to orthologous genes, Actes des Journées Informatiques de Metz, 2003, pp. 203-212.
[10] , The complexity of computing metric distances between partitions. Math. Soc. Sci. 1 (1981) 269-287. | MR | Zbl
[11] , Graph Clustering by Flow Simulation. Ph.D. Thesis, University of Utrecht (2000).
[12] and , Community detection in complex networks using Extremal Optimization, arXiv:cond-mat/0501368 (2005) 4 p.
[13] , and , An efficient algorithm for large-scale detection of protein families. Nucleic Acids Res. 30 (2002) 1575-1584.
[14] and , Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99 (2002) 7821-7826. | MR | Zbl
[15] , Partitions optimisées selon différents critères; Evaluation et comparaison. Math. Sci. Hum. 161 (2003) 41-58. | MR
[16] , 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. | MR
[17] and , An examination of procedures for determining the number of clusters in a data set. Psychometrica 50 (1985) 159-179.
[18] , Identifying dense clusters in large networks. Social Networks 23 (2001) 261-283.
[19] , Networks: Shortest paths, weighted networks and centrality. Phys. Rev. (2001) 64.
[20] and , Finding and evaluating community structure in networks. Phys. Rev. E 69 (2004) 026113.
[21] , Modularity and community structure in networks. arXiv:physics/0602124v1, (2006) 7 p. | MR
[22] and , Computing communities in large networks using random walks. J. Graph Algorithms Appl. 10 (2), (2006) 191-218. | MR
[23] , Sur quelques aspects mathématiques des problèmes de classification automatique. ICC Bulletin (1964).
[24] and , DNA microarray data and contextual analysis of correlation graphs. BMC Bioinformatics 4 (2003) 15.
[25] , Network structure and minimum degree. Social Networks 5 (1983) 269-287. | MR
[26] , Mode analysis: generalization of nearest neighbor which reduces chaining effects, in Numerical taxonomy, Academic Press (1976) 282-311.
Cité par Sources :
