KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
§
Verlagsausgabe
DOI: 10.5445/IR/1000086785
Veröffentlicht am 22.10.2018
Originalveröffentlichung
DOI: 10.3390/sym10100504

Invariant Graph Partition Comparison Measures

Ball, Fabian; Geyer-Schulz, Andreas

Abstract:
Symmetric graphs have non-trivial automorphism groups. This article starts with the proof that all partition comparison measures we have found in the literature fail on symmetric graphs, because they are not invariant with regard to the graph automorphisms. By the construction of a pseudometric space of equivalence classes of permutations and with Hausdorff’s and von Neumann’s methods of constructing invariant measures on the space of equivalence classes, we design three different families of invariant measures, and we present two types of invariance proofs. Last, but not least, we provide algorithms for computing invariant partition comparison measures as pseudometrics on the partition space. When combining an invariant partition comparison measure with its classical counterpart, the decomposition of the measure into a structural difference and a difference contributed by the group automorphism is derived.


Zugehörige Institution(en) am KIT Institut für Informationswirtschaft und Marketing (IISM)
Publikationstyp Zeitschriftenaufsatz
Jahr 2018
Sprache Englisch
Identifikator ISSN: 2073-8994
URN: urn:nbn:de:swb:90-867857
KITopen ID: 1000086785
Erschienen in Symmetry
Band 10
Heft 10
Seiten Article: 504
Bemerkung zur Veröffentlichung Gefördert durch den KIT-Publikationsfonds
Vorab online veröffentlicht am 15.10.2018
Schlagworte graph partitioning; graph clustering; invariant measures; partition comparison; finite automorphism groups; graph automorphisms
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page