| Title | Weak Invariants of Actions of the Automorphism Group of a Graph |
| Authors | Ball, Fabian and Geyer-Schulz, Andreas |
| Year | 2017 |
| Volume | Archives of Data Science, Series A 2(1) / 2017 |
| 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. |