KIT | KIT-Bibliothek | Impressum | Datenschutz

The Impact of Graph Symmetry on Clustering

Ball, Fabian; Geyer-Schulz, Andreas

Abstract:
This article investigates the effect of graph symmetry on modularity optimal graph clustering partitions. The key finding is that there actually exists an impact of graph symmetry, as more than 22% of the analyzed graphs have an unstable partition. The results are based on an empirical analysis of 1254 symmetric graphs, which are a subset of the 1699 graphs that were analyzed by Ball and Geyer-Schulz (2018a). For each graph a modularity optimal partition is computed by a graph clustering algorithm. Additionally, the generating sets for the automorphism group of each graph are obtained. All computed partitions are tested for stability, which means that the symmetry that is captured by the automorphism group does not change this partition. Furthermore, definitions that allow to distinguish local and global symmetry of graphs are presented.

Open Access Logo


Verlagsausgabe §
DOI: 10.5445/KSP/1000087327/09
Veröffentlicht am 04.11.2019
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Informationswirtschaft und Marketing (IISM)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2018
Sprache Englisch
Identifikator ISSN: 2363-9881
KITopen-ID: 1000099550
Erschienen in Archives of Data Science, Series A (Online First)
Band 5
Heft 1
Seiten A09, 19 S. online
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page