Networks are fundamental in many areas of research as a model for studying relations between objects, such as persons and their social ties, computers in the Internet, interactions between proteins, or traffic systems. Due to the increasing importance of these studies and the steadily growing complexity of these networks, their visualization is increasingly relevant, as well.
Aside from mere presentation purposes, an appropriate visual representation is able to significantly contribute to insight into the structural properties of a network under study. This is subject to certain requirements: First, there are frequently context-specific aesthetic constraints and conventions. Second, the visualization is required to represent the network structure, i.e., the underlying graph, appropriately, and should not be misleading.
From a computer science point of view, it is the representation of the structure that is crucial for the construction of network visualizations. The field of graph drawing is concerned with methods for the automatic computation of geometric positions for objects in networks. There are countless models and algorithms, and the concrete choice is specific to the particular application.
An approach frequently used due to its simplicity, its effectivity, and its appealing results, is force- or energy-based drawing. The geometric arrangement of graph elements is determined using a quality measure, which assesses how well similarity or proximity in the graph is reflected by the visualization.
Some of the graph drawing methodologies have counterparts in other scientific disciplines, such as data analysis, psychometrics, sociology, or statistics. Many of these methods can be adapted to graphs and empirically lead to appealing and meaningful visualizations.
This thesis is concerned with the application of Multidimensional Scaling (MDS) to graph drawing. MDS is an entire family of methods for analyzing data about similarity or proximity. In the context of graphs, the principal objective is that if nodes are proximate in the graph, they should also be proximate in the visual representation.
Part I discusses the methodological foundations of MDS and the connections and differences to the traditional force- and energy-based drawing approaches.
The earliest variant of multidimensional scaling uses elementary linear algebra and Euclidean geometry and is presented in Chapter 3. It is based on spectral decompositions and produces unique optimal results. We apply classical scaling to the distance matrices of graphs and present a novel method to significantly reduce the time and space complexity. Classical scaling is thus made applicable even to very large graphs, for which the original classical scaling and almost all other graph drawing methods are prohibitive.
A very popular and widely used graph drawing approach is based on a goal function, termed energy or stress, which measures how well the current layout corresponds to the desired distances. Graph layouts are computed by iteratively minimizing this goal function. This methodology has been known long before its application to graph drawing in more general contexts. Chapter 4 discusses these connections and presents an extension in which additional constraints are integrated into the layout process.
An extensive experimental study about the quality of MDS and other graph layout methods based on graph-theoretical distances is presented in Chapter 5. The principal result is a recommendation to use a specific combination of MDS methods and algorithms to efficiently obtain the visually most pleasing results. The experimental
methodology is based on a set of hypotheses; the experiments are designed so as to support or reject these hypotheses.
Chapter 6 presents a method for drawing directed graphs which uses a decomposition of skew-symmetric matrices. Edges are to be drawn as curves winding clockwise around the origin, instead of pointing downwards.
Three applications in Part II of this thesis show how the presented methods are adapted and extended to various requirements: MDS is combined with other visualization methods for the visual analysis of dependencies between components of large software systems (Chapter 7). Particular aesthetic conventions are expressed as constraints in the radial layout of social networks (Chapter 8). Finally, a method for the visual analysis of large bibliographic networks (Chapter 9) applies a fast variant of MDS to advanced graph models.

