基于拓扑势和谱聚类的社区发现研究

摘要

社区发现是复杂网络领域的热点研究内容。社区发现算法有很多种，谱聚类方法是其中一类典型的方法。与其他的传统方法相比，该方法具有映射简单，数理逻辑严密，及适用于任何形状的数据集等优点。但是，谱聚类方法也存在一些不足。首先，需要人工确定社区数目，虽然可以利用谱间隙的梯形结构确定社区数目，但是当网络社区结构不明显时，无法通过Normal矩阵的特征向量对应的阶梯数目判断社区个数。其次，构建谱聚类的映射矩阵多采用节点度构造，节点的度能够直观地反映节点与邻接节点间的关系，但是无法反映其与网络中其他节点之间的联系，无法包含更多的结构信息，致使特征值及其相应特征向量的计算出现偏差，在一定程度上影响了社区划分结果的准确性。
　　本文提出基于拓扑势场模型的社区数量检测方法。该算法基于复杂网络构建拓扑势场，然后根据节点的拓扑势值计算网络的凹凸性参数。该值越大，复杂网络对应拓扑势模型的波峰波谷越明显，该值越小，复杂网络所对应拓扑势模型的起伏越平缓。本文针对上述两种类型复杂网络的特点分别搜索局部极大势值节点，并对这些节点进行必要的判定和合并，最终检测出整个复杂网络的社区数目。通过对真实复杂网络和人工生成的网络的实验，表明该方法具有较高的社区数量检测的正确率。提出融合拓扑势场和谱聚类的社区发现算法。该算法利用节点拓扑势值构造谱聚类中的节点标准矩阵，并通过基于拓扑势场模型的复杂网络社区数量检测方法所获得的局部极值点指导谱聚类进行社区发现，将局部极值点作为K-means聚类算法的初始中心点，减少迭代次数，提高谱聚类算法的性能。节点拓扑势是周围节点在本节点处产生势值的叠加和，能从全局角度反映节点间的紧密关系，使得节点标准矩阵包含了更多的节点间结构信息，有助于提高社区划分结果的准确性。通过对真实复杂网络和人工生成的网络的实验，表明该方法对能够有效的发现网络的社区，划分正确率更高。

目录

封面

声明

致谢

中文摘要

英文摘要

目录

1 绪论

1.1 研究的背景与意义（Background and Significance）

1.2 研究现状（Research Overview）

1.3 本文主要研究内容（Main Research Contents）

1.4 本文组织结构（Organization of this Thesis）

2 相关技术综述

2.1 拓扑势场（The Topology Potential）

2.2 谱聚类（Spectral Clustering）

2.3 本章小结（Summary）

3 基于拓扑势场模型的社区数量检测方法

3.1 引言（Introduction）

3.2 社区数量检测（The Community Number Detection）

3.3 仿真实验（Simulation Experiment）

3.4 本章小结（Summary）

4 基于拓扑势和谱聚类的社区发现算法

4.1 引言（Introduction）

4.2 社区发现算法分析（ Analysis of Community Discovery Algorithm）

4.3 仿真实验（Simulation Experiments）

4.4 本章小结（Summary）

5 总结与展望

5.1 本文总结（Conclusions of Thesis）

5.2 进一步的研究工作（Future Work）

参考文献

作者简历

学位论文数据集