Graph visualization plays an increasingly important role in software engineering and
information systems. Examples include UML, E-R diagrams, database structures,
visual programming, web visualization, network protocols, molecular structures,
genome diagrams, and social structures.
Many classical algorithms for graph visualization have already been developed
over the past decades. However, these algorithms face difficulties in practice, such as
the overlapping nodes, large graph layout, and dynamic graph layout. In order to solve
these problems, this research aims to systematically address both algorithmic and
approach issues related to a novel framework that describes the process of graph
visualization applications. At the same time, all the proposed algorithms and
approaches can be applied to other situations as well.
First of all, a framework for graph visualization is described, along with a generic
approach to the graphical representation of a relational information source. As the
important parts of this framework, two main approaches, Filtering and Clustering, are
then particularly investigated to deal with large graph layouts effectively.
In order to filter 'noise' or less important nodes in a given graph, two new
methods are proposed to compute importance scores of nodes called NodeRank, and
then to control the appearances of nodes in a layout by ranking them.
Two novel algorithms for clustering graphs, KNN and SKM, are developed to
reduce visual complexity. Identifying seed nodes as initial members of clusters, both
algorithms make use of either the k-nearest neighbour search or a novel node
similarity matrix to seek groups of nodes with most affinities or similarities among
them. Such groups of relatively highly connected nodes are then replaced with
abstract nodes to form a coarse graph with reduced dimensions.
An approach called MMD to the layout of clustered graphs is provided using a
multiple-window�multiple-level display.
As for the dynamic graph layout, a new approach to removing overlapping nodes
called Force-Transfer algorithm is developed to greatly improve the classical Force-
Scan algorithm.
Demonstrating the performance of the proposed algorithms and approaches, the
framework has been implemented in a prototype called PGD. A number of
experiments as well as a case study have been carried out.
| Identifer | oai:union.ndltd.org:ADTP/216485 |
| Date | January 2004 |
| Creators | Huang, Xiaodi, xhuang@turing.une.edu.au |
| Publisher | Swinburne University of Technology. |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | http://www.swin.edu.au/), Copyright Xiaodi Huang |
Page generated in 0.0047 seconds