Automatic abstraction of graphs based on node similarity for graph visualization


Huang, Xiaodi; Lai, Wei


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


Publication type

Conference paper


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


Knowledge Systems Institute




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.