Info
Bei "Hierarchical Edge Bundles" geht es um die Visualisierung von Compound Graphen. In einem Compound Graphen gibt es sowohl hierarchische - also Eltern-Kind-Beziehung - als auch nichthierarchische (adjazente) Strukturen. Letztere beschreiben die Beziehungen zwischen den Knoten (Daten). Beispiele hierfür sind z.B. die Organisation von Softwaresystemen, soziale Netzwerke oder hierarchisch organisierte Literaturzitiernetzwerke.
Während hierarchische Strukturen mittels klassischer Baumstrukturen wie dem Rooted Tree, Radial Tree, Balloon Tree oder dem Treemap Layout dargestellt werden (in unserer Applikation haben wir uns auf die ersten drei Baumstrukturen beschränkt), werden adjazente Kanten visuell gebündelt dargestellt. Als Analogie kann man hier elektrische Kabel oder Netzwerkkabel sehen, die üblicherweise in Kabelkanälen verlegt werden und erst am Ende einzeln zum jeweiligen Bestimmungsort verlaufen.
Die Realisierung des Ansatzes erfolgt mittels stückweise kubischer B-Splines, da hier ausreichende lokale Kontrolle und geringe Komplexität (Grad) vorhanden sind. Der Pfad entlang der Kanten der Hierarchie zwischen zwei Knoten einer Adjazenzrelation wird dabei als Kontrollpolygon für die B-Spline benutzt. Um Mehrdeutigkeiten aufzulösen, wird die Bündelstärke mittels des Parameters β, der die B-Spline Ebenheit steuert, verringert. Die Begradigung der B-Spline kann entweder mittels Begradigung von jedem Kontrollpunkt oder Begradigung von jedem Spline-Punkt durchgeführt werden. Bei Adjazenzrelationen zwischen zwei Geschwistern kommt es zu Überschneidungen im Bereich des gemeinsamen Elternknotens (Vorfahrens). Abhilfe schafft hier die Entfernung des kleinsten (letzten) gemeinsamen Vorfahrens (LCA - least common ancestor) aus dem Kontrollpolygon. Das kann allerdings wieder zu Mehrdeutigkeiten führen. Deshalb wird der LCA nur dann entfernt, wenn im Ausgangskontrollpolygon mehr als 3 Kontrollpunkte vorhanden sind.
Um kurze Kanten hervorzuheben werden sie beim Rendering über die langen Kanten gezeichnet und es wird Alpha Blending, bei dem lange Kanten mit einer höheren Transparenz als kurze Kanten gezeichnet werden, verwendet. Die Richtung einer Kante wird mittels Farbkodierung visualisiert, indem der Anfang der Kante (Quelle) grün und das Ende einer Kante (Ziel) rot gezeichnet wird. Dazwischen wird interpoliert.
In einer Benutzerstudie wurde festgestellt, dass die meisten Probanden für die Visualisierung der Hierarchien Radial Trees über Balloon Trees und über das Treemap Layout bevorzugten. "Hierarchical Edge Bundles" wurde als nützlich empfunden, um einen schnellen Überblick über die Adjazenzrelationen zu bekommen. Außerdem wurde das Ergebnis von den Probanden als ästhetisch empfunden.
Zusammenfassend ist zu sagen, dass bei einer nichtgebündelten Darstellung die "Hot Spots" zu sehen sind. Man kann aber i.A. nur sehr schwer erkennen welcher Knoten mit welchem Knoten verbunden ist. Die Lösung für dieses Problem ist die gebündelte Darstellung, die zusätzlich noch die Relationen zwischen Systemen mit wenigen Verbindungen deutlicher visualisiert. Probleme bei diesem Ansatz gibt es noch in Form von Überlappungen von den gebündelten Kanten bei Datensätzen bzw. Baumstrukturen mit sehr vielen kollinearen Knoten.
Referenzen der Abbildungen dieser Seite und des Algorithmuses
- Danny Holten: Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data, IEEE Transactions on Visualization and Computer graphics, vol. 12, no. 5, September / October 2006
