Spectral Analysis And Clustering Of Relational Graphs

As the application of clustering is extended and further investigated, the problems of clustering in high dimensions become the hot topic of clustering research. In the last few years, clustering of graphs in huge database is also an active research problem. In clustering, metric features which measure the friendliness relationships are often classified into similarity coefficients and distances. The difficulty of clustering of graphs, especially the clustering of large amount of relational graphs, lies on the representation of graphs and the definition of distance function. This dissertation is based on spectra theory of graphs and statistical theories. In this dissertation, we investigate graph spectra and spectral features, relational graph representation and clustering in low dimensional spaces. There are four research aspects: 1) Graph spectra and spectral decomposition; 2) Dimensionality reduction of spectra features and the visualization of graph sets in low dimensional spaces; 3) Spectral clustering of graphs; 4) Graph clustering analysis based on spectral edit distance. The contributions of this dissertation are as follows:Relational graph description of images. The relational graph representation of images can be constructed by geometrical features in images, such as corner points, vertex points, inflection points, boundaries and textures. Using these features, we can construct relational graphs, such as regional adjacent graphs, graphs built by line segments, feature points and corner points. Because of the superiority in anti-noising of geometrical features, and the great development of segmentation of geometrical features in images, the research on relational graphs becomes more and more active. We extract features of corner points in images, and construct different types of relational graphs. Delaunay graphs are used to construct the corresponding matrices in experiments, Matrices in research mainly include binary adjacent matrix, weighted adjacent matrix and Laplacian matrix.Graph spectra and spectral decomposition. The eigenvalues of the adjacency matrix of a relational graph is its spectra. Each eigenvalue has its corresponding eigenvector. These eigenvalues are arranged in descending order. Using the ordered...