Article Details

Title Weak Invariants of Actions of the Automorphism Group of a Graph
Authors Ball, Fabian and Geyer-Schulz, Andreas
Year 2017
Volume 2(1)
Abstract Automorphism groups of graphs may lead to multiple equivalent solutions of graph-clustering algorithms and to a certain degree of arbitrariness in selecting one or more solution(s) as well as to problems with partition comparison measures. Knowledge of the automorphism group is crucial for stability analysis, for evaluating the degree of arbitrariness involved in selecting a solution, as well as for a further classification as congruent solutions or structurally equivalent solutions. For this purpose we identify three weak invariants of group actions of the automorphism group of a graph, namely modularity, partition type, and the Kolmogorov-Sinai entropy. In particular, we extend the Kolmogorov-Sinai entropy for measuring the uncertainty in finite permutation groups and we apply the underlying construction for testing if multiple structurally equivalent solutions exist for a given graph partition.