This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
11th International Conference Information Visualization (IV '07)
A Fast Algorithm for Balanced Graph Clustering
Zurich, Switzerland
July 04-July 06
ISBN: 0-7695-2900-3
Mao Lin Huang, University of Technology, Sydney
Quang Vinh Nguyen, University of Technology, Sydney
Scalability problem is a long-lasting challenge for both information visualization and graph drawing communities. Available graph visualization techniques could perform well for small or medium size graphs but they are rarely able to handle very large and complex graphs. One of effective approach to solve this problem is to employ graph abstraction; that is to hierarchically partitioning the complete graph into a clustered graph. A graph visualization technique is then applied to display the abstract view of this clustered graph with partially displayed detail of one or a few sub-graphs where the user is currently focusing on. This reduces the complexity of display and makes it easier for users to interpret, perceive and navigate the large scale information. In this paper, we propose a graph clustering method which can quickly discover the community structure embedded in large graphs and partition the graph into densely connected sub-graphs. The proposed algorithm can not only run fast, but also achieve a consistent partitioning result in which a graph is divided into a set of clusters of the similar size in terms of their visual complexity and the number of nodes and edges. In addition, we also provide a mechanism to partition very dense graphs in which the number of edges is much larger than the number of nodes.
Citation:
Mao Lin Huang, Quang Vinh Nguyen, "A Fast Algorithm for Balanced Graph Clustering," iv, pp.46-52, 11th International Conference Information Visualization (IV '07), 2007
Usage of this product signifies your acceptance of the Terms of Use.