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 ... 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 possi ... mehr

Open Access Logo


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