基于谱聚类的社区发现算法实现研究
关键词 数据挖掘 社区发现 图的划分 谱聚类算法 K-means
毕业论文设计说明书（论文）外文摘要
Title Study on Community Discovery Algorithm based on Spectral Clustering
Abstract
Nowadays data mining is a hot topic, and spectral clustering algorithm is one of the methods of importance. Spectral clustering algorithm derived from graph partitioning problem, and is of great importance and practical value in graph theory, complex network, data mining, etc. The project applies spectral clustering algorithm to implement community detection, and employs K-means spectral clustering algorithm to realize community pision. This graduation design employs Unnormalized Laplacian algorithm and Normalized Laplacian algorithm to realize a spectral clustering algorithm for community detection, and experiments are conducted by using artificial data and network data of Zachary karate club. The results of the experiments indicate that the method is efficient in the detection of community structure.
Keywords Data Mining; Community Detection; Graph Partition; Spectral Clustering Algorithm; K-means
目录
1. 绪论 1
1.1 概述 1
1.2 国内外研究现状 1
1.3 聚类分析 2
1.3.1 聚类分析简介 2
1.3.2 研究现状 2
1.3.3 传统的聚类算法 3
1.4 论文章节安排 5
2. 论文的核心技术 6
2.1 LAPLACIAN矩阵 6
2.1.1 Unnormalize Graph Laplacian 6
2.1.2 Normalize Graph Laplacian 7
2.2 K-MEANS算法介绍 7
2.3 谱聚类算法介绍 9
2.3.1 谱聚类算法的图划分准则 10
2.3.2 相似矩阵、度矩阵 10
2.3.3 势函数，Fiedler向量及谱 10
3. 设计与实现 12
3.1 初步分析 12
3.2 实现细节及说明 13
3.2.1 主要函数介绍 13
3.2.2 实现细节和说明 16
4. 实验结果与分析 18
4.1 环境 18
4.2 实验过程 18
4.2.1 人造数据的验证 19
4.2.2 网络数据的验证 22
4.3 结果分析 23
4.3.1 不同算法的对比 23
4.3.2 K值的选取 24
4.3.3 分析误检原因 25
4.3.4 谱聚类算法与K-Means算法的比较 25
结 论 27
致 谢 28
参考文献29
1. 绪论
1.1 概述
网络在现实生活中存在于方方面面，它可以表示许多复杂的系统比如社会系统、信息交互系统、生态系统、生产过程系统等。通过先前众多学者的研究表明，我们可以将复杂网络中的节点分成不同的节点组。同一个的节点组节点之间的关联性和不是同一个节点组节点之间的关联性是不一样的，前者要更强一些。这种在复杂的网络里存在的拓扑学特性被命名为社区结构。由此可见，社区即是每个节点组。