An Evaluation of the use of Clustering Coefficient as a Heuristic for the Visualisation of Small World Graphs

Abstract

Many graphs modelling real-world systems are characterised by a high edge density and the small world properties of a low diameter and a high clustering coefficient. In the "small world" class of graphs, the connectivity of nodes follows a power-law distribution with some nodes of high degree acting as hubs. While current layout algorithms are capable of displaying two dimensional node-link visualisations of large data sets, the results for dense small world graphs can be aesthetically unpleasant and difficult to read. In order to make the graph more understandable, we suggest dividing it into clusters built around nodes of interest to the user. This paper describes a graph clustering using the average clustering coefficient as a heuristic for determining which node a vertex should be assigned to. We propose that the use of clustering coefficient as a heuristic aids in the formation of high quality clusters that consist of nodes that are conceptually related to each other. We evaluate the impact of using the clustering coefficient heuristic against other approaches. Once the clustering is performed we lay out the graph using a force directed approach for each clustering individually.