Interactive web-based visualization of large dynamic graphs

Abstract

The visualization and analysis of large graphs plays an essential role in various application fields. Since the size of graphs grew exponentially in the past few years, it became a challenge to reduce the visual clutter of dense and occluded graphs. By abstracting the structure of a node-link diagram, containing thousands of nodes and edges, visual clutter is reduced drastically, supporting the analysis of underlying patterns in an interactive approach. Additional visual techniques are used to overcome the challenge of representing the evolution of structural diagram changes and relationships between entities in dynamic graph visualization. The recent publications of large static and dynamic graph visualization techniques are using rich clients based on fast processing GPU algorithms, as well as distributed approaches for cluster-computing frameworks. Even though these techniques are capable of processing large-scale graphs interactively, they are also restricted by the user’s hardware or are more complex and expensive than simple client-server solutions. This thesis aims to provide an alternative approach, at providing a distributed, cross-platform, server-client application, able to visualize large node-link graphs, consisting of thousands of elements, interactively in a standard web-browser. We describe an aggregation strategy based on meta-elements, that provides an adjustable level of detail interface and visualizes the hierarchy of cumulative elements throughout multiple abstraction layers. By highlighting structural changes over time in dynamic graphs in combination with tools, such as panning and zooming and overview and detail, our system allows for dynamic graph exploration. We will demonstrate the usability of our technique by providing a complete prototype and present benchmarks on different graphs. Furthermore, we evaluate technical aspects of our approach as well as its applicability to large real-world graphs.

Die Visualisierung und Analyse großer Graphen spielt in verschiedenen Anwendungsbereichen eine wesentliche Rolle. Da die Größe von Diagrammen in den letzten Jahren exponentiell zugenommen hat, wurde es zu einer Herausforderung, das visuelle Durcheinander von dichten Graphen zu verringern. Durch die Abstraktion der Struktur eines ungerichteten Graphs, welcher Tausende von Knoten und Kanten beinhalten kann, wird das visuelle Durcheinander drastisch reduziert und die Analyse der zugrunde liegenden Muster in einem interaktiven Ansatz unterstützt. Zusätzliche visuelle Techniken werden verwendet um die Darstellung der strukturellen Entwicklung des Graphen und Beziehungen zwischen Entitäten in der Visualisierung zu überwinden. Die jüngsten Veröffentlichungen verwenden entweder "Rich Clients", die auf speziellen GPU-Algorithmen basieren, oder Cluster-Computing. Obwohl diese Techniken in der Lage sind, große Diagramme interaktiv zu verarbeiten, sind sie entweder durch die Hardware des Benutzers eingeschränkt, oder komplex und teurer als einfache Client-Server-Lösungen. Diese Arbeit zielt darauf ab, einen alternativen Ansatz zur Bereitstellung einer verteilten, plattform übergreifenden Server-Client-Anwendung bereitzustellen, mit der große Diagramme, die aus Tausenden von Elementen bestehen, interaktiv in einem modernen Webbrowser dargestellt werden können. Wir beschreiben eine auf Metaelementen basierende Aggregationsstrategie, die einen anpassbaren Detailgrad bietet und die Hierarchie kumulativer Elemente über mehrere Abstraktionsebenen hinweg visualisiert. Durch Hervorheben von strukturellen Änderungen in dynamischen Graphen über den Lauf der Zeit, in Kombination mit Techniken wie "Panning and Zooming und Overview and Detail", ermöglicht unser System die interaktive Analyse von Diagrammen. Wir werden die Verwendbarkeit unserer Technik anhand eines vollständigen Prototyps demonstrieren und die Geschwindigkeit anhand unterschiedlicher Testdaten messen. Darüber hinaus bewerten wir auch technische Aspekte unseres Ansatzes, sowie seine Anwendbarkeit auf große reale Diagramme.