模块化无标度网络模型的建立与仿真分析毕业设计(论文)

计算机科学与技术学院毕业设计(论文)论文题目模块化无标度网络模型的建立与仿真分析 指导教师职 称讲师学生姓名学 号专 业班 级系 主 任院 长起止时间2013年11月23日至2014年5月30日2014年5月30日目 录摘 要iAbstractii第一章 绪论11.1课题的意义及背景11.2课题的目的21.3课题的内容3第二章 复杂网络与模块化无标度网络模型62.1复杂网络的概述62.2 复杂网络的统计特性7 2.2.1 平均路径长度8 2.2.2 聚类系数8 2.2.3 度与度分布92.3 典型无标度模型介绍11 2.3.1 BA模型11 2.3.2模块化无标度网络模型13第三章 BA模型与模块化模型算法比较153.1 BA模型15 3.1.1 BA模型的特性15 3.1.2 BA模型的算法163.2 模块化无标度网络模型17 3.2.1 模块结构的定义17 3.2.2 模块结构的定量描述-Q函数18 3.2.3 模块化无标度网络模型的算法21第四章 BA模型与模块化无标度网络模型的仿真与分析234.1 Matlab的介绍234.2 聚类系数与平均路径长度的比较24 4.2.1 聚类系数的比较25 4.2.2 平均路径长度的比较274.3度分布与累积度的比较28 4.3.1 度分布的比较28 4.3.2 累积度的比较354.4 模块度值的比较384.5 小结39参考文献42附 录45附录145附录248南华大学计算机科学与技术学院毕业设计（论文）模块化无标度网络模型的建立与仿真分析 摘要：在我们的现实生活中，很多复杂系统都可以抽象为复杂网络。复杂网路的研究，既是人们对现实网络的探究，也是对网络科学的发展。通过研究复杂网络，进一步了解现实生活中各种网络系统的发展规律，更好的制定应对机制，让我们的生活更加有序，让我们所处的网络化社会更加和谐，让我们的认知更进一步。我们的现实网络大多遵循无标度网络的特性。而BA网络是经典的无标度网络模型，进来，为了刻画真实网络所具有的模块化结构，科学家提出了模块化无标度网络模型，模块化无标度网络的研究也得到了广泛的关注。本文通过使用Matlab7.0对模块化无标度网络以及BA无标度网络进行了仿真分析，对比了他们的统计结果，得出他们的平均路径长度基本相同，度分布都遵从幂律分布，在对数坐标系下近似一条直线，聚类系数也大致相同。但是模块化无标度网络的模块度值要远大于BA无标度网络，更符合我们的真实网络，例如万维网，Internet等。为进一步研究复杂网络上的动力学行为打下坚实的基础。关键词：模块化无标度；平均路径长度；聚类系数；度分布；模块值The Establishment and Simulation Analysis of The Scale-free Modular Network ModelAbstract:In our real life, a lot of complex system can be abstracted as a complex network. Research on complex networks, inquiry to the real network is people,also for the development of network science. By the study of complex network,to further understand the development law of various network systems in real life, better develop coping mechanism, make our life more orderly, make the network society in which we live more harmonious, let our cognitive further. Our real network mostly follow scale-free network characteristics. The BA network is a scale-free network model, in the classical modular structure, in order to describe the actual network has, scientists have proposed modular scale-free network model of scale-free networks, modular has gained wide attention. In this paper, through the use of Matlab7.0 on the modular scale-free network and no BA simulated scale network, the statistical results of their comparison, the average path length and they are basically the same, the degree distribution follows a power-law distribution, a straight line approximation in logarithmic coordinates, clustering coefficient is roughly the same. But the modular scale-free network module value is much larger than the BA scale-free network, more in line with our real network, such as the world wide web, Internet etc. As the basis for further research on dynamical behavior in complex networks and lay hold.Key word：Modular scale-free;average path length;clustering coefficient;degree distribution;module value第一章 绪论1.1课题的意义及背景自二十世纪以来，以互联网为主的网络信息技术发展迅猛，使得我们人类得以以一个较高的速度进入网络的殿堂中来。今天，人类已然生活在一个各种各样的复杂网络所混合而成的世界中。人类社会所随之而来的网络化是一把双刃剑，它一方面给我们的生活与生产带来了便利，较大的提高了我们生产效率，生活水准，但它也给我们的生活造成了一些的负面影响，如：局部动荡、传染病等大范围，全球性的扩散。我们的生活越来越离不开网络，网络在我们生活中所扮演的角色，所承当的任务越来越重，如果不能全方面理解网络，那么对我们的生活将造成极大的影响。因此，我们必须加大对网络的开发与利用，掌握其发展规律，使物尽天择，人尽其责。网络不仅仅是各种各样复杂系统形态的表现形式，更是系统结构拓扑性的模型。一切事物都是由于两者或者更多客体相互作用所形成的，可以毫不夸张的认为，系统是相互作用的稳态。在物理学研究中，物理学家们主要研究物体间最基本的相互作用。在化学研究领域，化学家们则研究分子间的相互作用。在生物学领域，生物学家们研究基因，蛋白质以及生物体之间的相互影响与相互作用。因此，如果把一个事物看作是一个系统，那么其结构我们便可以想象成网络。在这个网络中，充当节点是我们前面所提到的各个个体，充当边的是各个个体之间的相互作用。而后，我们可以用我们所熟悉的研究网络的各种方法，来研究这些系统，分析他们的拓扑特性。这一思路，在许多领域，都引起了学者的关注。如果按照最早的方式，用一些规则图来研究分析各类系统的网络拓扑，范围很有限。于是，在数学家Erdos和Renyi的长期试验和不断努力下，终于完成了ER网络模型的建立，主要用来系统的解释通信工程和自然生命界中所涉及到的网络及其问题。用在各个网络节点间随机连接的方法，就可以模拟出这类系统的基本网络结构。这一方法铸就了随机网络理论的基础。在以后的科学研究中，这种方法主导了科学家们半个世纪之久。但这种方法是静态的，仅仅使用于不变的网络，而对于我们生活与现实世界中普遍存在的动态的，一步一步演化的系统所具有的一些重要特性，如马太效应，即富者更富现象，便无法进行分析研究。之后在1999年，A-L Barabasi等发表了他们的研究成果，他们在计算机科学的基础之上，实证性地探究分析了万维网，因特网等各类复杂网络的网络拓扑，并且发现了我们今天耳熟能详的“无标度特性”。这一创举打破了随机网络的限制，全面改善了我们对复杂网络系统的认识。使我们了解到我们生活的现实世界里，许多我们耳熟能详的网络大多遵从我们所发现的网络特性，由此我们可以推断，找到网络中普遍存在并且使用的法则，是切实可行的，在不久的将来，我们将全面掌控网络。随着复杂网络在各个科学领域的发展。无标度性和模块性是许多真实复杂网络存在的网络特性。例如WWW就是一个典型的无标度网络，我们可以把其看做是由许多网站的模块结构相互交叉构成的网络系统，其中同一个模块结构内部的各个网站关注和讨论的主题相似。为了通过模拟重现这种真实的复杂网络，构建模块化无标度网络模型得到了各领域学者的思考与探究。同时也为复杂网络上物理学行为的研究搭建一个良好的平台，奠定了坚持的基础，为复杂网络的学习、掌握和优化设计提供了最基本的支撑。模块化无标度网络模型的网络特征，正是复杂网络的结构中最具代表性的一种。模块化无标度网络模型的建立，充分还原了我们现实生活中复杂网络的形成。因此，对模块化无标度网络模型的建立与仿真分析，是我们了解真实复杂网络存在特性的重要手段，是为复杂网络的分析，控制，优化设计提供强有力支持的关键。1.2课题的目的 通过文献的阅读，老师的指导，充分理解模块化无标度网络模型的概念，了解模块化无标度网络模型的构造算法，以及其统计特性。了解复杂网络的研究概况及历史、在我们生活中的运用以及复杂网络的研究前景，方向对我们未来生活可能造成的影响。通过对Matlab的学习，了解其基本原理，掌握其理论知识，在老师的指导下，能够熟练使用Matlab。并且建立我们所需要的实验网络，分析数据，得到结果。毕业设计是对我们四年大学学习生涯的考察，是对我们在学校所学知识的的检验，在过去所学内容的理论基础上，进一步联系实际生活，是使学生具有从事科学研究初步能力，不如社会，提高技能的重要环节。此次毕业设计是我们到工作岗位上承担技术性工作前的最后一次实际演习，通过毕业设计的结果，检验我们四年大学生活是否虚度，也可以从中查找以前学习中的薄弱环节，督促我们加以弥补与改进。毕业设计一方面让我们更熟悉了自己在大学中所学习的理论，基本，方法，手段，更让我们对一些实际问题有了自己的看法，在遇到的问题时，能够沉着冷静的思考分析，得心应手的解决困难。通过毕业设计，完成我们对网络工程师的初步演练，使我们具有初步的科学研究能力，技能掌握方法。通过对毕业设计的学习研究，能够拓展我们的知识面，增长我们的实战能力，提高我们的技能水平。把所学的理论知识与实际问题结合分析，从而进一步提高计算机绘图的能力以及编写编程能力。通过毕业设计加深我们对基本知识和基本技能的理解和掌握。增强我们收集查阅文献手册、图表等技术资料的能力,比较论证的能力。提高了我们的分析能力，在问题的认知与见解方面有了全方位的提升，在成果后期的测试与调试过程中，能够运用多种方式，采用妥善的办法处理问题。增强了我们对计算机的应用能力，并且在一定程度上，提高了我们的外语水平。是在实际情况中运用计算机处理问题的体现，同时也运用了外语运用能力，口头和书面表达能力和综合分析和总结报告的能力。同时使我们具有工程技术人员应有的职业素养；认真，负责、务实，求是的科学态度；吃苦，耐劳，敢于攻坚，勇于创新，敢于奋斗的风貌；以及虚心，好学，团结，互助的优良作风。1.3课题的内容理解复杂网络基本模型、熟悉复杂的基础知识（如，聚类系数，平均路径长度，度分布等）。了解在多现实网络中，优先连接机制存在于某些区域中，为什么要优先连接，优先连接的好处，与实际意义。进而建立模块化无标度网络模型。比较经典BA无标度模型与模块化无标度网络模型的异同，分析模块化无标度网络模型的统计特征，在BA经典无标度网络基础上的改进与优点。深入理解复杂网络,模块化无标度网络模型及其生成算法，并对生成模型进行统计特性分析。具备C语言、Matlab或者其他计算机语言编程的能力。其次学习Matlab编程，学习常用函数的应用以及使用方法。Matlab，即一种计算机语言。取名源于Matrix Laboratory，意识是以矩阵的方式来处理计算机数据。此软件把数值计算，可视化环境放在了一起，直观方便，并且支持函数的计算，鉴于这些优点，越来越多的研究人员及学者开始广泛使用，应用范围也日益广泛。Matlab是matrix&laboratory的缩写，翻译过来即为矩阵工厂或者矩阵实验室。他的工作界面如下图所示：图1.1 MATLAB的工作界面Matlab由美国mathworks公司发布。主要提供了集计算，可视化，函数等于一身的高科技计算环境。Matlab所提出的解决方案，不仅为我们的网络学研究，以及数学研究，更为我们现实中一些必要的工程计算，及其他方面的科学做出了巨大的贡献。使过去许多遗留问题得到解决。Matlab的推出，很大程度上告别了传统计算机语言（如C、Fortran）的编辑模式，引领了国际计算机行业的先进水准。Matlab、Mathematica、Maple被誉为三大数学软件。因为他们的出现，我们人类在数学计算机类领域的研究才可以突飞猛进，取得不可估量的成就。Matlab不但可以运算矩阵、绘制图像。还可以计算函数，统计数据。而且支持各种算法。可以创建用户操作面板、甚至连接其他编程语言的程序一起工作等。在材料工程，通信技术，移动联通等大型公司，以及图像，金融等重要领域，Matlab都彰显了他不可替代的一面。Matlab的原理来自于我们所学习的矩阵。其命令表达式融会贯通于数学界，工程。与人们在日常生活中所使用的比较相似，所以Matlab处理这些问题，就比用传统编程语言简单便捷得多。并且Matlab兼备了Maple等其他软件的特点，这使得Matlab日渐称为数学软件界的一支新秀。在最近的版本兼容了C，FORTRAN，C+，JAVA等语言。支持混合语言的调运。客户将自己编写的程序编码导入到MATLAB函数库中，日后可以直接调用，方便快捷。此外在互联网上，还有许多MATLAB爱好者编写的实用的程序代码，我们可以直接下载使用，为广大用户切实提供了方便，有利于一起交流。 在此，我们通过Matlab仿真得到所需要的网络模型，分别设定不同的参数，分析两种复杂网络模型在算法和统计特征上的区别，完成毕业设计论文。第二章 复杂网络与模块化无标度网络模型2.1复杂网络的概述我们生活在自然界中，而自然界中不可避免的存在许许多多，各种各样，诡异多端的复杂系统，这些复杂系统可以归结为形形色色的网络，方便我们描述，探究。其中，一个典型的网络是由许多个点，与各个点之间相互连接的边组成的，其中这些点用来表示在各个真实系统中的每个个体，而这些边则表示每两个个体之间的相互作用联系，通常情况是根据两个点之间某种特定的关系而联系在一起的，反之则无法连接。那么有边相连的两个点我们说是相邻的两个点。例如神经系统，我们可以理解为这是一个由大量神经小细胞相互连接而形成的一个庞大的网络。我们的计算机系统则可以看成是由世界上各个地方大量自由工作的计算机，通过互联网聚集在一起，而形成的网络，类似的例如交通网络，生活电网等。然而，数学家和物理学家在考虑问题的时候，通常只专注于两个点之间是否有边连接，而这两个节点为什么连接，怎么连接，边是长边还是短边，在什么地方连接，又与哪一个下级相连接，却不是他们关注的对象。针对这一现象，我们定义了网络的拓扑性质，即在网络中，不考虑节点的具体位置和连边的具体状态就可以表现出来的特性，与之对应的结构即为网络拓扑结构。于是，又出现了一个问题，什么样的拓扑结构才是比较接近真实生活的结构呢？对于这个问题的探究，延续了一百多年，大致分为三个阶段。早期阶段，科学家们认为，复杂系统间的结构与关系与一些我们已知的规则图形比较相似，如二维平面上的欧几里得图，它看起来我们所穿的花纹衬衣，又比如说最近玲环网，它总是叫我们联想到一群手拉手，围着篝火跳舞的回族少女。而后，到了二十世纪五十年代末，科学家们经过苦思冥想，想出了一种新的方法来构造网络结构。这种方法是把每对节点之间的连边存在与否，按照一定的几率来计算，而不是固定的。在以后的几十年中，这种方法被认为是最研究真实系统最合适的网络。 自二十世纪末以来，以Internet为主，网络信息技术发展迅速，人类社会大踏步进入到网络时代。不仅是Internet及WWW，不仅是生活电网及城市交通网络，还是生物体内的新陈代谢网络，甚至包括科研合作网络以及各种文化、环境、社会关系网，等等网络，均是一些具有一定的特性的复杂网络，这标志着第三个阶段的到来。网络不仅方便了我们的生产与生活，而且对提高生产效率和生活质量具有不可估量的作用，但是网络也给我们的生活与工作及社会带来了一定程度上的不必要的麻烦。用我们通俗的眼光来看，各个复杂网络仅仅是各个研究领悟的不同研究对象，而复杂网络所关注的则是看似毫无联系的各种网络的共性及普适方法。复杂网络是以一种全新的角度开启的对社会、管理、工程技术、医药等各个领域的各种复杂系统探究思索的新思路,由此形成了多种领域，全体位相互重叠、多种方法相互渗透的一门新兴学科。每一个复杂的系统均可看做是相互作用的多个个体组成的系统 ,从而体现了复杂网络研究的普适性。同时复杂网络以开创性的眼光，保持个体的自主性，相互性，研究各复杂网络间的共性，寻求普遍适用的解决办法。复杂网络的研究已经成为各个层次的科学工作者共同聚集的论点，它以大量的研究做基础，以新颖的探究思路做手段，用科学的研究方法做论证，吸引了社会各界研究力量的参与。在07年的论文检索中发现，关于SCI和EI的发表超过了万篇文章，有力的证明了复杂网络研究的热度。我们想要对现实系统进行研究，在实际操作中不具备可操作性。现实系统规模庞大，结构冗余，变化较快，不等我们探究透彻，就已经发生了翻天覆地的变化。但是复杂网络理论告诉我们，可以通过对研究个体及其作用变换为一个网络模型。然后我们以模型为基础进行相关研究，以模型为研究基础，真实反映现实网络的结构，细致刻画现实网络的特征，保证我们研究对象的真实性，保证研究结构的可靠性，保证研究方式方法的科学性。2.2 复杂网络的统计特性在人类漫长的研究历程中，人们提出了许多概念和方法来描述网络的基本特征，其中最具有广泛研究意义的有：平均路径长度（average path length）、聚类系数（clustering coefficient）、度分布（degree distribution），下面我们将对他们逐一介绍。2.2.1 平均路径长度由名字我们便可得知，平均路径长度即为网络中两个节点和之间的距离。定义为连接这两个点的最短路径上边的数目。在一个网络中，任意两个内含节点之间的距离的最大值为网络的直径，记为,即 （2-1） 网络的平均路径长度，即为该网络中任意两个节点距离的平均值，即 （2-2）其中N表示该网络节点的总个数。网络的平均路径长度在一度也叫网络的特征路径长度。我们可以用时间量级来计算一个NM网络的平均路径长度。图2.1 简单网络如图2-1所示:这个小型网络有5个顶点，5条连线。我们便可以得到，网络直径，平均路径长度 例如，在城市道路交通网中，两地之间最短路径的路的个数。经过科学家们的长期研究得知，虽然现实网络中个体数目巨大，但是网络的平均路径长度却都很小，甚至让我们不可思议。2.2.2 聚类系数举个例子，在你的朋友关系网络中，你的朋友在很多时候彼此也是朋友，我们就把这种属性定义为为网络的聚类特性。我们假设网络有一节点，然后用条边将这个网络连接起来，那么这个节点就是节点的邻居。那么可知，在这个顶点最大限度的情况下有条边。那么这个节点真实连接的边数，和总的可能存在的边数之比即为节点的聚类系数，即 （2-3）从几何特点上看，上式可等价定义为 （2-4）“与顶点连接的三元组”是指涵盖顶点的三个顶点，并存在从顶点到其他两个顶点的两条边。2.2.3 度与度分布经过科学家们数年的努力，我们发现度是描述节点特征的主要指标。节点的度是说与节点连接的结点个数。对于有向网络，节点的度又分为出度和入度。节点的出度是指该节点指向其它节点的边的数目。节点的入度是指从其它节点指向该节点的边的数目。通俗来讲，节点的度越大就意味着这个节点在这个系统中连接的节点越多，扮演的角色越重要。我们把一个网络中所有包含的节点的度的平均值叫做该网络的平均度，用表示。网络中节点的度的分布情况可用函数来描述。一种说法是，表示在一个系统中随机选择的顶点的度为的概率。另一种说法是系统中顶点度数为的顶点数与顶点总数的比。完全随机网络的度分布近似其形态在距离最大值很远的地方处呈指数下降。这意味着并不存在的节点，这样的网络叫做均匀网络。经过许多科学家证明，许多实际网络的度分布事实上不符合泊松分布，而是符合幂率分布。我们把任意挑选到的顶点的度数为的概率, 记为 , 为度数,可以更直观的告诉我们该节点在该系统中所扮演的角色。除了这三种最基本的统计属性以外，复杂网络还具有许多与传统网络，ER网络等网络不一样的统计特征，这里面最值得关注的莫过于小世界性，和无标度属性。经过长期的研究表明，规则网络具有比较大的剧烈系数，和较大的平均路径长度：随机网络具有较小的聚类系数和小的平均路径长度。而后，科学家Watts和Strogatz开创了以后新的理论，以一个很小的概率，打断规则网络中原有的边，然后随机选择新的节点重新连接在一起，就形成了一个新的网络。这个网络与我们过去所研究的ER网络和规则网络均不相同，介于他们二者之间。它具有大的聚类系数和小的平均路径长度。往后，科学家把这种特性的定义为小世界性，把这种网络定义为小世界网络，如图2.2所示。图2.2 小世界网络拓扑结构图往后，在漫长的实验道路中，科学家们发现真实网络都具有小世界性。同时，科学家们还发现真实网络的节点按照幂律分布。这里的顶点的度是指该顶点所具有的连接节点的个数。节点服从幂律分布是指，可以用一个幂律函数近似的表示该节点与该特性的度之间的联系。幂律函数曲线如图2.3所示，是一条缓慢滑坡的曲线，这就告诉我们，在这个网络中可以找到度很大的节点。图2.3 BA网络度分布图 对于传统的规则网络和随机网络来说，度值在一个很狭窄的区间内取值，所以我们基本找不到和平均度值相差较大的节点。那么我们就可以把度看做是考察一个节点的重要指标。我们就把这种顶点的度的分布满足幂律分布的网络叫做无标度网络，把这种特性叫做无标度特性，如图2.4所示。图2.4 无标度网络拓扑结构图除了上文介绍的小世界性和无标度性，真实网络还存在许多统计上的特性，如，混合模式特性，度相关性，超小世界性等，有兴趣的读者可以查阅相关文献。在此，不一一介绍。2.3 典型无标度模型介绍 由上文我们可以知道，在小世界网络的研究兴起之后，后期有大量的科研学者投身到复杂网络的研究中。他们发现许多现实网络在统计特性上存在普遍共性，其中最显著的就是他们的节点度分布都服从幂律分布。这一发现逐渐演化成无标度网络，形成了无标度网络模型的建立，最具代表性的便是经典BA无标度网络模型。2.3.1 BA模型源于对科学的热爱，对真理的探索，1998年，Barabasi和Albert等开展了一项关于万维网(World Wide Web)的研究。他们本认为其结果应该是一个符合随机网络的“钟形图”，即泊松分布，但是他们却发现结果天壤之别。Internet上网页基本由少数几个高连通的页面相互串接。只有不到20%的页面连接大于4，其他均小于4。这些有高连通的页面却只占整个网络的极小部分，只有不到万分之一。他们计算了k个连接着Internet的页面，发现这些页面的连接也遵从幂律分布。于是在1999年，Barabasi和Alberty提出了史上最重要的一种离婚，即构造无标度网络的演化模型。他们也采取了与Price相类似的办法。Barabasi和Albert认为随机网络之所以不能解释集散节点存在的原因：是因为随机网络不能表现现实网络中的两个重要属性：第一，增长特性，我们的现实网络每天都不在不断变化，每天都有新的节点产生并加入到我们的网络中来，每天也都有旧的节点消失，我们的网络也是通过不断演化，更新而来的，而随机网路在安置连接之前能够得到所有的网络节点，而节点数在网络中是固定的，一成不变的;第二，优先连接机制，随机模型都假设在添加新的连接时，概率都是均匀的，而事实上却不是如此，许多真实网络都是择优连接的。例如Internet，人们在选择页面连接到何处时，本可从多达数亿的网站中选择，但是我们大部分人仅仅熟悉Internet中的一小部分，例如百度，酷狗这些网页，这一小部分分事实上含有连接度较多的网站，只要我们连接到这些节点，便可以连接到数以万亿的其他节点，这一偏好就等同于增强了他们的偏好，这种“择优连接”的过程，也发生在其他网络当中。比如在好莱坞，连接着关系较多的明星往往更便于得到新锐们的关注。又比如在我们每天所使用的互联网上，一些端口很多的路由器由于担负着繁重的工作，一般情况下会被分配到更多的带宽，以便更好的工作，服务于社会。因此我们便更喜欢把自己的电脑连接到这些路由器上，从而得到更快，更高效的网络服务。我们可以通过图2.5来更好的理解。图2.5 真实网络示意图在过去，我们常常说在我们的网络节点集散中，出现了“富者更富”的现象。这又是为什么呢？无标度网络模型给出了解释。介于增长特性和优先连接机制的出现，当网络中有新的节点产生时，他在选择自己的连接对象时比较喜欢和已经有较多连接的节点相连接。正如我们在生活中，如果让我们选择交朋友的对象，恐怕许多人都会选择已经有很多朋友的人来建立关系。随着时间的推移，这种趋势愈发明显，从而造成了集散现象的产生。显然，我们可以推论“富者更富”现象在以往的随机网络中是不可能出现的。 随着BA模型的发明与广泛推广，复杂网络的历史又翻开了一页新的篇章。人们在网络研究的历史长河中铸就了新的里程碑。此后，有更多的学者开始了对复杂网络的研究与探索，他们提出了诸如加速增长，局域时间，网络老化，网络适应性以及非线性优先连接机制等。但是我们必须承认一点，我们只能说绝大多数网络是无标度网络，而不能一概而论的说所有的现实网络都是无标度网络，还有小部分网络服从指数分布，截断形式等，这也是我们研究的科学性所在。如图2.6就是一个幂律分布的网络。 图2.6 典型的具有幂律分布的网络-蛋白质网络2.3.2模块化无标度网络模型 我们在漫长的学习与探索过程中，明白一个道理。即使是大家普遍认同的，我们也不能一概而论的，更不能断章取义。我们在上文中说，许多现实的系统网络都有小世界性和无标度性，换言之他们具有许多共同的全局结构特征。但是，他们还是有区别的，要不然我们怎么能说他们终究是不同的网络，在局部方面看，各个网络还是各有异同的。于此，我们就必须再了解这些网络的局部所存在不一样的地方，探讨这些不同产生的机理，过程，后期的发展状况。举个例子，我们生物界的细胞网络，细胞是靠各种功能联系在一起的，功能类似的细胞高度集中，形成了一个团体，我们把这个团体叫做模块。那么到底什么是模块呢？一般的定义是，一组物理性质或者功能性质而聚集在一起，共同工作，从而完成一个特例的功能的节点。在我们生活中许多地方，都具备了模块。比如说，我们现在所熟知的FACEBOOK，博客，微博，都是由许多有共同兴趣的人聚集在一起的：再比如说，在一个汽车的制造过程中，不管是发动机，还是轮胎，都是由一个特定的群体专业生产制造的，所以说高度模块化在我们的生活中随处可见，而模块化的工作，生活，是现代社会的必要的产物。例如在生物系统中，相对固定的核糖核酸和脱氧核糖核酸，就是我们生命活动的基础。事实上，一个系统中的绝大多数分子或者是具有模块化活动的一个细胞内的联合体的一部分（如核糖体），或者是参与到一个功能上的更广的模块以作为一个相对独立过程的调控单元（如信道中的信号放大）。那么网络中的模块是如何构成的呢？近期的研究表明，模体可能是复杂网络的基本模块，也就是我们所说的基本组成部分。假设两个网络具有相同的规模，那么无标度网络要比随机网络具有较高的聚类系数，即我们所说的高聚类行。所谓的高聚类行就是指这个网络的某一部分，由各种高度链接的顶点组成，成型一个团体也就是模块，而这也正是出现某一个功能模块的前提。在一个网络内部的某个模块显示了这个网络在一定层次上的链接模式。尽管如此，但是这么多模块也不是所有的模块都是重要模块的。在一个复杂网络中，可以包括各种各样的模块，如三角形模块，正方形模块，菱形模块等。其中的一些模块所占的比例很高，而另一些模块却占有较低的比例。这些比例高的模块就叫做模体。我们知道，一个复杂网络都是由他内部特定的模块所表示的，那么如果我们可以清晰准确的辨识出这些模块，就有利于我们了解这个网络的局部特征，进而了解整个网络。第三章 BA模型与模块化模型算法比较3.1 BA模型通过上文的介绍，我们知道随机网络和“小世界”网络的度分布遵从泊松分布。该分布的特点主要表现在在其均值处有一个峰值，而两侧则呈现出逐渐递减，导致这样的网络在后来也被称为指数网络（exponential networks）。随着科技的发展，技术的进步，后来人们提出了复杂网络的概念，例如我们熟悉的万维网，互联网，英特网等，以及生物界的神经系统网，生物体的新陈代谢网等的节点的度分布都遵从幂律分布。由于这种网络的顶点关联方式并没有显著的特别属性，我们就把他们称为无标度网络。为了进一步给大家解释这种网络中节点的度分布服从幂律分布的现象，Barabasi和Albert创造了一个无标度网络模型，就是我们现在所广泛研究的BA无标度网络模型。3.1.1 BA模型的特性在现实意义中，我们知道一个网络具有幂律度分布固然是有意义的，但是更为重要的是我们要理解幂律分布的产生机理。由Barabasi和Albert创建的BA无标度网络模型实际上阐述了真实网络的两个重要特性:(1) 增长特性：我们的网络每天都在变化，用户每天都在增加与退出，网上的网站也在每天更新，每天都有新的页面产生，有旧的页面撤除。再例如，每天都有新的车辆上户，也有旧的车辆报废；每天都有新的想法产生等等。所以说，我们的网络规模在不断增长。而ER随即图和WS小世界模型中网络节点数是固定的，这不符合实际网络的发展规律。 （2）优先连接特性：每当有新的节点加入到已知网络中时，他们在选择邻居的时候都愿意选择那些已经有很多节点连接的节点作为自己的邻居，也就是我们所说的“马太效应”或者说“富者更富”现象。举个例子，我们在做毕业设计时，我们喜欢参考借鉴那些名人学者的学术研究报告。在我们的朋友圈中，可能很多人都认识某几个特别受欢迎的人，但是这些人互相却并不认识。而在ER随即图中，两个节点之间是否有边相连是完全随机确定的，在WS和小世界模型中，长程边的端点也是完全随机确定的。3.1.2 BA模型的算法 1）增长性：开始时创建少量节点，在每个时间间隔添加一个具有条边的新节点（连接到已存在于系统中的个节点上）。2）择优连接：当选择与新节点连接时，假设新节点连接到节点i的概率取决于该节点的连通度，即 （3-1） 经过这样的计算后，我们在经过t时刻以后，就可以得到一个，mt条边的BA无标度网络模型。我们可以看到网络整体上呈现幂律分布：，幂指数。这个结果在后来的多种理论方法和实验结构都得到了证明，实验结果如图3.1所示。图3.1 BA网络度分布图3.2 模块化无标度网络模型 随着近年来对许多实际网络的研究及探索，人们发现，他们都有一个共同的特点，我们把这一特点叫做网络的模块结构。它指的是网络中的节点可以根据他们之间的连接关系分成一些个小团体，每个团体内节点间的连接比较紧密，团体间节点的连接比较分散，如图3.2所示。图3.2 模块化网络示意图模块结构在我们的实际生活系统中具有重要意义，比如说，在我们的人际关系网中，模块可以基于我们人类不同的职业，地域，国家，民族，信仰，工作，年龄等因素形成;又例如在我们的引文网中，不同的模块又代表了不一样的研究领域；在Internet中，不同模块又代表了不同主题的网站；在生物系统中，新城代谢网，神经系统网等，不同的模块表示了不同的功能：在我们的食物链中，模块可以表示每一个小的食物链;当然了，在我们网络的结构与性质科研中，模块结构也具有显著特征，并且为一些现实中存在的性质的研究提供了可靠方便的基础。3.2.1 模块结构的定义 经过大量的研究，网络中的模块结构目前还没有被广泛确认的定义，较为常用的是基于相对连接概率的的定义：网络中的节点可以依照某种特定的联系分成组，组内节点连接紧密，而组间节点连接稀疏。但是，这个定义中所提到的“紧密”和“稀疏”并没有明确的定义，也没有统一的标准，所以在我们的实际研究中，并不方便我们使用。基于此，人们给出了一些定量化的定义，如，提出了强模块和弱模块的定义。强模块的定义为：子图V中任意一个节点与V内部节点连接的度大于其与V外部节点连接的度。弱模块的定义为：子图中所有节点与V内部节点的度之和大于V中所有节点与V外部节点连接的度之和。看起来似乎拗口，但在实际中得到了广泛应用。另外，科学家们还提出了一个更强化的定义，集。所谓集就是一个节点的集合，它的所有真子集之间的连接都比与集合外部的连接要多的多。 当然了，还有另外一种定义。以连通性为标准定义模块，称之为派系。一个派系，包含3个或者更多的节点，这些节点形成一个全通图，也就是说要求每两个节点之间必须相互连接。然后我们可以通过特定的函数减少这些连接，那么我们就可以得到N个新的派系。那么这就必然导致其中的一些节点在不同的派系中出现，即节点的重叠性。这些重叠的节点属于多个派系，这些不同的派系通过这些重叠的节点而相互连接。那么可知，这些重叠的节点相互连接，这种模块也具有广泛的研究意义，因为在现实生活中，一个个体往往同时属于多个系统。当然，还有其他定义，在这里，由于篇幅的原因，我们就不一一介绍了。 为了方便，在此次研究中，我们采用基于相对连接概率的模块结构定义。3.2.2 模块结构的定量描述-Q函数 在我们日常的学习与研究中，那些通过描述而得出的定义不方便我们使用区分。为了更好的研究，科学家们给出了模块化函数的定义。这一函数以定量的角度说明了网络的模块结构，利于我们对模块进行划分。具体来说，这个函数是指，把网络中一个模块内部的边的数目与另外随机网络中节点的边数目进行比较，这个比值的期望值相减，便得到一个差值。 那么我们如何构造这个随机网络呢？首先，我们给定一个网络，保持所有顶点的模块属性一致，节点间的边根据节点的度任意相连。如果模块结构划分的好，那么模块内部连接的紧密程度应高于随机网络的期望水平。用Q函数定量描述模块划分的的模块化水平。假设网络已经被划分出模块结构，为顶点所属的模块，则网络中的模块内部连边所占比例可以表示成， （3-2）其中，为网络连接矩阵中的元素，如果两点有边相连则，否则等于0。为函数，即时，值为1，否则等于0。为网络中边的数目。在模块结构中，边随机连接的网络中，两点存在连边的可能性为，为顶点的度。所以函数的表达式为： （3-3） 模块化Q函数从出现到现在，受到了广大科研人员的喜爱与推崇。不仅改进了一些旧的探索模块结构的算法，并且创造出了很多以此为基础的新算法。为我们后续的科研工作奠定了基础。 无标度网络可以用不同的方法产生的ODS。第一个模型是由艾伯特和Barabsi提出的BA无标度网络模型。他们认为必要的网络具有无标度特性。第一是增长机制，随着社会的进步，网络也随之发展，网络规模的持续增大。例如每个月都会有新的研究论文的发表，WWW上每天都有新的网页产生。第二是优先连接机制而新的节点更倾向于与那些具有较高连接的HUB节点相连接。由这两种机制，我们提出的生成模型如下：从C社区表示为U1，U2，和每一个社区的一个市民ABER从初始节点，在每个时间点我们添加到每个社区的新节点M边缘连接N新的节点。在这个社区不同的节点在其他社区的CM-N不同节点已经存在于系统根据PA规则，N= KI /？研究级联手段的可能性。这个新的节点将被连接到节点i的依赖程度与上一顶点的关系：在我们的研究中，我们发现系统的平衡状态系统是渐近稳定的。结果表明，缩放行为是独立于它的初始拓扑的m和n值的变化。这样的结果不会发生质的变化。 受到上面说提及到的这两种方式及以往的工作方式的启发，我们提出了新的模型如下所述：从记为C的社区开始 U1 U2 U3UC，并付给每个社区一个小的标号，定位初始节点，在以后的每一步，我们给每个社区添加一个新的节点与相连，链接的边缘节点到新节点的距离小于等于N米。这个社区内的不同节点与其他C-1社区内的百万个节点真实的存在于这系统中，按照PA规则分布。我们定义为：表示新节点将被链接到节点I的依赖程度。在我们的研究中，我们发现该平衡状态是趋于稳定的，SYS-TEMS=12。这个结果说明：缩放行为是独立于该网络的初始节点N的个数和M N的取值变化。这个结果表示，网络的稳定性是不会随着网络及网络参数的变化而改变的。另外，度分布不管是在本地网络，还是每一个社区，更或者是全球网络中，都具有较强的稳定性，并且遵循PA机制，符合幂律分布。基于以前的测量方法，纽曼和格文提出了测量一个网络的特定部分，他们称之为模块化 ，如下：。表示行或者列的，归结为链接到模块的边缘，即链接到社区R和 HR 是模块的边缘 即在原有的网络，链接到子集R和W的节点子集。 在一个给定的网络（边缘节点的下降不考虑他们所在的社区）是可以得到的。在我们的网络模型中，我们可以改变的取值来得到关于模块结构强度各种值。 最大的值是从最精准的网络模块划分得来的。我们将得到。当时，表示强烈的模块结构。他的两个节点在同一模块的边缘，被定义为桥边，并且和桥边链接的两个节点属于不同的模块。3.2.3 模块化无标度网络模型的算法 如上所述，我们的模型不仅要考虑节点的度有限连接机制，而且还得考虑模块的规模优先选择。这两种优先连接机制如下： 1）模块结构的优先连接选择：当有一个新的节点加入到某个模块中，或者从一个模块中挑选其模块外的节点数时，它选择模块i的概率与模块的规模成正比，即： （3-4） 2）度优先选择连接：给定一个模块i，让一个新的节点从中选择连接对象时，它选择模块i内节点j的概率为： （3-5） 其中表示模块i内节点j的度，而是一个偏重，且。如下图所示，我们给出了该模型的演化示意图,如图3.3所示：图3.3 模型演化示意图第四章 BA模型与模块化无标度网络模型的仿真与分析上面一章节的内容中，我们描述了经典无标度BA模型与模块化无标度网络的异同，下面我们将通过Matlab对两者进行仿真模拟对比，来进一步了解。4.1 Matlab的介绍 Matlab软件是由美国Mathworks公司推出的用于数值计算和图形处理的科学计算系统环境。MATLAB是英文MATrix LABoratory(短阵实验室)的缩写。在Matlab环境下，用户可以集成地进行程序设计、数值计算、图形绘制、输入输出、文件管理等各项操作。 Matlab提供了一个人机交互的数学系统环境，该系统的基本数据结构是矩阵，在生成矩陈对象时，不要求作明确的维数说明。与利用c语言或FoRTRAN语言作数值计算的程序设计相比，利用MATLAB可以节省大量的编程时间。 Matlab的良好的开放性和运行的可靠性使原先控制领域里的封闭式软件包（如英国的UMIST，瑞典的LUND和SIMNON，德国的KEDDC）纷纷淘汰，而改以Matlab为平台加以重建。 MathWorks公司于2001年推出Matlab6.0版本，6.x版在继承和发展其原有的数值计算和图形可视能力的同时，出现了以下几个重要变化：（1）推出了SIMULINK。这是一个交互式操作的动态系统建模、仿真、分析集成环境。它的出现使人们有可能考虑许多以前不得不做简化假设的非线性因素、随机因素，从而大大提高了人们对非线性、随机动态系统的认知能力。（2）开发了与外部进行直接数据交换的组件，打通了Matlab进行实时数据分析、处理和硬件开发的道路。（3）推出了符号计算工具包。1993年MathWorks公司从加拿大滑铁卢大学购得Maple的使用权，以Maple为“引擎”开发了Symbolic Math Toolbox 1.0。MathWorks公司此举加快结束了国际上数值计算、符号计算孰优孰劣的长期争论，促成了两种计算的互补发展新时代。（4）构作了Notebook 。MathWorks公司瞄准应用范围最广的Word ，运用DDE和OLE，实现了Matlab与Word的无缝连接，从而为专业科技工作者创造了融科学计算、图形可视、文字处理于一体的高水准环境。Matlab的推出，很大程度上告别了传统计算机语言（如C、Fortran）的编辑模式，引领了国际计算机行业的先进水准。并且Matlab兼备了Maple等其他软件的特点，这使得MATLAB日渐称为数学软件界的一支新秀。在最近的版本兼容了C，FORTRAN，C+，JAVA等语言。支持混合语言的调运。客户将自己编写的程序编码导入到Matlab函数库中，日后可以直接调用，方便快捷。4.2 聚类系数与平均路径长度的比较 经过我们前面的介绍以及相关文献的考证，我们对经典BA无标度网络模型和模块化无标度网络模型有了大概的了解，那么这二者究竟有什么异同之处呢，下面，我们就用实证来分析。首先我们在Matlab中建立这两者的模型，通过模型的对比，得出我们所希望以及所预料的结果，验证我们的设计思路。在实验前，我们本着科学的研究方法，设计统一规模的模拟网络，便于我们对二者的分析比较。就BA而言，我们知道，BA网络所具有的优先链接增长机制，明确了每一个新节点加入网络后的连接方向。换言之，我们只要对初始网络中每个节点的度进行计算，就可以知道每个新节点的连接方向。度越大的节点，被新节点选取作为邻居的概率就越大。久而久之，富者越富的现象凸显。即各个节点的度是不一样的，一个节点被越多的节点相连，那么他的度就越大，新节点连接的概率就越大。就比如说一个好的歌手，如果他被很多的人喜欢，那么就有更多的人喜欢他，关注他。我们本次模拟所采取的算法如下： 1）增长性：开始时创建少量节点，在每个时间间隔添加一个具有条边的新节点（连接到已存在于系统中的个节点上）。2） 择优连接：当选择与新节点连接时，假设新节点连接到节点的概率取决于该节点的连通度，即： （4-1） 模块化无标度网络，在以BA网络作为基础模型，然后进行模块的划分，即在网络中选取M个点作为一个模块。然后我们对这个模块中的节点的度进行计算，那么新加入的节点就可以根据这个概率，在这个模块中进行优先连接。例如我们想要新开一家服装店，那么我们一定首选选择服装店稠密的街道进行开店，就是一个小的模块，所生成的网络也就是模块化网络。 我们本次模拟所采取的算法如下： 1）模块结构的优先连接选择：当有一个新的节点加入到某个模块中，或者从一个模块中挑选其模块外的节点数时，它选择模块i的概率与模块的规模成正比，即： （4-2）2）度优先选择连接：给定一个模块，让一个新的节点从中选择连接对象时，它选择模块内节点j的概率为： （4-3） 其中表示模块i内节点j的度，而是一个偏重，且。4.2.1 聚类系数的比较我们知道聚类系数C用来表示网络中节点的聚集情况，即我们平时所说的网络有多紧密。通过对聚类系数的比较，我们可以得到网络的紧密程度，对网络的了解更近一步。通过研究证实，只有在全连通网络中（即每个节点都与其他节点相连），聚类系统才可以等于1，一般情况下的网络中，剧烈系统均小于1。在完全随机网络中，C-N，但是在大量的实验证明下，大部分的真实网络中的节点比较喜欢聚集在一起，那么聚类系数C的值远大于N，但是远远小于1。为了便于对比，我们规定两种网络模型的网络规模一致，如表4.1所示。在往后的实验中，我们设定BA无标度网络模型都用BA缩写，而模块化无标度网络模型都用M缩写。实验中两种网络的参数设置如表4.1所示。表4.1 网络参数表BA模型M模型=8=8m=2N=2000N=2000随机连接C=5