Graph- und Netzwerkvisualisierung

Die Graph- und Netzwerkvisualisierung stellt Entitäten und ihre Beziehungen dar, meist als Knoten-Kanten-Diagramme, und hilft dabei, Strukturen wie Cluster, Pfade und zentrale Knoten zu erkennen.

Definition

Graph- und Netzwerkvisualisierung ist die visuelle Darstellung von Daten, die aus Entitäten und den Beziehungen zwischen ihnen bestehen, unter Verwendung von Layouts, die Knoten positionieren und Kanten routen, oder von Matrixdarstellungen, sodass strukturelle Eigenschaften des Netzwerks wahrnehmbar werden.

Scope

Dieses Thema behandelt die visuelle Darstellung relationaler Daten: Knoten-Kanten-Diagramme und Graph-Layout-Algorithmen wie kraftbasierte und hierarchische Layouts, Matrixdarstellungen von Graphen sowie Techniken für große und dichte Netzwerke und Navigations- und Ästhetikkriterien für lesbare Graphen. Es behandelt nicht die algorithmische Theorie von Graphen als Datenstrukturen, die zu Algorithmen gehört, noch die perzeptive Grundlage der Kodierung im Allgemeinen, die unter visueller Kodierung und Wahrnehmung behandelt wird.

Core questions

• Wie positionieren Layout-Algorithmen Knoten, um Strukturen sichtbar zu machen?
• Wann sind Knoten-Kanten-Diagramme besser als Matrixdarstellungen?
• Wie können sehr große oder dichte Netzwerke lesbar gemacht werden?
• Welche ästhetischen Kriterien erleichtern die Interpretation einer Graphenzeichnung?

Key concepts

• Knoten-Kanten-Diagramm
• kraftbasiertes Layout
• hierarchisches (geschichtetes) Layout
• Adjazenzmatrix-Darstellung
• Minimierung von Kantenkreuzungen
• Graphenästhetik
• Clustering und Aggregation
• Skalierbarkeit großer Netzwerke

Key theories

Graphenlayout und Ästhetik

Die Graphenzeichnung strebt Layouts an, die ästhetische Kriterien wie wenige Kantenkreuzungen, kurze, gleichmäßige Kanten und sichtbare Symmetrie erfüllen; kraftbasierte und hierarchische Algorithmen erzeugen Layouts, die Strukturen sichtbar machen.

Knoten-Kanten- versus Matrixdarstellungen

Kontrollierte Experimente zeigen, dass Knoten-Kanten-Diagramme gut für kleine, dünn besetzte Graphen und Pfadverfolgungsaufgaben geeignet sind, während Matrixdarstellungen besser für große, dichte Graphen und Aufgaben wie das Finden des am stärksten verbundenen Knotens skalieren.

Navigation und Skalierbarkeit

Übersichten zur Graphenvisualisierung katalogisieren Methoden zur Navigation und Vereinfachung großer Netzwerke, einschließlich Clustering, Filterung und Fokus-Plus-Kontext-Navigation, um große Graphen interpretierbar zu halten.

Clinical relevance

Netzwerkvisualisierung wird verwendet, um Beziehungen in sozialen Netzwerken, biologischen Pfaden, Infrastrukturen und Wissensgraphen zu verstehen; die Wahl der richtigen Darstellung und des richtigen Layouts hilft Analysten, Gemeinschaften, Hubs und Pfade zu erkennen, die in rohen relationalen Daten unsichtbar wären.

History

Die Graphenzeichnung entwickelte in den 1980er und 1990er Jahren starke algorithmische Grundlagen, die in Di Battista und Kollegen' Text von 1999 zusammengefasst wurden. Herman, Melancon und Marshall untersuchten die Graphenvisualisierung für die Informationsvisualisierung im Jahr 2000, und spätere kontrollierte Studien, wie der Vergleich von Knoten-Kanten-Diagrammen mit Matrixdarstellungen, verfeinerten die Richtlinien für die Wahl der Darstellung für Netzwerke unterschiedlicher Größe.

Debates

Knoten-Kanten-Diagramme versus Matrixdarstellungen für große Graphen

Knoten-Kanten-Diagramme sind intuitiv und weit verbreitet, werden aber unübersichtlich, wenn Graphen dichter werden, während Matrixdarstellungen in großem Maßstab lesbar bleiben, aber für die Pfadverfolgung weniger natürlich sind; die bessere Wahl hängt von der Größe, Dichte und Aufgabe des Graphen ab.

Key figures

• Ivan Herman
• Giuseppe Di Battista
• Peter Eades
• Roberto Tamassia
• Jean-Daniel Fekete

Seminal works

• dibattista1999
• herman2000
• ghoniem2005

Frequently asked questions

Was ist ein kraftbasiertes Layout?

Ein kraftbasiertes Layout behandelt einen Graphen wie ein physikalisches System, wobei Kanten wie Federn wirken, die verbundene Knoten zusammenziehen, und Knoten sich gegenseitig abstoßen. Wenn sich die Simulation einpendelt, entsteht ein Layout, bei dem eng verbundene Gruppen clustern und die Gesamtstruktur sichtbar wird, ohne manuelle Platzierung.

Warum eine Matrix anstelle eines Knoten-Kanten-Diagramms verwenden?

Bei großen, dichten Netzwerken werden Knoten-Kanten-Diagramme zu einem Gewirr sich kreuzender Kanten. Eine Matrixdarstellung platziert Knoten entlang von Zeilen und Spalten und markiert jede Verbindung in einer Zelle, wodurch Kantenüberlagerungen vermieden werden und Aufgaben wie das Erkennen stark verbundener Knoten oder dichter Untergruppen in großem Maßstab einfacher werden.