复杂网络上的社团结构探测研究

论文摘要

近年来复杂网络研究受到了来自物理以及其它学科的研究者的广泛关注,成为当今的一个研究热点。大量研究已经表明在真实世界中各种不同的复杂网络具有许多共同的结构特征,例如小世界性质、无标度性、社团结构等。我们对复杂网络的社团结构及其探测方法进行了研究。在复杂网络中社团结构的存在意味着网络通常由若干个社团组成,在这些社团内节点之间的连接相对紧密,而各个社团之间的连接则比较的稀疏。网络的这种结构特征对网络的动力学有着重要影响,并且在真实网络中这些社团通常对应着某种功能单元如社会网络中真实的社会分组、WWW上内容相关的网页、或论文引用网络中关于某个主题的论文。因此,探测分析网络的社团结构对我们认识和理解真实复杂网络的结构以及功能有着重要意义。目前,已经有许多研究者投身到社团结构探测的研究当中并提出了各种各样的算法以便能够快速而准确的找到网络中的社团,但是探测算法的时间复杂度和准确性之间的矛盾仍然是大规模复杂网络的社团结构分析面临的重要问题。在本文中,我们系统分析了已有的社团探测算法,然后设计了一种改进社团探测算法准确性的方案,并根据这个方案,提出了一类改进的社团探测算法。本文共分为五章。在第一章我们对复杂网络的研究进行了回顾,并介绍了本文的主要研究内容。在第二章,我们介绍了复杂网络的主要结构特征,并系统介绍了复杂网络的社团结构,包括社团的定义、社团结构探测、以及社团划分的评价。在第三章中我们系统分析了已有的一些社团探测算法及其性能。同时,根据研究的需要我们研究了这些算法如何扩展到加权网络,以及在考虑加权网络的内在边权之后算法的探测能力的变化。根据前一章的分析,我们在第四章中首先设计了一个改进社团探测算法精度的方案,然后据此提出了一类改进的Girvan-Newman算法,并在计算机产生的具有已知社团结构的网络以及一些真实网络上测试了这些算法。测试的结果显示无论是在计算机产生的网络上还是在真实网络上改进后的算法都要比原算法有更优异的表现。另外,我们还将改进的算法扩展到了具有内在权重的网络;测试的结果显示同样是考虑了内在边权,改进算法的权重版本要胜过原算法的权重版本。这些结果说明我们对算法的进行改进的尝试是成功的,同时也证实了我们的改进方案的可行性。第五章对本文的工作进行了总结,并对本领域的研究进行了展望。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 复杂网络及其发展
• 1.3 复杂网络研究的意义以及面临的挑战
• 1.4 本文的研究内容以及论文的结构安排
• 第二章 复杂网络的结构特征以及社团结构研究
• 2.1 引言
• 2.2 复杂网络的主要结构特征
• 2.2.1 小世界效应
• 2.2.2 聚类性
• 2.2.3 无标度性
• 2.2.4 度关联性
• 2.3 复杂网络的社团结构研究
• 2.3.1 社团定义
• 2.3.2 社团结构探测
• 2.3.3 社团结构划分的评价
• 2.4 小结
• 第三章 复杂网络的社团探测算法分析
• 3.1 引言
• 3.2 Girvan-Newman 的基于边介数的算法
• 3.2.1 算法
• 3.2.2 扩展到加权网络
• 3.3 Radicchi 等的基于边聚类系数的算法
• 3.3.1 算法
• 3.3.2 扩展到加权网络
• 3.4 Fortunato 等的基于信息中心度的算法
• 3.4.1 算法
• 3.4.2 扩展到加权网络
• 3.5 Newman 快速算法
• 3.5.1 算法
• 3.5.2 扩展到加权网络
• 3.6 Duch 等的极值优化算法
• 3.6.1 算法的基本思想
• 3.6.2 τ-EO 算法
• 3.6.3 扩展到加权网络
• 3.7 小结
• 第四章 一类改进的社团探测算法
• 4.1 引言
• 4.2 方案
• 4.3 算法的实现
• 4.4 算法的测试
• 4.4.1 计算机产生的网络
• 4.4.2 真实网络
• 4.5 扩展到加权网络
• 4.6 小结
• 第五章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 致谢
• 个人简历和攻读硕士学位期间所获成果