Symmetry-based Graph Clustering Partition Stability

Stability of clustering partitions (e. g. Gfeller et al., 2005; von Luxburg, 2010) and the problem of how to define good clusters (e. g. Hennig, 2015) are recurring topics in data analysis. We present a novel approach to characterize the stability of graph clustering partitions that is based solely on the graph’s automorphism group. All in all, three formally equivalent definitions are given, each from a different point of view. Two of these conditions are exploited for the design of an algorithm for fast stability detection of a graph clustering partition. These characterizations can be perfectly combined with others in terms of an additional constraint that a “good” clustering solution must fulfill. Our propositions are likely to be generalized for other data formats than graphs, provided the automorphism group is known.