A Quality Metric for Visualization of Clusters in Graphs
This work addresses a specific gap in graph visualization for researchers and practitioners needing to assess cluster representation, but it is incremental as it builds on existing graph quality metrics.
The authors tackled the lack of a metric for evaluating how well graph drawings represent cluster structures, and they defined a new clustering quality metric that effectively captures visual cluster quality variations in experiments.
Traditionally, graph quality metrics focus on readability, but recent studies show the need for metrics which are more specific to the discovery of patterns in graphs. Cluster analysis is a popular task within graph analysis, yet there is no metric yet explicitly quantifying how well a drawing of a graph represents its cluster structure. We define a clustering quality metric measuring how well a node-link drawing of a graph represents the clusters contained in the graph. Experiments with deforming graph drawings verify that our metric effectively captures variations in the visual cluster quality of graph drawings. We then use our metric to examine how well different graph drawing algorithms visualize cluster structures in various graphs; the results con-firm that some algorithms which have been specifically designed to show cluster structures perform better than other algorithms.