复杂网络中社团结构的发现

论文摘要

现实中存在的大量复杂系统都可以用各种各样的网络进行刻画。复杂网络是复杂系统的抽象表示,由节点和边组成。网络中的节点代表现实中的不同个体,边则代表这些个体之间的关系。复杂网络理论的研究不仅仅属于数学范畴,而是涉及到了从物理学到生物学,从工程技术到管理学和社会科学等众多领域的研究,并且受到越来越多的重视和关注。人类社会的日益网络化也需要人们对各种人工的和自然的复杂网络有更加深刻的认识和了解。复杂网络已成为网络时代科学研究中的一个极其重要的具有挑战性的课题,甚至被称为“网络的新科学”。更为重要的是,有越来越多的研究表明,许多看上去各不相同的网络之间都存在着非常惊人的相似之处,社团结构就是其中之一。发现网络中的社团结构,对于了解网络结构和分析网络特性都有着非常重要的意义。社团结构的分析在生物学领域、物理学领域、计算机图形领域和社会学领域等众多不同领域中都有着非常广泛的应用。因此,如何利用网络中的各种信息准确的分析社团结构,是一个值得研究的问题。本文正是通过对社团性质的深入研究,开展了如下的研究工作。一种基于共享邻居数的社团结构发现算法。该方法首先选取度最大的节点作为社团的初始节点。其次,计算已知社团与其邻居节点之间的共享邻居数。最后,根据共享邻居数的大小,找到与社团连接最强的节点,并且利用局部模块度判断是否将该点加入到已知社团中去,进而达到发现社团结构、实现网络聚类的目的。为了验证该算法的有效性和可行性,将该方法应用于三个典型的复杂网络,取得了较好的实验结果。基于局部信息的社团结构发现算法。通过定义边的聚类系数和基于局部信息,提出了一个寻找复杂网络中社团结构的算法。该方法首先在网络的剩余节点中寻找度最大的节点作为社团的初始节点。然后利用该节点的边聚类系数和该点的度数值,判断与社团相连的其他节点是否可以加入到节点所在的社团中。最后得到了复杂网络的社团结构。通过对三社团网络和空手道俱乐部网络的实验,证明了该方法的可行性和有效性。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 选题背景
• 1.2 研究问题的国内外研究现状
• 1.3 复杂网络中几个典型的网络
• 1.4 本文研究的主要内容
• 1.5 文章组织结构
• 2 复杂网络中社团发现的常用算法
• 2.1 分割方法
• 2.1.1 Kernihan-Lin 算法
• 2.1.2 谱平分法
• 2.1.3 Wu-Huberman 算法
• 2.2 分级聚类方法
• 2.2.1 Newmen 快速算法
• 2.2.2 GN 算法
• 2.2.3 基于相异性算法
• 2.2.4 基于信息中心度的算法
• 3 基于共享邻居数的社团结构发现算法
• 3.1 引言
• 3.2 相关概念
• 3.2.1 局部模块度
• 3.2.2 共享邻居数
• 3.3 算法描述
• 3.4 实验与分析
• 3.4.1 Zachary 空手道俱乐部关系网络
• 3.4.2 三社团网络
• 3.4.3 足球网
• 4 基于局部信息的复杂网络社团结构发现算法
• 4.1 引言
• 4.2 相关概念
• 4.3 算法描述
• 4.4 实验与分析
• 4.4.1 三社团网络
• 4.4.2 Zachary 空手道俱乐部网络
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