基于谱聚类的社区发现算法实现研究
时间:2018-05-06 19:54 来源:毕业论文 作者:毕业论文 点击:次
| 摘要社交网络的挖掘是目前的研究热点，谱聚类是其中的一个重要算法。谱聚类算法源于图的划分问题,在图论、复杂网络、数据挖掘等方面都有着非常重要的作用和实际应用价值。本课题使用谱聚类方法来实现社区发现，应用K-means聚类算法得到社区划分。本毕业设计采用Unnormalized Laplacian算法以及Normalized Laplacian算法实现了一个可以用于社区发现的聚类算法，并分别采用人造数据以及Zachary柔道俱乐部网络数据进行了实验，结果表明本方法可以有效地发现社团结构。22346 关键词 数据挖掘 社区发现 图的划分 谱聚类算法 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 概述 网络在现实生活中存在于方方面面，它可以表示许多复杂的系统比如社会系统、信息交互系统、生态系统、生产过程系统等。通过先前众多学者的研究表明，我们可以将复杂网络中的节点分成不同的节点组。同一个的节点组节点之间的关联性和不是同一个节点组节点之间的关联性是不一样的，前者要更强一些。这种在复杂的网络里存在的拓扑学特性被命名为社区结构。由此可见，社区即是每个节点组。 (责任编辑：qin) |