《《复杂网络社团发现算法的研究》-公开DOC·毕业论文》由会员分享，可在线阅读，更多相关《《复杂网络社团发现算法的研究》-公开DOC·毕业论文（40页珍藏版）》请在金锄头文库上搜索。
1、本科毕业设计（论文）题目:复杂网络社团发现算法的研究姓名 学院 信息与通信工程专业班级 学号 班内序号 指导教师 2012年6月复杂网络社团发现算法的研究 摘 要近些年，随着WS小世界网络模型和BA无标度网络模型的提出，国内外掀起了研究复杂网络的热潮。复杂网络是对于复杂系统的高度抽象，其中许多性质如小世界性质、无标度性质以及聚集性质等等已经得到了充分的研究。复杂网络的研究是以系统的观点来看待真实系统，如Internet网络、电力网、新陈代谢网络等。(大量的文献表明，)复杂网络通常会呈现出社区结构特性，而如何在实际网络中高效地发现社区结构是近年来复杂网络的研究热点之一。社团结构是复杂网络普遍存在
2、的拓扑特性之一，发现复杂网络中的社团结构也是复杂网络研究的基础性问题。在文章中讨论了一些复杂网络以及关于社区评估和确定方面的概念、理论、算法及应用等。同样的，文章中也讨论了一种可以应用于大型复杂网络的社团发现的random walk算法，并且显示了它和其他算法在社团划分上有相同的表现，同时拥有更低的复杂度。文章中将random walk算法应用于对已知社团结构的复杂网络的划分以及比较其划分的社团结构的结果。除此之外，文章中对于此类算法给出一定改进，使该算法在复杂网络的社团划分上拥有了更高的准确度以及较低的复杂度。关键词 复杂网络，社团发现算法，random walk，复杂度Verifying
3、Platform of Cognitive Radio NetworkABSTRACTIn recent years，as the WS small-world network model and BA scalefree network model was proposed，the study on complex networks is achieving a climax at home and abroad nowComplex network is the highly abstract of the complex system, many of the properties, s
4、uch as small world nature, scale-free property and gathered properties and so on, have got fully research. The study on complex networks treats the real systems such as the Internet，electricitynetworks and metabolic networks with the viewpoint of system science(Lots of literatures show that communit
5、y structure exists in many real networksHow to find such communities effectively is one of focuses of many recent researches in the branch of complex networksCommunity structure is one of the common topological characteristics of complex networks. Community detection has become a fundamental problem
6、 in the research field of complex networks.In the article, the author discusses some complex networks as well as the theory, method and application about the evaluating and identifying of the community. Similarly,in this context we also discuss the random walk algorithm that can be used in a large,
7、complex network to identify the community and show that it performs as well as other methods at the division of complex networks, but at lower computational complexity.In the article the algorithm is applied to the division of complex networks that has knowing the community structure and compare the
8、 results of the classification of the community structure. In addition, the article gives certain improvement to such algorithm, so that the algorithm in the community division of complex network has the higher accuracy and lower complexity.KEYWORDS the complex network, community detection, random w
9、alk, complexity目录第一章绪论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第三章 复杂网络中的社团结构 143.1 分级聚类143.1.1 凝
10、聚算法143.1.2 分裂算法153.2 迭代二分法153.2.1 Kernighan-Lin 算法153.2.2 谱平分法163.3 其他经典算法173.3.1 GN（Girvan-Newman）算法173.3.2 Newman快速算法173.3.3 Radicchi算法17第四章 基于随机游走的社团发现算法194.1 随机游走算法的基本原理194.1.1 随机游走算法的相似度矩阵获取194.1.2 随机游走算法的矩阵融合204.1.3 矩阵元素融合方式214.2 随机游走算法的代码编译过程224.2.1 随机游走算法的相似度矩阵的获取224.2.2 随机游走算法的相似度矩阵融合23第五章
11、随机游走算法在社团划分中的应用255.1 随机游走算法对复杂网络的划分255.1.1 已知社团结构的复杂网络255.1.2 对复杂网络的划分265.2 随机游走算法的复杂度28第六章 基于随机游走算法的程序优化296.1 随机游走算法的复杂度的优化296.2 随机游走算法的应用于加权网络30第七章总结与展望317.1 总结317.2 对未来的展望31参考文献34致谢35I北京邮电大学本科毕业设计（论文）第一章 绪 论复杂网络一般指节点众多、连接关系复杂的网络。由于其灵活普适的描述能力, 能够广泛应用于各科学领域对复杂系统进行建模、分析, 近年来吸引了越来越多的人对其进行研究。随着研究的深入,
12、人们发现许多实际网络均具有社团结构,即整个网络由若干个社团组成, 社团之间的连接相对稀疏、社团内部的连接相对稠密。社团发现则是利用图拓扑结构中所蕴藏的信息从复杂网络中解析出其模块化的社团结构, 该问题的深入研究有助于以一种分而治之的方式研究整个网络的模块、功能及其演化, 更准确地理解复杂系统的组织原则、拓扑结构与动力学特性, 具有十分重要的意义。自2002 年Girvan 和Newman 基于边介数提出GN 算法以来, 国际上掀起一股社团发现的研究热潮, 来自生物、物理、计算机等各学科领域的研究者们带来了许多新颖的思想和算法, 并广泛应用于各个学科领域的具体问题中。1.1复杂网络研究背景1.1
13、.1 从七桥问题开始近年来复杂网络研究的兴起，使得人们开始广泛关注网络结构复杂性及其与网络行为之间的关系，要研究各种不同的复杂网络在结构上的共性，首先需要有一种描述网络的统一工具。这种工具在数学上成为图(graph).任何一个网络都可以看做是由一些节点按某种方式连接而构成的一个系统。具体网络的抽象图表示，就是用抽象的点表示具体网络中的节点，并用节点之间的连线表示具体网络中节点间的连接关系。实际网络的图表示法可以追溯到18世纪伟大的数学家欧拉(Euler)对著名的“Konigsberg 七桥问题”的研究。Konigsberg 是东普鲁士（现俄罗斯）的一个城镇，城中有一条横贯城区的河流，河中有两座
14、岛，两岸和两岛间共有七座桥，一个人能否在一次散步中走过所有的七座桥，而且每座桥只经过一次，最后返回原地？1736年，欧拉仔细的研究了这个问题。他用数学抽象法，将被河流分隔开的四块陆地抽象为四个点，分别用A、B、C和D表示，而将七座桥抽象为连接四个点的七条线，分别用a、b、c、d、e、f、g表示，这样就得到了四个点和七条线构成的一个图，如图（图1-1）所示。图1-1 七桥问题于是欧拉考虑如果一笔画出图1-1，则七桥问题迎刃而解。可以想象，能一笔画出的图形，一定只有一个起点和一个终点（这里要求起点和终点重合），中间经过的每一点总是包含进去的一条线和出去的一条线，这样除了终点和起点外，每一点都只能有
15、偶数条线与之相连。因此，如果要求起点和终点重合的话，那么能够一笔画出的图形中所有的点都必然有偶数条线与之相连。从图1-1中四个点看，每个点都是有三条或五条线通过，所以不能一笔画出这个图形，就是说不重复的一次走遍七座桥是据对不可能的。欧拉的七桥问题的抽象和论证思想，开创了数学中的一个分支-图论（graph theory）的研究。因此，欧拉被公认为图论只父，而图1-1被称为欧拉图。事实上，今天人们关于复杂网络的研究与欧拉当年关于七桥问题的研究在某种程度上是一脉相承的，即网络结构域网络心智密切相关。1.1.2 复杂网络近代的研究20世纪90年代以来，以Internet为代表的信息技术的迅猛发展使人类社会大步迈入了网络时代。从Internet到WWW，从大型电力网络到全球交通网络，从生物体中的大脑到各种新陈代谢网络，从科研合作网络到各种经济、政治和社会关系网络等，可以说；人们已经生活在一个充满着各种各样的复杂网络的世界中。人类社会的网络化是一把“双刃剑”：它既给人类社会生产与生活带来了极大便利，提高了人类生产效率和生活质量，但也给人类社会生活
