KIT | KIT-Bibliothek | Impressum | Datenschutz

Weak Invariants of Actions of the Automorphism Group of a Graph

Ball, Fabian; Geyer-Schulz, Andreas

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.

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