复杂网络社团发现算法的研究毕业论文.doc

《复杂网络社团发现算法的研究毕业论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、复杂网络社团发现算法的研究毕业论文目录第一章绪论11.1复杂网络的研究背景11.1.1从七桥问题开始11.1.2复杂网络近代的研究21.2复杂网络社团结构研究的现状31.3本文的研究内容以及文章结构6第二章复杂网络的基本概念以及网络拓扑的基本模型72.1复杂网络的基本概念72.1.1网络的图表示72.1.2平均路径长度82.1.3聚类系数82.1.4精准度92.1.5复杂网络社团结构定义92.2网络拓扑基本模型和性质102.2.1小世界模型102.2.2无标度网络模型112.2.3模块性与等级网络12第三章复杂网络中

2、的社团结构143.1分级聚类143.1.1凝聚算法143.1.2分裂算法153.2迭代二分法153.2.1Kernighan-Lin算法153.2.2谱平分法163.3其他经典算法173.3.1GN（Girvan-Newman）算法173.3.2Newman快速算法173.3.3Radicchi算法17II第四章基于随机游走的社团发现算法194.1随机游走算法的基本原理194.1.1随机游走算法的相似度矩阵获取194.1.2随机游走算法的矩阵融合204.1.3矩阵元素融合方式214.2随机游走算法的代码编译过程224

3、.2.1随机游走算法的相似度矩阵的获取224.2.2随机游走算法的相似度矩阵融合23第五章随机游走算法在社团划分中的应用255.1随机游走算法对复杂网络的划分255.1.1已知社团结构的复杂网络255.1.2对复杂网络的划分265.2随机游走算法的复杂度28第六章基于随机游走算法的程序优化296.1随机游走算法的复杂度的优化296.2随机游走算法的应用于加权网络30第七章总结与展望317.1总结317.2对未来的展望31参考文献34致谢35II北京邮电大学本科毕业设计（论文）第一章绪论复杂网络一般指节点众多、连接关系

4、复杂的网络。由于其灵活普适的描述能力,能够广泛应用于各科学领域对复杂系统进行建模、分析,近年来吸引了越来越多的人对其进行研究。随着研究的深入,人们发现许多实际网络均具有社团结构,即整个网络由若干个社团组成,社团之间的连接相对稀疏、社团内部的连接相对稠密。社团发现则是利用图拓扑结构中所蕴藏的信息从复杂网络中解析出其模块化的社团结构,该问题的深入研究有助于以一种分而治之的方式研究整个网络的模块、功能及其演化,更准确地理解复杂系统的组织原则、拓扑结构与动力学特性,具有十分重要的意义。自2002年Girvan和Newman基

5、于边介数提出GN算法以来,国际上掀起一股社团发现的研究热潮,来自生物、物理、计算机等各学科领域的研究者们带来了许多新颖的思想和算法,并广泛应用于各个学科领域的具体问题中。1.1复杂网络研究背景1.1.1从七桥问题开始近年来复杂网络研究的兴起，使得人们开始广泛关注网络结构复杂性及其与网络行为之间的关系，要研究各种不同的复杂网络在结构上的共性，首先需要有一种描述网络的统一工具。这种工具在数学上成为图(graph).任何一个网络都可以看做是由一些节点按某种方式连接而构成的一个系统。具体网络的抽象图表示，就是用抽象的点表示具

6、体网络中的节点，并用节点之间的连线表示具体网络中节点间的连接关系。实际网络的图表示法可以追溯到18世纪伟大的数学家欧拉(Euler)对著名的“Konigsberg七桥问题”的研究。Konigsberg是东普鲁士（现俄罗斯）的一个城镇，城中有一条横贯城区的河流，河中有两座岛，两岸和两岛间共有七座桥，一个人能否在一次散步中走过所有的七座桥，而且每座桥只经过一次，最后返回原地？1736年，欧拉仔细的研究了这个问题。他用数学抽象法，将被河流分隔开的四块陆地抽象为四个点，分别用A、B、C和D表示，而将七座桥抽象为连接四个点的七

7、条线，分别用a、b、c、d、e、f、g表示，这样就得到了四个点和七条线构成的一个图，如图（图1-1）所示。35北京邮电大学本科毕业设计（论文）图1-1七桥问题于是欧拉考虑如果一笔画出图1-1，则七桥问题迎刃而解。可以想象，能一笔画出的图形，一定只有一个起点和一个终点（这里要求起点和终点重合），中间经过的每一点总是包含进去的一条线和出去的一条线，这样除了终点和起点外，每一点都只能有偶数条线与之相连。因此，如果要求起点和终点重合的话，那么能够一笔画出的图形中所有的点都必然有偶数条线与之相连。从图1-1中四个点看，每个点都

8、是有三条或五条线通过，所以不能一笔画出这个图形，就是说不重复的一次走遍七座桥是据对不可能的。欧拉的七桥问题的抽象和论证思想，开创了数学中的一个分支----图论（graphtheory）的研究。因此，欧拉被公认为图论只父，而图1-1被称为欧拉图。事实上，今天人们关于复杂网络的研究与欧拉当年关于七桥问题的研究在某种程度上是一脉相承的，即网络结构域网