Clustering Graphs for Visualization via Node Similarities

Xiaodi Huang, Wei Lai

Research output: Contribution to journalArticlepeer-review

52 Citations (Scopus)


Graph visualization is commonly used to visually model relations in many areas. Examples include Web sites, CASE tools, and knowledge representation. When the amount of information in these graphs becomes too large, users, however, cannot perceive all elements at the same time. A clustered graph can greatly reduce visual complexity by temporarily replacing a set of nodes in clusters with abstract nodes. This paper proposes a new approach to clustering graphs. The approach constructs the node similarity matrix of a graph that is derived from a novel metric of node similarity. The linkage pattern of the graph is thus encoded into the similarity matrix, and then one obtains the hierarchical abstraction of densely linked subgraphs by applying the k-means algorithm to the matrix. A heuristic method is developed to overcome the inherent drawbacks of the k-means algorithm. For clustered graphs we present a multilevel multi-window approach to hierarchically drawing them in different abstract level views with the purpose of improving their readability. The proposed approaches demonstrate good results in our experiments. As application examples, visualization of part of Java class diagrams and Web graphs are provided. We also conducted usability experiments on our algorithm and approach. The results have shown that the hierarchically clustered graph used in our system can improve user performance for certain types of tasks
Original languageEnglish
Pages (from-to)225-253
Number of pages29
JournalJournal of Visual Languages and Computing
Issue number3
Publication statusPublished - 2006


Dive into the research topics of 'Clustering Graphs for Visualization via Node Similarities'. Together they form a unique fingerprint.

Cite this