关键词: 谱特征分解, 图分割, 相似度矩阵, 图聚类

Abstract:

In order to analyze the structured data in database with valid clustering, the algorithm firstly mines the depth data characteristics of different graph sample, and constructs the association matrix including connection relations and nodes with hierarchy, completes the analysis of spectral characteristics combined with the Laplace matrix. Secondly, it uses the Gaussian kernel to build the similarity matrix, to facilitate post-processing the value of similarity matrix normalized in the range of 0-1. Finally, it combines k-means with graph partitioning algorithm to make the data k-partition, then gets k cluster of the database. The experimental results demonstrate that the improved Laplace has finer division of the internal structure in matrix, and improves the pre-process results of the sample. The minimum rate cut algorithm ensures the accuracy of the premise, and turns the NP-hard problem into a polynomial time to solve the problems and improve algorithm efficiency.

Key words: spectral decomposition, graph segmentation, similarity matrix, graph clustering