Extending the Usability of Multidimensional Scaling for Graph Drawing

Abstract

Multidimensionale Skalierung (MDS) ist eine Familie von Methoden zur Visualisierung von Ähnlichkeitsdaten als Abstände im niedrigdimensionalen Raum. Die graphische Repräsentation von Objekten ermöglicht das Verständnis der zu Grunde liegenden strukturellen Eigenschaften, sowohl lokal als auch im globalen Zusammenhang. Durch die Wiedergabe von Objektähnlichkeiten als Abstände zwischen den diese Objekte repräsentierenden Punkten in einer graphischen Darstellung werden die bestehenden Beziehungen effizient dargestellt. In Bereichen, welche auf dem Konzept der Nachbarschaftsanalyse aufbauen, wie zum Beispiel der Visualisierung von Verkehrssystemen, der Molek ulstruktur in der Chemie oder einer Teilmenge von Computerverbindungen aus dem Internet, wurde so die Visualisierung von Objekt-Beziehungen mit Hilfe von MDS-Methoden erfolgreich verwendet. Die wachsende Größe und Komplexität der zu Grunde liegenden Struktur verstärkt die Bedeutung ihrer visuellen Repräsentation. Ziel des Graphenzeichnens ist die geometrische Repräsentation einer Menge von Objekten und deren Beziehungen. Dafür sollten Objekte mit geringen graphentheoretischen Abständen in der Regel auch geometrisch nah und Objekte mit grösseren graphentheoretischen Abständen geometrisch weiter von einander entfernt gezeichnet werden. Das Ziel ist eine geometrische Repräsentation, welche zuverlässig die lokalen und die globalen Zusammenhänge von Graphobjekten widerspiegelt. Da dies auch das Ziel von MDS ist, kann das Graphenzeichnen sehr von Methoden dieser Familie profitieren. Andererseits gibt es wichtige Kriterien, welche den Nutzen von MDS im Graphenzeichnen steuern: die zu Grunde liegende Zeit- und Raumkomplexität der Methode und vom Anwendungsbereich abhängige ästhetische Kriterien. Ersteres impliziert die Notwendigkeit von effizienten und effektiven Graphenzeichenmethoden, welche auch für grösseren Datensätze geeignet sind. Letzteres dagegen ist die Anforderung, welche durch die erzeugte Repräsentation erfüllt werden soll. Ziel dieser Arbeit ist es, den Nutzen von MDS Verfahren für das Graphenzeichnen zu erweitern. Die präsentierten Erweiterungen haben zum Ziel, die Skalierbarkeit und die Flexibilität der Verwendung von MDS zu verfeinern und zu verbessern. Durch die Nutzung der der MDS zu Grunde liegenden Zielfunktionen konnten elegante und praktische Lösungen erzielt werden. Neben der Möglichkeit, grössere Datensätze zu bearbeiten, wurde auch die Flexibilität der MDS-Methoden verbessert, so dass spezifische Nebenbedingungen erfüllen werden können. Der erste Teil dieser Arbeit betrachtet ein spektrales MDS-Verfahren, die klassische Skalierung (CMDS) und deren jüngst vorgeschlagene Ann aherungen. Die pr asentierten Verbesserungen betreffen nicht nur die Qualität der Näherung, sondern auch die Effizienz des Verfahrens. Die Nutzbarkeit von CMDS für das Zeichnen von Graphen wird au erdem erweitert, indem man Modifikationen der Eingabe berücksichtigen und Freiheitsgrade des CMDS anpassen kann, sowie eine niedrigdimensionale Abbildung einer hochdimensionalen CMDS-Lösung. Ein weiterer, verbreiteter MDS-Ansatz, die Distanz Skalierung, wird im zweiten Teil der Arbeit betrachtet. Es werden Aspekte zur Minimierung der zu Grunde liegenden Zielfunktion untersucht und effiziente Verbesserungen vorgeschlagen. Die Verbesserungen betreffen sowohl die Beschleunigung der Konvergenz der genutzten iterativen Minimierung als auch die tatsächliche Komplexität der Iteration. Die vorgeschlagenen Verfahren erlauben es so, viel grössere Datensätze zu verarbeiten. Der letzte Teil der Arbeit betrachtet eine spezi sche Anpassung von MDS-Modellen. Die Anpassungen für die visuelle Betonung einer ausgew ahlten Region eines Graphen, sowohl für die Klassische Skalierung als auch für die Distanz Skalierung werden bereitgestellt. Um das visuelle Durcheinander allgemeiner Layouts zu reduzieren, wird eine Anpassung der Distanz Skalierung präsentiert.