基于谱特征和图分割的图聚类算法

摘要：

为了对图数据库中的结构化数据有效的聚类分析,首先对不同的图数据样本进行特征的深度挖掘,构造了包含节点间连接层次关系的关联度矩阵,与拉普拉斯矩阵结合共同完成谱特征分析;然后利用高斯核函数进行相似度矩阵的构建,将相似度归一化到0到1的范围内便于后期处理;最后结合图分割与k-means算法将相似度矩阵进行k分割,得到k个聚类.经过大量分析实验表明,改进的拉普拉斯矩阵对样本内部结构有更为精细的划分,提高了前期样本处理效果.最小比率割算法在保证精度的前提下,将NP难的问题转化为多项式时间内解决的问题,提高了算法的效率.

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

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金61373112;陕西省自然科学基金2016JM6078

在线出版日期：2017-08-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：222-226