Applications of Multidimensional Scaling to Graph Drawing

Cite This

Files in this item

Checksum: MD5:3d5625ae4100e5fedfea3e816ec556eb

PICH, Christian, 2009. Applications of Multidimensional Scaling to Graph Drawing [Dissertation]. Konstanz: University of Konstanz

@phdthesis{Pich2009Appli-5726, title={Applications of Multidimensional Scaling to Graph Drawing}, year={2009}, author={Pich, Christian}, address={Konstanz}, school={Universität Konstanz} }

2011-03-24T15:59:38Z eng application/pdf Applications of Multidimensional Scaling to Graph Drawing 2011-03-24T15:59:38Z Pich, Christian Anwendungen der Multidimensionalen Skalierung auf das Zeichnen von Graphen terms-of-use 2009 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.<br />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.<br />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.<br />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.<br />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.<br />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.<br />Part I discusses the methodological foundations of MDS and the connections and differences to the traditional force- and energy-based drawing approaches.<br />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.<br />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.<br />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<br />methodology is based on a set of hypotheses; the experiments are designed so as to support or reject these hypotheses.<br />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.<br />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. Pich, Christian

Downloads since Oct 1, 2014 (Information about access statistics)

Diss_Pich.pdf 1039

This item appears in the following Collection(s)

Search KOPS


My Account