复杂网络社团结构发现算法的研究

论文摘要

复杂网络可以用来描述现实社会中的实际网络,比如Internet,交通网,电子邮件联系网,电力网等常见的实体网络。它也可以表示包含大量个体和个体之间相互作用的系统,如恒星及星际气体中的化学反应,人与人之间的社会关系,物种之间的捕食关系,科学研究中的合作关系等。人们生活在一个充满着各种各样的复杂网络的世界中。这也使得对复杂网络的研究成为必要。由于复杂网络中节点众多,结构复杂,所以研究复杂网络非常困难。然而,复杂网络的社团结构性质可以帮助了解网络结构与分析网络特性,因此寻找网络中的社团结构具有极为重要的意义。从20世纪末开始,复杂网络的研究已渗透到生命科学、数理学科和工程学科、社会科学等众多不同的领域。对复杂网络的研究,已成为科学研究中一个极其重要的富有挑战性的课题。寻找复杂网络中的社团结构已经成为复杂网络研究的热点之一,本文正是对复杂网络中社团结构的发现方法进行研究。本文在详细研究已有的复杂网络社团结构发现算法的基础上,提出了两种新的社团发现方法:（1）在谱平分法的基础上,提出了一种新的复杂网络社团结构发现算法——基于谱平分法的社团划分方法。该算法对传统的SNN相似度矩阵进行改进,然后将改进后的矩阵与谱平分算法相结合来寻找网络中的社团结构。通过多个经典实例的验证,证明该方法对社团结构不明显的网络也具有较好的划分效果。并且与目前比较流行的社团发现算法进行比较可知,利用该算法划分得到的结果准确率较高。（2）将Wu-Huberman算法和贪婪算法的思想相结合,提出了一种新的社团发现方法——基于Wu-Huberman方法和贪婪算法相结合的聚类算法。该方法定义了一种新的局部模块度计算方法,并采用了新的距离衡量标准,即斜率距离来衡量社团之间的距离。通过实例验证可知,在社团数目未知的情况下,与已有的社团发现算法相比,该方法在计算速度上也有了明显的改善。

论文目录

• 摘要
• Abstract
• 1. 绪论
• 1.1 引言
• 1.2 复杂网络的发展史
• 1.3 复杂网络中的基本概念
• 1.4 复杂网络中的社团结构
• 1.5 研究内容与结构安排
• 2. 复杂网络中社团结构发现的常用算法
• 2.1 KERNIGHAN-LIN 算法
• 2.2 谱平分法
• 2.3 分裂算法
• 2.4 凝聚算法
• 2.5 派系过滤算法
• 3 一种基于谱平分法的社团划分方法
• 3.1 引言
• 3.2 预备知识
• 3.3 一种基于谱平分法的社团划分方法
• 3.4 实验
• 3.5 小结
• 4. 基于WU-HUBERMAN 方法和贪婪算法相结合的聚类算法
• 4.1 引言
• 4.2 预备知识
• 4.3 一种新的社团发现算法
• 4.4 实验
• 4.5 小结
• 5. 总结与展望
• 5.1 工作总结
• 5.2 未来研究展望
• 参考文献
• 致谢
• 攻读硕士学位期间论文发表情况