KIT | KIT-Bibliothek | Impressum | Datenschutz

Impact of Symmetries in Graph Clustering

Ball, Fabian

Abstract:

Diese Dissertation beschäftigt sich mit der durch die Automorphismusgruppe definierten Symmetrie von Graphen und wie sich diese auf eine Knotenpartition, als Ergebnis von Graphenclustering, auswirkt. Durch eine Analyse von nahezu 1700 Graphen aus verschiedenen Anwendungsbereichen kann gezeigt werden, dass mehr als 70 % dieser Graphen Symmetrien enthalten. Dies bildet einen Gegensatz zum kombinatorischen Beweis, der besagt, dass die Wahrscheinlichkeit eines zufälligen Graphen symmetrisch zu sein bei zunehmender Größe gegen Null geht. Das Ergebnis rechtfertigt damit die Wichtigkeit weiterer Untersuchungen, die auf mögliche Auswirkungen der Symmetrie eingehen. ... mehr

Abstract (englisch):

This dissertation is about how the graph symmetry, which is defined by the graph’s automorphism group, has an impact on the result of a graph clustering algorithm—a partition of nodes. By the analysis of nearly 1700 graphs from diverse application domains we can show that more than 70 % of these graphs contain symmetries. This is a contradiction to the theoretical result from combinatorics which says that the probability of increasingly large random graphs to be symmetric tends to zero. The result justifies the importance of further research that investigates the possible impact of this symmetry. ... mehr


Volltext §
DOI: 10.5445/IR/1000090492
Veröffentlicht am 05.02.2019
Cover der Publikation
Zugehörige Institution(en) am KIT Fakultät für Wirtschaftswissenschaften – Institut für Informationswirtschaft und Marketing (IISM)
Publikationstyp Hochschulschrift
Publikationsjahr 2019
Sprache Englisch
Identifikator urn:nbn:de:swb:90-904929
KITopen-ID: 1000090492
Verlag Karlsruher Institut für Technologie (KIT)
Umfang IX, 238 S.
Art der Arbeit Dissertation
Fakultät Fakultät für Wirtschaftswissenschaften (WIWI)
Institut Fakultät für Wirtschaftswissenschaften – Institut für Informationswirtschaft und Marketing (IISM)
Prüfungsdatum 16.01.2019
Externe Relationen Forschungsdaten/Software
Forschungsdaten/Software
Forschungsdaten/Software
Forschungsdaten/Software
Schlagwörter graph clustering, graph symmetry, graph automorphisms, graph partitioning, network analysis, graph analysis, entropy
Relationen in KITopen
Referent/Betreuer Geyer-Schulz, A.
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page