Visualization techniques for group structures in graphs

Abstract

Graph visualization plays a key role analyzing relations between objects. With increasing size of the graph, it becomes difficult to understand global and local structures of the graph. Grouping objects of the graph based on their attributes or relations helps reveal global structures. Visualizing these group structures together with the graph topology can highlight central objects and reveal outliers. The ability of a visualization to help detecting these features becomes more difficult for groups that overlap or change over time. In many applications, groups cannot be interpreted as disjoint sets of objects. In fact, objects are often involved in several groups, sometimes even to different extent. With the existing types of overlapping groups, further analysis tasks arise that need to be considered for the visualization. In addition, real-world scenarios are not static but change over time and so do relations among objects. With the graph topology changing over time, the group structure changes as well. The challenge for visualizations of dynamic groups in dynamic graphs is to facilitate the analysis of group-related features not only for individual points in time but over time, showing group evolution events. This thesis presents visualization techniques for group structures in graphs that address these challenges: overlap and time dependency. As a basis, a survey of the state of the art in visualizing group structures in graphs is presented. The first part of this thesis is dedicated to the visualization of overlapping groups in static graphs, where different types of overlaps are considered. With each technique, the complexity of the groups increases. First, a visual analytics system for crisp overlapping groups in multivariate graphs is presented. This system integrates interactive filtering of large and dense networks with groupbased layouts of the resulting subnetworks and a technique to compare those subnetworks. Second, a technique that visualizes fuzzy overlapping groups in a graph based on layout strategies and further visual mappings is presented. This technique facilitates the investigation of fuzzy group memberships at different levels of detail based on a hierarchical aggregation model. In contrast to these techniques, the third visualization technique shows groups based on multivariate edge attributes rather than vertex attributes or the topology of the graph. In particular, edge-edge relations are visualized as curves that are directly integrated into the node-link diagram representing the object-relation structure. The second part is dedicated to visualization techniques for dynamic groups in dynamic graphs. Again, the complexity of the group structure rises from the first technique addressing flat groups to the second technique addressing more complex hierarchical groups. Within both techniques, the evolution of groups is encoded using a flow metaphor. The first technique visualizes the partially aggregated graphs by node-link diagrams, whereas the second technique is based on an extended adjacency matrix representation that encodes the hierarchical structure of vertices as well as changes in the graph topology. All presented techniques visualize the group structure integrated with the graph topology in a single image. Finally, the use of all techniques is demonstrated for real data sets from biology, one of the main application domains of group structures in graphs.

Netzwerkvisualisierung spielt eine wichtige Rolle bei der Analyse von Relationen zwischen Objekten. Mit zunehmender Größe des Graphen wird es schwierig globale sowie lokale Strukturen des Graphen zu verstehen. Die Gruppierung von Objekten des Graphen basierend auf ihren Attributen oder Relationen hilft dabei, globale Strukturen aufzuzeigen. Durch die Visualisierung der Gruppenstruktur zusammen mit der Graphtopologie können zentrale Objekte und Ausreißer hervorgehoben werden. Die Fähigkeit einer Visualisierung, die Erkennung solcher Merkmale zu unterstützen, wird für überlappende oder sich zeitlich verändernde Gruppen noch schwieriger. In vielen Anwendungsbereichen können Gruppen nicht als disjunkte Mengen von Objekten verstanden werden. Vielmehr sind Objekte oftmals in mehrere Gruppen involviert, teilweise sogar in unterschiedlichem Umfang. Für die verschiedenen Arten überlappender Gruppen müssen weitere Analyseaufgaben für die Visualisierung in Betracht gezogen werden. Darüber hinaus sind Szenarien in der echten Welt nicht statisch, sondern ändern sich über die Zeit, weshalb auch die Relationen zwischen den Objekten dynamisch sind. Verändert sich die Graphtopologie über die Zeit, so ändert sich auch die Gruppenstruktur des Graphen. Die Herausforderung für die Visualisierung von dynamischen Gruppen in dynamischen Graphen ist es, die Analyse von gruppenbezogenen Eigenschaften nicht nur für individuelle Zeitpunkte, sondern auch über die Zeit hinweg zu ermöglichen, um Ereignisse in der Gruppenentwicklung aufzuzeigen. Diese Doktorarbeit präsentiert Visualisierungstechniken für Gruppenstrukturen in Graphen, welche folgende Herausforderungen angehen: Überlappung und Zeitabhängigkeit. Als Grundlage wird ein Überblick über den Stand existierender Techniken zur Visualisierung von Gruppenstrukturen in Graphen präsentiert. Der darauffolgende erste Teil der Doktorarbeit widmet sich der Visualisierung von überlappenden Gruppen in statischen Graphen, wobei verschiedene Arten von Überlappung betrachtet werden. Mit jeder dieser Techniken erhöht sich die Komplexität der Überlappung. Zuerst wird ein System zur visuellen Analyse von scharf überlappenden Gruppen in multivariaten Graphen präsentiert. Dieses System integriert interaktive Methoden zum Filtern großer dichter Netzwerke mit einem gruppenbasierten Layout der resultierenden Teilnetzwerke und einer Technik zum Vergleich solcher Teilnetzwerke. Darauf folgend wird eine Technik zur Visualisierung von unscharf überlappenden Gruppen in Graphen präsentiert. Diese Technik basiert auf Layout-Strategien und weiteren visuellen Abbildungen. Sie ermöglicht es, die unscharfen Gruppenzugehörigkeiten basierend auf einem hierarchischen Aggregationsmodell auf verschiedenen Detailstufen zu untersuchen. Diese ersten Techniken zeigen beide Gruppen von Objekten des Graphen. Im Gegensatz dazu widmet sich die dritte Visualisierungstechnik Gruppen von Relationen, welche von multivariaten Attributen dieser Relationen abgeleitet werden. Im Speziellen werden Relationen zwischen Kanten als Kurven visualisiert, welche direkt in das Knoten-Kanten-Diagramm des Graphen integriert werden. Der zweite Teil dieser Doktorarbeit widmet sich Visualisierungstechniken für dynamische Gruppen in dynamischen Graphen. Auch hier steigt die Komplexität der Gruppenstruktur: Die erste Technik dient der Visualisierung von flachen Gruppen, während die zweite Visualisierungstechnik für komplexere, hierarchische Gruppen entwickelt wurde. In beiden Techniken wird die Entwicklung der Gruppen mit Hilfe einer Fluss Metapher dargestellt. Während die erste Technik teilweise aggregierte Graphen als Knoten-Kanten-Diagramme darstellt, basiert die zweite Technik auf einer erweiterten Adjazenzmatrix-Darstellung, welche die hierarchische Struktur der Objekte sowie die Änderungen in der Graphtopologie kodiert. Alle Techniken, welche in dieser Doktorarbeit vorgestellt werden, visualisieren die Gruppenstruktur gemeinsam mit der Graphtopologie in einem Bild. Zuletzt wird der Nutzen aller Techniken am Beispiel von realen Datensätzen aus der Biologie, einem der Hauptanwendungsgebiete von Gruppenstrukturen in Graphen, gezeigt.