A Direct Approach to Graph Clustering

A. Hlaoui and S. Wang (Canada)


Graph clustering, Median graph, Graph matching, Structural representation, Indexing.


Bridging the gap between statistical and structural pattern recognition is an issue of high importance in real applications such as web mining and content-based image retrieval. For instance, the graph is a widely used data structure in these applications, but there is a lack of efficient algorithms for comparing and grouping graphs. In this paper, we propose a direct approach to the graph clustering problem. The key elements of the new approach are an efficient graph matching algorithm for computing the similarity between two graphs and a new median graph algorithm for computing the median of a set of graphs. Clustering is performed based on the k-means algorithm. Random graphs and synthetic images are used to demonstrate the performance of the proposed algorithm.

Important Links:

Go Back