KIT | KIT-Bibliothek | Impressum | Datenschutz

Symmetry-based Graph Clustering Partition Stability

Ball, Fabian; Geyer-Schulz, Andreas


Stability of clustering partitions (e. g. Gfeller et al., 2005; von Luxburg, 2010) and the problem of how to define good clusters (e. g. Hennig, 2015) are recurring topics in data analysis. We present a novel approach to characterize the stability of graph clustering partitions that is based solely on the graph’s automorphism group. All in all, three formally equivalent definitions are given, each from a different point of view. Two of these conditions are exploited for the design of an algorithm for fast stability detection of a graph clustering partition. These characterizations can be perfectly combined with others in terms of an additional constraint that a “good” clustering solution must fulfill. Our propositions are likely to be generalized for other data formats than graphs, provided the automorphism group is known.

Verlagsausgabe §
DOI: 10.5445/KSP/1000085951/01
Veröffentlicht am 10.12.2018
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: 2363-9881
KITopen-ID: 1000088364
Erschienen in Archives of Data Science, Series A (Online First)
Band 4
Heft 1
Seiten A01, 21 S. online
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page