Visualisierung dynamischer Graphen

Die Visualisierung dynamischer Graphen, insbesondere für größere Datensätze und wenn zusätzliche Informationen verfügbar sind, wie z.B. eine hierarchische Organisation der Objekte, ist eine anspruchsvolle Aufgabe. Viele Datendimensionen müssen gleichzeitig dargestellt werden:

Graphenvertices (Objekte)
durch die Graphen induzierte Kanten (Beziehungen)
die Gewichte der Kanten
die durch die Hierarchie induzierten Einschlusskanten
die Entwicklung der Graaphen im Zeitverlauf

State-of-the-Art Bericht

Wir haben den Bereich der dynamischen Grafikvisualisierung in einem EuroVis 2014 State-of-the-Art Report (STAR) untersucht. In diesem wachsenden Forschungsgebiet wurden bereits mehr als 120 Arbeiten veröffentlicht, darunter etwa 60 einzigartige Visualisierungstechniken. Wir haben die Techniken in eine einfache hierarchische Taxonomie eingeteilt und unsere Literatursammlung auch als interaktive Datenbank zur Verfügung gestellt.

Taxonomy of dynamic graph visualization techniques.

Animierte Node-Link-Diagramme

Herkömmliche Ansätze verwenden ein Time to Time Mapping und zeigen die zeitvariablen Diagrammdaten als animierte Sequenzen von Node-Link-Diagrammen. Obwohl diese Visualisierungsstrategie sehr intuitiv ist, hat sie auch einige Nachteile:

Wenn die Diagramme sehr dicht sind, d.h. viele Kanten haben, kommt es zu visuellem Durcheinander, verursacht durch viele Kantenübergänge.
Animation führt zu kognitiven Anstrengungen für den Betrachter, seine kognitive Karte zu erhalten.
Es werden ausgefeilte Layoutalgorithmen benötigt, um die beiden zuvor genannten Probleme zu umgehen, die eine hohe Laufzeitkomplexität aufweisen.

Timeline-basierte Diagramme

In unserer Forschung vermeiden wir ein time-to-time mapping und kodieren stattdessen die Zeitdimension in den Raum. Wir verwenden gestapelte grafische farbkodierte Elemente, um gewichtete zeitvariable Beziehungen darzustellen, und wir zeigen Links nur implizit durch unterschiedliche Orientierungen anstelle von direkten expliziten Links wie in Knoten-Link-Diagrammen.

Layered TimeRadarTrees visualization showing more than 6,000,000 data points of an evolving directed and weighted graph

TimeRadarTrees visualization for soccer match results of 14 years in a part of Europe

The thumbnail view for the goalkeeper showing all weighted relations to all other players in a specific time interval

Unser Ansatz ermöglicht die einfache Untersuchung eines zeitvariablen Diagrammdatensatzes für Trends, Gegentrends und Anomalien, welcher viele Vorteile hat:

visuelle Unordnung wird reduziert, indem die Links implizit angezeigt werden.
kognitive Anstrengungen werden reduziert und die kognitive Karte wird durch die Verwendung von statischen Bildern erhalten.
interaktive Funktionen können einfach angewendet werden
Laufzeitkomplexitäten werden reduziert und Grafiken können on-the-fly hinzugefügt werden.

Dynamic graphs encode the change of relations between object over time, and as that, are a very flexible and general data encoding. Visualizing these graphs, in particular, for larger data sets and when additional information is available such as a hierarchical organization of the objects is a challenging task. Many data dimensions have to be represented at the same time:

the graph vertices (objects)
the edges induced by the graph (relations)
the weights of the edges
the inclusion edges induced by the hierarchy
the evolution of the graph over time

State-of-the-Art Report

We surveyed the field of dynamic graph visualization in a EuroVis 2014 State-of-The-Art Report (STAR). Already more than 120 papers have been published in this growing field of research, among them about 60 unique visualization techniques. We classified the techniques into a simple hierarchical taxonomy and made our literature collection also available as an interactive database.

Taxonomy of dynamic graph visualization techniques.

Animated Node-Link Diagrams

Traditional approaches use a time-to-time mapping and show the time-varying graph data as animated sequences of node-link diagrams. Though this visualization strategy is very intuitive it also has some drawbacks:

if the graphs are very dense, i.e. have many edges, visual clutter occurs caused by many edge crossings
animation leads to cognitive efforts for a viewer to preserve his mental map
sophisticated layout algorithms are needed to circumvent the two former mentioned problems that have a high run time complexity

Timeline-Based Diagrams

In our research we avoid a time-to-time mapping and encode the time dimension into space instead. We use stacked graphical color coded elements to show weighted time-varying relations and we show links only implicitly by different orientations instead of direct explicit links as in node-link diagrams.