KIT | KIT-Bibliothek | Impressum | Datenschutz

Invariant Graph Partition Comparison Measures

Ball, Fabian 1; Geyer-Schulz, Andreas 1
1 Karlsruher Institut für Technologie (KIT)

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.


Verlagsausgabe §
DOI: 10.5445/IR/1000086785
Veröffentlicht am 22.10.2018
Originalveröffentlichung
DOI: 10.3390/sym10100504
Scopus
Zitationen: 3
Web of Science
Zitationen: 3
Dimensions
Zitationen: 4
Cover der Publikation
Zugehörige Institution(en) am KIT Fakultät für Wirtschaftswissenschaften – Institut für Informationswirtschaft und Marketing (IISM)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2018
Sprache Englisch
Identifikator ISSN: 2073-8994
urn:nbn:de:swb:90-867857
KITopen-ID: 1000086785
Erschienen in Symmetry
Verlag MDPI
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
Schlagwörter graph partitioning; graph clustering; invariant measures; partition comparison; finite automorphism groups; graph automorphisms
Nachgewiesen in Dimensions
Web of Science
Scopus
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page