Overview

In this chapter we will introduce a new method of clustering where the data to be clustered will be represented by graphs instead of vectors or other models. Specifically, we will extend the classical k-means clustering algorithm to work with graphs that represent web documents. We wish to use graphs because they can allow us to retain information which is often discarded in simpler models. For example, when representing web documents by graphs instead of vectors we can keep information such as the term appearance order or where in the document the terms appear. This in turn can possibly lead to an improvement in clustering quality, and we will investigate this experimentally.

Clustering with graphs is well established in the literature. However, the traditional paradigm in those methods has been to treat the entire clustering problem as a graph: nodes represent the items to be clustered and weights on edges connecting two nodes indicate the distance (dissimilarity) between the objects the nodes represent. The usual procedure is to create a minimum spanning tree of the graph and then remove the remaining edges with the largest weight in the minimum spanning tree until the number of desired clustered (connected components) is achieved [JMF99][TK99][Zah71]. After applying the algorithm the connected components indicate which objects belong to which clusters: objects whose nodes are connected by edges are in the same cluster. Recently there has been some progress with performing clustering directly on graph-based data. For example, an extension of self-organizing maps...