Explorative Graph Visualization

Abstract

Network structures (graphs) have become a natural part of everyday life and their analysis helps to gain an understanding of their inherent structure and the real-world aspects thereby expressed. The exploration of graphs is largely supported and driven by visual means. The aim of this thesis is to give a comprehensive view on the problems associated with these visual means and to detail concrete solution approaches for them. This is done on all three levels involved: the data level, the representation level, and the task level.
In a first step, the intricate dependencies on the representation level alone are discussed for the case of implicit tree visualizations. With the awareness of the representation issues involved, a second step takes the characteristics on data level into account, which are most importantly graph size and graph type. Their influence on the visualization design is discussed specifically for large trees and bipartite graphs. Finally, with bringing in the task level, the entire exploration workflow from computational preprocessing to the interaction with the visualization can be captured and thus discussed in terms of its consequences for the visualization design. This includes issues of necessary confirmative elements in the exploratory analysis, as well as selecting appropriate data sets from a heterogeneous data pool for an analysis.
Concrete visualization techniques are introduced to underline the value of this comprehensive discussion for supporting explorative graph visualization.

Kurzfassung

Netzwerkstrukturen (Graphen) sind heutzutage weitverbreitet. Ihre Untersuchung dient dazu, ein besseres Verständnis ihrer Struktur und der durch sie modellierten realen Aspekte zu gewinnen. Die Exploration solcher Netzwerke wird zumeist mit Visualisierungstechniken unterstützt. Ziel dieser Arbeit ist es, einen Überblick über die Probleme dieser Visualisierungen zu geben und konkrete Lösungsansätze aufzuzeigen. Da diese Visualisierungen im Wesentlichen durch die drei Faktoren Repräsentation, Daten und Aufgaben beeinflußt werden, wird die Diskussion in drei Schritten geführt.
In einem ersten Schritt werden die miteinander verflochtenen Probleme der Repräsentationsebene am Beispiel der impliziten Baumrepräsentationen diskutiert. Zu den dabei identifizierten Herausforderungen kommen dann in einem zweiten Schritt die Eigenschaften der Daten und deren Auswirkungen auf die Repräsentation hinzu. Dies sind hauptsächlich die Größe eines Graphen und auch dessen Typ. Beispielhaft werden diese Aspekte für die Darstellung großer Bäume und bipartiter Graphen diskutiert. Im letzten Schritt werden dann die Aufgaben betrachtet und es werden die sich ergebenden Vorteile einer umfassenden Modellierung aller drei Einflußfaktoren (Repräsentation, Daten und Aufgaben) auch über den Rahmen der Exploration hinaus am Beispiel einer automatischen Auswahl von Daten für eine gegebene Aufgabe herausgestellt. Neue Visualisierungstechniken werden in jedem Schritt eingeführt, um den Nutzen der geführten Diskussion für die explorative Graphvisualisierung am konkreten Beispiel zu belegen.