The Impact of Graph Symmetry on Clustering

This article investigates the effect of graph symmetry on modularity optimal graph clustering partitions. The key finding is that there actually exists an impact of graph symmetry, as more than 22% of the analyzed graphs have an unstable partition. The results are based on an empirical analysis of 1254 symmetric graphs, which are a subset of the 1699 graphs that were analyzed by Ball and Geyer-Schulz (2018a). For each graph a modularity optimal partition is computed by a graph clustering algorithm. Additionally, the generating sets for the automorphism group of each graph are obtained. All computed partitions are tested for stability, which means that the symmetry that is captured by the automorphism group does not change this partition. Furthermore, definitions that allow to distinguish local and global symmetry of graphs are presented.