Automatic abstraction of graphs based on node similarity for graph visualization

Author(s)

Huang, Xiaodi; Lai, Wei

Abstract

Graph clustering has applications in many areas such as hypermedia systems, web communities and graph visualization. This paper proposes a new approach to clustering graphs. This approach constructs the node similarity matrix of a graph based on a novel metric of node similarity, and then applies the K-means algorithm to such a matrix to obtain a hierarchical abstraction of the graph. A heuristic method is proposed to overcome the inherent drawbacks of the k-means algorithm. We also describe a multilevel multi-window approach to hierarchical layouts of clustered graphs in different abstract level views for reduction of visual complexity. The proposed approaches demonstrate good results in our experiments, and an example of visualization of part of Java 1.4 class diagrams is shown as well.

Publication year

2003

Publication type

Conference paper

Source

Proceedings of the 15th International Conference on Software Engineering and Knowledge Engineering (SEKE 2003), San Francisco, California, United States, 01-03 July 2003, pp. 111-118

Publisher

Knowledge Systems Institute

ISBN

9781891706127

Copyright

Copyright © 2003 Knowledge Systems Institute. The authors retain the right to reproduce, or have is reproduced the above paper for the author's personal use or for company use provided that (a) the source and KSI copyright are included, (b) the copies are not used in a way that implies KSI endorsement of a product or service of an employer, and (c) the copies per se are not offered for sale.

Details