Eine Vielzahl der gegenwärtig gesammelten Daten kann durch Graphen modelliert werden. Ein Graph in seiner einfachsten Form besteht aus einer Menge von Entitäten, auch Knoten genannt, und einer Menge von ungerichteten Beziehungen zwischen diesen, Kanten genannt. Prominente Beispiele für Daten, die mit Graphen modelliert werden können, sind soziale Netzwerke und andere soziale Medien, wie beispielsweise Facebook, Google+, Twitter oder ResearchGate. Das Anwendungsgebiet von Graphen ist jedoch nicht auf die Modellierung von sozialen Netzwerken begrenzt; sie können überall da eingesetzt werden, wo Beziehungen zwischen Objekten untersucht werden. Ebenso vielfältig wie das Anwendungsgebiet von Graphen ist auch die Menge an Werkzeuge für deren Analyse. Da das Sammeln von massiven Datensätzen in Zeiten des Internets vergleichbar einfach geworden ist, stößt eine Vielzahl dieser Analysetechniken an die Grenzen ihrer Anwendbarkeit. Gleichzeitig ist die Analyse eben jener massiven Datensätze von unschätzbarem Wert für Wirtschaft, Politik, Gesundheitswesen, Sicherheit, Sport, und Wissenschaft, um nur einige Beispiele zu nennen. Eine Lösung, um die Analyse dieser Daten zu ermöglichen, besteht darin, die Komplexität des Graphens zu reduzieren, indem man diesen ausdünnt.

Das Ziel der Ausdünnung von Graphen ist eine schlankere Darstellung des Originals, indem man die Anzahl von Knoten bzw. Kanten vermindert, wobei man gleichzeitig einige seiner Eigenschaften aufrecht erhält oder zumindest approximiert. Zwar führt die Ausdünnung zu einem Informationsverlust, jedoch sind nicht alle Knoten bzw. Kanten gleichermaßen wichtig für die durchzuführende Analyse. Insofern der Ausdünnungsprozess jene Knoten und Kanten verschont, welche unentbehrlich für die anschließende Analyse sind, kann diese für große Graphen durchgeführt werden und potentiell zu den gleichen Ergebnissen, oder zumindest einer Approximation dieser, führen.

Die vorliegende Arbeit beschäftigt sich mit drei unterschiedlichen Ausdünnungsverfahren und deren effizienten Berechnung, das Hauptaugenmerk liegt dabei auf dem “Quadrilateral Simmelian Backbone”.

Die Berechnung des Quadrilateral Simmelian Backbone besteht aus zwei Teilproblemen, nämlich der Aufzählung aller vollständigen Teilgraphen mit drei Knoten, sogenannten Dreiecken, und dem Zählen, wie oft eine Kante in einem speziellen nicht induzierten Viereck, das heißt einem Teilgraphen mit vier Knoten, vorkommt.

In Kapitel 3 beschäftigen wir uns mit effzienten kombinatorischen Algorithmen zum Aufzählen von Dreiecken und zeigen, dass die meisten Dreiecksaufzählungsverfahren aus der Literatur Instanziierungen eines einzigen generischen Verfahren sind. Basierend auf dieser Abstraktion zeigen wir, dass nahezu alle dieser Algorithmen eine Laufzeit von O(a(G)m) haben, wobei a(G) die Arborizität des Graphen bezeichnet und m die Anzahl seiner Kanten ist. Diese Laufzeit wurde bisher nur für den Algorithmus von Chiba and Nishizeki (1985) bewiesen. Weiterhin zeigen wir hier, dass unsere verbesserte Implementation dieses Algorithmus in der Praxis der schnellste ist.

Das effiziente Aufzählen von Dreiecken ist nicht nur relevant für den Quadrilateral Simmelian Backbone, sondern auch für die Berechnung eines anderen Ausdünnungsverfahren, dem “Irreducible Spine” (Pfaltz, 2013). In Kapitel 4 präsentieren wir einen dynamische Algorithmus zur Bestimmung des Irreducible Spine in O(a(G)m) Zeit und beweisen seine Eindeutigkeit bis auf Isomorphie. Die Konstruktion des Irreducible Spines basiert darauf, dominierte Knoten aus dem Graphen sukzessive zu entfernen. Da die verwendete Definition von Dominanz nur eine von vielen möglichen Instanziierungen des Dominanzkonzepts von Brandes (2016) und daher austauschbar ist, präsentieren wir zusätzlich weitere Algorithmen zur Berechnung anderer Arten von Dominanz.

In Kapitel 5 widmen wir uns wieder der effizienten Berechnung des Quadrilateral Simmelian Backbone. Obgleich für dessen Berechnung nur die Anzahl eines bestimmten Subgraphs mit vier Knoten wichtig ist, führen wir hier einen ganzheitlichen Ansatz zur Berechnung der Häufigkeiten aller induzierten und nicht-induzierten Subgraphen mit vier Knoten ein. Genauer gesagt präsentieren wir einen Algorithmus mit Komplexität in O(a(G)²m), der diese Häufigkeiten für jeden Knoten und jede Kante berechnet mitsamt einer Unterscheidung der Automorphismusklassen in diesen Teilgraphen. Weitherhin zeigen wir in diesem Kapitel am Beispiel des “Triaden Zensus”, wie man unserer Ansatz auf gerichtete Graphen erweitern kann.

Ausgehend von den Ergebnissen von Kapitel 3 und 5, führen wir in Kapitel 6 den Algorithmus zur effizienten Berechnung des Quadrilateral Simmelian Backbone mit einer Laufzeit in O(m(a(G) + log m)) ein. In einer umfangreichen experimentellen Studie zeigen wir, dass der Quadrilateral Simmelian Backbone besonders gut geeignet ist, um die Gruppenstruktur eines Graphens herauszuarbeiten und bessere Ergebnisse liefert als verwandte Ansätze.

Die Ergebnisse der Evaluation in Kapitel 6 zeigen, dass die Qualität des Quadrilateral Simmelian Backbone stark von der Anzahl der ausgedünnten Kanten abhängt. Daher zeigen wir in Kapitel 7, wie man diese Anzahl automatisch in O(m(a(G) + log m)) Zeit bestimmen kann und veranschaulichen die Effektivität unseres Verfahrens anhand von Experimenten.

Abschließend präsentieren in Kapitel 8 ein weiteres Ausdünnungsverfahren. Wie wir durch Experimente zeigen, ermöglicht diese Methode der “Stressminimierung”, ein energiebasiertes Graphenzeichenverfahren, in einem Bruchteil der Zeit annähernd die selben Zeichnungen zu erzeugen wie wenn es den Originalgraphen als Eingabe erhalten hätte. Weiterhin zeigt unsere Evaluation, dass dieses Ausdünnungsverfahren bessere Ergebnisse bei vergleichbarer Laufzeit liefert als alternative Herangehensweisen, um Zeichnungen mit geringem Stress zu erzeugen.