Netzwerke sind in vielen Bereichen ein grundlegendes Modell, mit dem man Beziehungen zwischen bestimmten Objekten untersucht, etwa Personen und deren Bekanntschaften, Rechner im Internet, Interaktionen zwischen Proteinen oder Verkehrsnetze. Wegen der stets zunehmenden Bedeutung dieser Untersuchungen und der wachsenden Komplexität und Größe dieser Netzwerke wird auch die Visualisierung solcher Daten immer bedeutender.
Eine geeignete grafische Darstellung kann, neben Zwecken der Präsentation, auch zur Interpretation und einem besseren Verständnis der Eigenschaften eines betrachteten Netzwerks beitragen. Dies ist aber abhängig von bestimmten Anforderungen: Einerseits gibt es oft anwendungsspezifische ästhetische Vorgaben und Konventionen; Andererseits sollte eine Darstellung die Struktur des Netzwerks, also den darunterliegenden Graphen, getreu wiedergeben und nicht unnötig verfälschen.
Für die Erstellung von Netzwerkvisualisierungen ist aus Sicht der Informatik vor allem die Wiedergabe der Struktur bedeutend. Im Forschungsgebiet des Graphenzeichnens werden Verfahren entwickelt, um automatisch Positionen für Objekte in einem Netzwerk zu bestimmen; es gibt eine Vielzahl verschiedener Modelle und Algorithmen, deren Auswahl stark vom Einsatzgebiet abhängt.
Ein Ansatz, der wegen seiner Einfachheit und Effektivität und seiner guten Ergebnisse häufig verfolgt wird, ist das kräfte- oder energiebasierte Zeichnen. Die geometrische Anordnung der Objekte in einem Graphen wird mit einem Gütekriterium bestimmt, das bewertet, wie gut Ähnlichkeit oder Nähe im Graphen in der Visualisierung wiedergegeben werden.
Einige dieser Zeichenverfahren haben Entsprechungen in anderen Fachgebieten, etwa Datenanalyse, Psychometrie, Soziologie oder Statistik. Viele der dort verwendeten Methoden lassen sich auf Graphen übertragen und führen oft zu ansprechenden und aussagekräftigen Visualisierungen.
Diese Arbeit befasst sich mit der Anwendung der Mehrdimensionalen Skalierung (MDS) auf das Zeichnen von Graphen. MDS ist eine Familie von Methoden zur Analyse und Visualisierung von Ähnlichkeitsdaten. Das Hauptziel ist dabei, dass Knoten, die im Graphen benachbart und damit ähnlich sind, auch in der Visualisierung benachbart sein sollen.
Teil I behandelt die methodischen Grundlagen von MDS und stellt Gemeinsamkeiten und Unterschiede zu den bekannten kräfte- und energiebasierten Zeichenverfahren heraus.
Die Klassische Skalierung ist die älteste Variante von MDS und wird in Kapitel 3 auf die Abstände in Graphen angewendet. Unter der Annahme, dass diese ursprünglich von Positionen aus einem Euklidischen Raum stammen, werden Ergebnisse aus der Linearen Algebra verwendet, um diese Positionen zu rekonstruieren und eindeutige, in einem bestimmten Sinne optimale Zeichnungen zu finden. Da die verwendeten Matrixoperationen nur bis zu bestimmten Eingabegrößen skalierbar sind, wird ein Verfahren vorgestellt, mit dem die Berechnung wesentlich beschleunigt und für große Graphen überhaupt erst möglich wird.
Der meistverwendete MDS-Ansatz ist Distanz-Skalierung. Dabei wird die Anordnung mit einer Zielfunktion bewertet, in welche die Graph- und Layoutdistanzen direkt eingehen, und die iterativ optimiert wird. Kapitel 4 stellt die Beziehungen zu bekannten Zeichenalgorithmen her. Außerdem wird eine Erweiterung beschrieben, mit der
Nebenbedingungen als zusätzliche Zielfunktion definiert werden.
In einer experimentellen Studie in Kapitel 5 werden aus Erfahrungen und allgemeinen Annahmen Hypothesen über verschiedene Varianten von MDS und andere Zeichenverfahren hergeleitet, zu denen Experimente z.B. mit Initialisierungen und Beschleunigungen durchgeführt wurden. Es wird eine Kombination bestimmter Algorithmen vorgeschlagen, die, gestützt auf Ergebnisse der Experimente, die besten Lösungen verspricht.
Kapitel 6 stellt eine Methode zum Zeichnen gerichteter Graphen vor, die eine Zerlegung schiefsymmetrischer Matrizen verwendet. Dabei sollen Kanten nach Möglichkeit als Kurve im Uhrzeigersinn um den Ursprung gezeichnet werden statt von oben nach unten.
Drei Anwendungen zeigen in Teil II der Arbeit, wie die vorgestellten Methoden an verschiedene Anforderungen angepasst und erweitert werden: Bei Abhängigkeiten zwischen Komponenten großer Softwaresysteme (Kapitel 7) wird MDS mit anderen Visualisierungsmethoden kombiniert. Besondere ästhetische Vorgaben werden beim radialen Layout sozialer Netzwerke als Nebenbedingungen ausgedrückt (Kapitel 8). Eine Methode zur Darstellung und Analyse großer bibliographischer Netzwerke
(Kapitel 9) verwendet schließlich eine schnelle Variante von MDS für erweiterte Graphenmodelle.