复杂网络社团发现算法的研究及其应用

论文摘要

复杂网络是复杂系统的表现形式，由于这样的网络其节点数量规模较大，而且节点与节点之间的联系较为复杂，所以这样的网络就被称为“复杂网络”。近年来，随着对复杂网络特性的分析不断深入，探索网络中的社团结构逐渐成为研究热点。揭示网络中的社团结构，对于了解网络拓扑结构、分析网络特性、理解网络中各个部分的功能、发现网络中隐藏的规律和预测网络的行为都尤为重要，而揭示社团结构的方法就是利用网络中所已知的特性和信息，将看似无规律的网络划分出隐藏在其中的结构。由于现存的大部分社团发现算法是基于网络的整体进行计算和划分，其缺点为时间复杂度相对较高，并且其针对性也相对较弱。本论文认为，根据已知的网络局部信息所划分出的“局部社团结构”将对于一些网络的研究更加有针对性。在本文中所提到的“局部社团结构”是指根据提供的网络局部信息，按照某种规则而划分出的社团结构，该结构对所给出的局部信息有着特殊的意义。本文提出了两种针对不同情况的局部社团划分算法：（1）基于二部图的社团划分算法。二部图结构相对简单，将原网络抽象成为二部图结构的形式，并将原网络的节点作为二部图中的“下集节点”。在已知某两点的条件下，通过二部图得到其对应的初始社团结构，利用初始社团结构在“下集投影”中利用AC算法和边介数等概念，划分出与已知节点相关的“相似性社团”结构。由于在进行局部社团划分时并不需要对整个网络进行计算，该算法在对随机给出的节点进行计算时，有比较好的即时性。此方法适用于发现与已知节点相关的“相似性社团”。（2）基于中心度发现社团将度中心度与流介数中心度相结合，首先计算出节点的度中心度和流介数中心度，得出网络中的几何中心点和信息、物质或能量在网络上传输时经过路径最多的节点，并将这两个指标作为一个整体考虑，得到这两个指标相对比较大的节点，再在这些节点和其邻居节点上利用CPM社团发现算法，从而发现网络中的“中心社团”。此方法可以发现网络中相对“重要”的社团，这对复杂网络上的传播机理、相继故障等分析都有一定的意义。随后利用该方法分析兰州市公共交通线路网络的中心社团结构，实验结果表明了该社团在网络中的确起到了比较重要的作用。此方法适用于发现网络中的中心社团结构。

论文目录

• 摘要
• Abstract
• 常用符号
• 插图目录
• 表格目录
• 第1章 绪论
• 1.1 研究背景和意义
• 1.2 基本概念
• 1.2.1 密度、平均路径长度、聚类系数、度分布
• 1.2.2 中心度
• 1.3 国内外研究现状
• 1.3.1 分裂与聚合方法
• 1.3.2 其它算法
• 1.4 本文的主要研究内容与组织结构
• 第2章 具有代表性的社团结构划分算法
• 2.1 Kernighan-Lin算法
• 2.2 谱平分方法
• 2.3 分裂方法
• 2.3.1 GN算法
• 2.3.2 快速分裂算法
• 2.4 聚合方法
• 2.4.1 Newman快速算法
• 2.4.2 结合谱分析的凝聚算法
• 2.5 本章小结
• 第3章 结合二部图发现局部社团算法
• 3.1 Aaron Clauset算法
• 3.2 二部图表示复杂网络
• 3.3 基于二部图表示的社团发现算法
• 3.4 社团发现算法实验及分析
• 3.5 本章小结
• 第4章 基于中心度发现社团算法
• 4.1 派系过滤算法
• 4.2 中心度分析
• 4.3 基于中心度发现社团算法
• 4.4 社团发现算法实验及分析
• 4.4.1 实验网络运用中心度发现社团算法及分析
• 4.4.2 实际网络运用中心度发现社团算法及分析
• 4.5 本章小结
• 总结与展望
• 参考文献
• 致谢
• 附录 （攻读学位期间所发表的学术论文目录）