Automatic Graph Clustering

Abstract

We present a technique and a program for the automatic clustering of graphs. The technique is based on several heuristics, which allows for an efficient implementation on a personal computer. Our approach is capable of clustering graphs with ? 3000 vertices efficiently. The demonstration shows an interactive user environment that supports both automatic and user-controlled clustering. As an application, we consider the clustering of large WWW connectivity graphs. 1 Introduction Clustering is the process of grouping information to achieve a more recognizable presentation of source data. The computation of a clustering generally requires a metric on the data to determine the closeness of data points. The clustering of graphs can be based on either graph structure, or on some semantic properties of the application domain. In this paper, we do not make any assumptions about the "meaning" of vertices and edges, but focus solely on the structure. In this context, the only available metric ...