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. ... mehrBei der Analyse werden sowohl sehr kleine Graphen (<100 Knoten/Kanten) als auch sehr große Graphen (>10 000 000 Knoten/>25 000 000 Kanten) berücksichtigt.
Weiterhin wird ein theoretisches Rahmenwerk geschaffen, das zum einen die detaillierte Quantifizierung von Graphensymmetrie erlaubt und zum anderen Stabilität von Knotenpartitionen hinsichtlich dieser Symmetrie formalisiert. Eine Partition der Knotenmenge, die durch die Aufteilung in disjunkte Teilmengen definiert ist, wird dann als stabil angesehen, wenn keine Knoten symmetriebedingt von der einen in die andere Teilmenge abgebildet werden und dadurch die Partition verändert wird. Zudem wird definiert, wie eine mögliche Zerlegbarkeit der Automorphismusgruppe in unabhängige Untergruppen als lokale Symmetrie interpretiert werden kann, die dann nur Auswirkungen auf einen bestimmten Bereich des Graphen hat. Um die Auswirkungen der Symmetrie auf den gesamten Graphen und auf Partitionen zu quantifizieren, wird außerdem eine Entropiedefinition präsentiert, die sich an der Analyse dynamischer Systeme orientiert. Alle Definitionen sind allgemein und können daher für beliebige Graphen angewandt werden. Teilweise ist sogar eine Anwendbarkeit für beliebige Clusteranalysen gegeben, solange deren Ergebnis in einer Partition resultiert und sich eine Symmetrierelation auf den Datenpunkten als Permutationsgruppe angeben lässt.
Um nun die tatsächliche Auswirkung von Symmetrie auf Graphenclustering zu untersuchen wird eine zweite Analyse durchgeführt. Diese kommt zum Ergebnis, dass von 629 untersuchten symmetrischen Graphen 72 eine instabile Partition haben. Für die Analyse werden die Definitionen des theoretischen Rahmenwerks verwendet. Es wird außerdem festgestellt, dass die Lokalität der Symmetrie eines Graphen maßgeblich beeinflusst, ob dessen Partition stabil ist oder nicht. Eine hohe Lokalität resultiert meist in einer stabilen Partition und eine stabile Partition impliziert meist eine hohe Lokalität.
Bevor die obigen Ergebnisse beschrieben und definiert werden, wird eine umfassende Einführung in die verschiedenen benötigten Grundlagen gegeben. Diese umfasst die formalen Definitionen von Graphen und statistischen Graphmodellen, Partitionen, endlichen Permutationsgruppen, Graphenclustering und Algorithmen dafür, sowie von Entropie. Ein separates Kapitel widmet sich ausführlich der Graphensymmetrie, die durch eine endliche Permutationsgruppe, der Automorphismusgruppe, beschrieben wird. Außerdem werden Algorithmen vorgestellt, die die Symmetrie von Graphen ermitteln können und, teilweise, auch das damit eng verwandte Graphisomorphie Problem lösen.
Am Beispiel von Graphenclustering gibt die Dissertation damit Einblicke in mögliche Auswirkungen von Symmetrie in der Datenanalyse, die so in der Literatur bisher wenig bis keine Beachtung fanden.
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. ... mehrWe incorporate very small graphs (< 100 nodes/edges) as well as very large graphs (> 10 000 000 nodes/> 25 000 000 edges) in the analysis.
In addition, we present a theoretical framework that, on the one hand, allows a detailed quantification of graph symmetry and, on the other hand, formalizes the stability of node partitions regarding this symmetry. A partition of nodes—which is defined by the division of the node set into disjoint subsets—is said to be stable if there is no symmetry that maps nodes from one subset to another by altering the partition at the same time. Furthermore, we define how we can interpret a possible decomposition of the automorphism group into independent subgroups as local symmetry, which then has only an impact on a restricted area of the graph. To allow a quantification of the impact of the symmetry on the whole graph and on partitions of it, we also present a special entropy definition that has its origin in the analysis of complex dynamical systems. All our definitions are generic and can thus be applied on any graphs. For some of them, even the applicability for arbitrary cluster analyses is possible, as long as they result in a partition of data points on which a symmetry relation in form of a permutation group can be defined.
A second analysis is carried out to investigate the actual impact of symmetry on graph clustering. It comes to the result that out of 629 graphs a total of 72 have an unstable partition. We employ the definitions from the theoretical framework in the analysis. Moreover, we find the local structure of the symmetry to be the most significant factor that determines if the partition is stable or not. A very local symmetry mostly results in a stable partition and, contrarily, a stable partition mostly implies a local symmetry.
However, before the above results are described and defined, we give an extensive introduction to the diverse basic knowledge upon which they build. This includes the formal definitions of graphs and statistical graph models, partitions, finite permutation groups, graph clustering and algorithms for that, as well as the entropy concept. A separate chapter is dedicated to graph symmetry, which is described by a finite permutation group—the automorphism group of the graph. Aside from that, we present algorithms that are able to identify the graph symmetry. Some of them are even capable to solve the strongly related graph isomorphism problem.
All in all, this thesis exemplarily gives insights into a possible impact of symmetry in data analysis, which was considered—if at all—only scarcely in the literature.
