Comparison of algorithms in graph partitioning
IML-CNRS, 163 Av. de Luminy, 13288 Marseille Cedex 9, France; firstname.lastname@example.org
Accepted: 9 January 2008
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.
Mathematics Subject Classification: 05C85 / 90C35 / 90C59
Key words: Graph partitioning / partition comparison / simulation.
© EDP Sciences, ROADEF, SMAI, 2008