复杂网络的社团探测：基于节点相似度的新算法

摘要

随着复杂网络理论不断完善与应用研究的深入开展，网络科学已经逐步发展成为当前备受关注的热点课题。作为各类复杂系统一个共有的重要性质，社团结构对于理解网络系统的结构与功能具有重要的理论意义与应用价值，是网络科学研究的一个重要内容。理论上，社团探测是一个NP难题，其有效算法无法回避时间复杂度与计算精确度之间的矛盾。这一矛盾随着大数据时代的到来而变得更加尖锐。发展快速而准确的社团探测算法是目前社团结构研究的一个重点。
　　本论文首先回顾了复杂网络的拓扑性质与社团结构特征，总结和分析了传统的社团探测算法。其次，基于经典的GN算法，我们提出了一种改进的GN算法来探测无本征边权的网络，然后拓展到加权网络中。将改进的算法应用于人工和真实网络，测试结果表明：在无权和加权网络中，该算法均能够更有效地探测到社团结构。此外，改进算法中的边介数加权迭代方案可以直接应用于其它的社团探测算法中。
　　基于模块度优化的社团探测方法是一类广泛应用且有效的社团结构探测策略。考虑到网络理论中的节点相似度与社团结构探测的关联，我们针对模块度优化算法提出了基于局部拓扑相似度的社团探测算法。其算法的关键技术是：利用局部节点相似度将无权网络加权或者将加权网络重新权重化，然后再基于模块度优化方法实现网络的社团结构探测。我们将上述方案与三种传统的社团结构探测算法相结合，在均匀网络和异构网络中进行测试，比较分析了局部相似性指标对基于模块化的探测算法的影响。结果表明：各种局部相似性指标对改进的基于模块化的算法是起了至关重要的作用，在保证比较低的计算复杂度的同时，算法精度得到了显著提升，而且有效减弱了传统社团探测算法的分辨率限制。
　　最后，我们对本文的工作进行了总结，并对本领域的研究进行了展望。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪 论

1.1 研究背景与意义

1.2 国内外研究现状

1.3 论文的研究内容与结构安排

第2章 复杂网络的拓扑特征与社团结构

2.1 复杂网络的表征

2.2 复杂网络的拓扑性质

2.3 社团结构

第3章 几类经典的社团探测算法

3.1 Kernighan-Lin算法

3.2 基于Laplace矩阵特征值的谱平分法

3.3 Girvan-Newman算法

3.4 Newman 快速算法

第4章 社团探测算法的改进与测试

4.1 基于边介数的社团探测算法

4.2 基于节点相似度的社团探测算法

第5章 总结与展望

5.1 总结

5.2 展望

参考文献

致谢

个人简历与攻读硕士期间完成的论文