KIT | KIT-Bibliothek | Impressum

Weak Invariants of Actions of the Automorphism Group of a Graph

Ball, Fabian; Geyer-Schulz, Andreas

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.


Zugehörige Institution(en) am KIT Institut für Informationswirtschaft und Marketing (IISM)
Publikationstyp Zeitschriftenaufsatz
Jahr 2017
Sprache Englisch
Identifikator DOI: 10.5445/KSP/1000058749/02
ISSN: 2363-9881
URN: urn:nbn:de:swb:90-656464
KITopen ID: 1000065646
Erschienen in Archives of Data Science Series A (Online-First)
Band 2
Heft 1
Seiten 22 S. online
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page