Automatic Graph Clustering (System Demonstration)

Sablowski, Reinhard and Frick, Arne (1997) Automatic Graph Clustering (System Demonstration). In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 395-400 (Official URL:

Full text not available from this repository.


We present a new, easy to understand algorithm and programming environment allowing for the interactive or automatic clustering of graphs according to several heuristics. Our approach is based on graph structure only and can be implemented to run efficiently with a personal computer. It is capable of efficiently clustering graphs with >3000 vertices. We shall demonstrate the interactive user environmentfor automatic clustering. As an application, we consider the clustering of large WWW connectivity graphs.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_63
Classifications:M Methods > M.300 Dynamic / Incremental / Online
G Algorithms and Complexity > G.350 Clusters
ID Code:111

Repository Staff Only: item control page


M.R. Anderberg. Cluster analysis for applications. Academic Press, 1973.

Bosak. Graph partitioning. Kluwer, 1990.

F.J. Brandenburg. Designing graph drawings by layout graph grammars. In Roberto Tamassia and Ioannis Tollis, editors, Proceedings of Graph Drawing '94, volume 894 of LNCS, pages 416-427. DIMACS Workshop on GD, Springer-Verlag, 1995.

P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149-160, 1984.

J. Hartigan. Clustering Algorithms. J. Wiley and Sons, 1975.

S. Mukherjea, J.D. Foley, and S. Hudson. Visualizing complex hypermedia networks through multiple hierarchical views. Technical Report 95-08, Georgia Institute of Technology, Graphics, Visualization and Usability Center, College of Computing, Atlanta, CA 30332-0280, 1995. also appeared in the Proceedings of the ACM SIGCHI CHI '95, May 1995, denver, Colorado.

G. Zinssmeister and C. McCreary. Drawing graphs with attribute graph grammars. In Graph Grammar Workshop, pages 355-360, Williamsburg, 1994.