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 inherent 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 optimisations, and requires neither global criteria nor any a priori knowledge of the graph. It is presented here as a preliminary phase in a recent approach to graph partitioning problems: transforming the combinatorial problem (minimising edge cuts) into one of clustering by constructing some bijective 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 incorporate it into the clustering heuristic. The heuristic's performance on a well-known class of pseudo-random graphs is assessed according to several metric and combinatorial criteria.