Studien- und Diplomarbeiten im Bereich Graphenclustern

(Ansprechpartner: Andrea Schumm und Tanja Hartmann)

- Visualisierung: (Implementationsintensiv) Ziel wäre eine erste Studie, wie und ob eine 3D-Visualisierung eines sehr großen Graphen (ab 10^5 Elementen), basierend auf der sogenannten Landscape-Metaphor, für explorative Zwecke sinnvoll ist. Dabei sollten netzwerkanalytische Maßzahlen einen Teil des Layouts bestimmen, die Kantenstruktur den größten Teil (in Richtung Springembedding) und ästhetisch Aspekte den Rest. Hier gilt es kreativ zu sein und möglichst viele Informationen, die im Graphen stecken, gut lesbar an den Betrachter weiterzugeben. Wie genau das Implementiert wird ist offen, eine Möglichkeit wäre eine GUI mit Qt und OpenGL, so dass man durch den Graphen navigieren kann.

Der 5-Core eines Graphen ist der Teil der, der übrig bleibt, wenn alle Knoten mit einem Grad 4 oder weniger ausfallen - rekursiv. Es ist somit eine robuste Version des Knotengrades und bildet eine geschachtelte Hierarchie der Knotenmenge in Ebenen zunehmender Konnektivität. Die Struktur der Core-Hierarchie gilt als wichtiges Merkmal hinsichtlich z.B. der Stabilität, dem Routingverhalten und der Beherschbarkeit eines großen Netzwerks. Auf theoretischer Ebene sind Cores faszinierend. In dieser Arbeit sollen einzelne Fragen aus dem Netzwerkdesign beantwortet werden, entweder durch Algorithmen, oder durch Feststellung der Komplexität. Beispiele sind: Wieviele Kanten müssen einem Graphen mindestens hinzugefügt werden, um den Max-Core anzuheben? Wie baue ich sparsam einen k-Core der bei Ausfall von x Kanten noch immer bestehen bleibt?

Das Ziel des Graphenclustern ist es, einen gegebenen Graph G in Blöcke zu unterteilen, die in sich gut verbunden sind und untereinander schwach. Als Gütekriterium für Graphenclusterungen ist die Zielfunktion modularity sehr verbreitet, Techniken zur Maximierung gibt es viele. Jedoch ist bekannt dass es NP-schwer ist modularity zu maximieren, d.h. in der Praxis werden hauptsächlich Heuristiken zur Optimierung von Modularity eingesetzt.

In der Arbeitsgruppe von Professor Sanders existiert bereits ein Framework für die Partitionierung von Graphen. Die Anzahl Blöcke ist in dem Fall vorgegeben und die Blöcke müssen ungefähr gleich groß sein. Es handelt sich dabei um Mehrlevelalgorithmen, d.h. der Eingabegraph wird zunächst durch Kontraktionsschritte verkleinert, dann wird das Problem „gelöst“ und die Lösung wird levelweise wieder auf den Eingabegraphen projetziert. Dieses Framework enthält interessante Techniken zur Cut-Optimierung, z.B. Flow-Basiert, sehr lokale Suchen und auch globale Techniken. Ziel der Arbeit ist es zu untersuchen wie sich diese Techniken auf das Clustern von Graphen übertragen lassen und sich ggf. auch andere Zielfunktionen zu überlegen. Vorrausetzungen sind Interesse und solide Kenntnisse über Algorithmen and Datenstrukturen. Gute Programmierkenntnisse in C++ sind von Vorteil. Diese Arbeit wird von Andrea Schumm und Christian Schulz (Lehrstuhl Sanders) betreut.