复杂网络中的社团结构探测和应用研究

摘要

在现实中，许多复杂系统可以表示成复杂网络。其中，节点表示系统的各种元素，连边表示元素之间的联系。通过应用复杂网络理论，人们能够更好地理解、预测和控制复杂系统的行为。随着对复杂网络的深入研究，人们发现许多实际网络都具有社团结构，即各个子图的内部连接比较紧密，而子图之间的连接比较稀疏。通过对社团结构的研究，人们能够更好地了解网络结构的特征和功能。目前社团结构的研究包括社团结构的定义、探测和应用。本文分别对社团结构的探测和应用进行了研究，主要贡献和创新点如下：
　　(1)提出了一种快速的模拟退火优化算法，该算法通过优化模块度来探测静态网络中的社团结构。尽管许多基于模块度优化的社团探测算法被提出，但是它们本质上都是基于一种贪婪策略来优化模块度，因此获得的模块度通常都是一种局部最大值。基于此，本文利用模拟退火算法来优化模块度。同时，为了提升模拟退火算法的收敛速度，本文从两个方面对它进行优化：(i)利用层次聚类算法获取一个初始社团划分；(ii)在优化模块度的每一步，随机从一个社团中提取一个连通子图并转移到另外一个社团。实验结果表明该算法不仅能够获得很高的模块度，而且与传统模拟退火算法相比，极大地提升了计算效率。
　　(2)提出了一种快速的动态社团探测算法，该算法首先利用上一时刻的社团结构和当前时刻的网络结构构造一个小网络，然后在小网络上探测当前时刻的社团结构。实验结果表明与传统算法相比，该算法极大地提升了社团探测的计算效率。另外，本文还提出了一种快速的社团映射算法，该算法首先将上一时刻的每个社团分裂成若干个小模块，然后使用这些小模块构建一个小网络并在小网络上探测当前时刻的社团。由于每个社团都可以看成是若个小模块的组合，因此在社团映射阶段可以通过统计两个社团的共同模块来计算它们的相似度。实验结果表明该算法不仅能够保证社团划分的质量，而且还能够极大地提升社团映射阶段的计算效率。
　　(3)提出了一种基于社团结构的关键节点组挖掘算法。对于许多传统算法来说，它们通常都是选择前k个最重要的节点或者k个互不相连的重要节点作为关键节点。然而，这些关键节点可能通常只位于少数社团。由于一个关键节点的影响力很难从它所在的社团传播到其它社团，因此传统算法选择的一组关键节点的影响力有限。为了最大化一组关键节点的影响力，本文提出了选择关键节点的三个约束条件：（i）单个节点的影响力很强；(ii)它不能与已知的关键节点相连；（iii）它不能与包含关键节点的社团相连。实验结果表明该算法选择的一组关键节点更有影响力。
　　(4)提出了一种基于社团结构的快速链路预测算法。在实际网络中，链接倾向于在局部聚集并形成社团结构，这种现象表明社团结构与链路形成之间存在相关性。因此，本文首先提出一种获取独立社团划分样本的算法，然后设计了两个基于社团划分样本的统计量，分别用来预测社团内部和社团之间的节点对产生连边的概率。实验结果表明与经典的SBM模型相比，该算法不仅能够准确地预测网络中的丢失连边，而且还能够极大地提升计算效率。另外，通过该算法计算的连边概率，本文揭示了社团结构中的三种链路形成机制。实验结果表明该算法在由三种链路形成机制选择的测试集上具有更高的准确率。
　　上述前两个工作分别提升了静态社团探测算法和动态社团探测算法的计算效率，而后两个工作则分别研究了社团结构在关键节点识别和链路预测中的应用。

目录

声明

第一章 绪论

1.1 研究工作的背景与意义

1.2 国内外研究历史与现状

1.3 本文的主要研究内容

1.4 本论文的结构安排

第二章 复杂网络的基础理论

2.1 复杂网络的基本拓扑性质

2.2 复杂网络模型

2.3 社团结构的定义

2.4 社团结构生成模型

2.5 社团质量评价指标

2.6 本章小结

第三章 静态网络中的社团探测研究

3.1 概述

3.2 快速的模拟退火优化算法

3.3 实验结果与分析

3.4 本章小结

第四章 动态网络中的社团探测及演化研究

4.1 概述

4.2 时间窗口划分方法

4.3 动态社团相关概念

4.4 快速的片社团划分方法

4.5 快速的片社团映射方法

4.6 本章小结

第五章 基于社团的多关键节点识别方法研究

5.1 概述

5.2 一组关键节点识别算法

5.3 实验结果与分析

5.4 本章小结

第六章 基于社团的链路预测研究

6.1 概述

6.2 快速的链路预测方法

6.3 实验结果与分析

6.4 本章小结

第七章 全文总结与展望

7.1 全文工作总结

7.2 后续工作展望

致谢

参考文献

攻读博士学位期间取得的成果

参加的科研项目