A stochastic heuristic for visualising graph clusters in a bi-dimensional space prior to partitioning

This paper presents a new stochastic heuristic to reveal some structures in herent in large graphs, by displaying spatially separate clusters of highly connected vertex subsets on a two-dimensional grid. The algorithm employed is inspired by a biological model of ant behavior; it proceeds by local op timisations, and requires neither global criteria, nor any a priori knowled ge of the graph. It is presented here as a preliminary phase in a recent ap proach to graph partitioning problems: transforming the combinatorial probl em (minimising edge cuts) into one of clustering by constructing some bijec tive mapping between the graph vertices and points in some geometric space. After reviewing different embeddings proposed in the literature, we define a dissimilarity coefficient on the vertex set which translates the graph's interesting structural properties into distances on the grid, and incorpor ate it into the clustering heuristic. The heuristic's performance on a well -known class of pseudo-random graphs is assessed according to several metri c and combinatorial criteria.