Graph Clustering based on Structural Similarity of Fragments

Abstract. Resources available over the Web are often used in combi-nation to meet a specific need of a user. Since resource combinations can be represented as graphs in terms of the relations among the re-sources, locating desirable resource combinations can be formulated as locating the corresponding graph. This paper describes a graph clustering method based on structural similarity of fragments (currently connected subgraphs are considered) in graph structured data. A fragment is char-acterized based on the connectivity (degree) of a node in the fragment. A fragment spectrum of a graph is created based on the frequency distri-bution of fragments. Thus, the representation of a graph is transformed into a fragment spectrum in terms of the properties of fragments in the graph. Graphs are then clustered with respect to the transformed spectra by applying a standard clustering method. We also devise a criterion to determine the number of clusters by defining a pseudo-entropy of cluster. Preliminary experiments with synthesized data were conducted and the results are reported