复杂网络结构对信息路由鲁棒性的影响毕业设计(论文).doc

《复杂网络结构对信息路由鲁棒性的影响毕业设计(论文).doc》由会员分享，可在线阅读，更多相关《复杂网络结构对信息路由鲁棒性的影响毕业设计(论文).doc（38页珍藏版）》请在三一办公上搜索。

1、计算机科学与技术学院毕业设计(论文)论文题目复杂网络结构对信息路由鲁棒性的影响 指导教师职 称讲师学生姓名学 号专 业班 级系 主 任院 长起止时间2013年10月11日至2014年5月23日2014年5月23日目 录摘要iAbstractii第一章 绪论11.1 课题的研究背景和意义11.2 复杂网络上信息路由的鲁棒性概述21.3 课题的提出及主要工作4第二章 复杂网络的拓扑结构参数62.1图的基本概念62.2网络的聚类系数72.3网络的度分布92.4实际中的网络拓扑112.4.1 Internet112.4.2 www122.4.3 其他网络阅读概述13第三章 复杂网络模型143.1 随机

2、网络143.2 小世界网络173.3 无标度网络19第四章 三种复杂网络模型上的信息路由鲁棒性仿真分析214.1 MATLAB软件简介214.2基于最短路径路由的级联故障模型224.3 随机网络的的信息路由鲁棒性仿真244.4小世界网络的信息路由鲁棒性仿真264.5无标度网络的信息路由鲁棒性仿真284.6 三种网络模型上结果的对比分析30第五章 总结31参考文献32谢 辞34复杂网络结构对信息路由鲁棒性的影响摘要：现在社会越来越依赖于许多大规模网络，如Internet、交通网、物流网等，在这些网络上输送或路由着与人类密切相关的的大量信息流。一个网络的路由鲁棒性的强弱无疑是人们比较关心的问题。研

3、究已表明，网络结构对其上的动力学行为有着重要影响，因此，越来越多的研究者基于典型的复杂网络模型对信息路由的鲁棒性展开研究。 本文首先概述了复杂网络上信息路由的鲁棒性研究现状。其次介绍了复杂网络的基本理论，如拓扑结构参数和典型的网络模型。然后，基于三种典型的复杂网络模型，包括WS小世界网络、BA无标度网络和ER随机网络，利用matlab仿真研究在最短路径路由策略下，网络由随机攻击和蓄意攻击而引发的级联故障行为，详细分析了网络结构对信息路由鲁棒性的影响。仿真结果表明，在随机攻击下，无标度网络的路由鲁棒性强于随机网络，在蓄意攻击下，则正好相反，而小世界网络的路由鲁棒性始终介于随机网络与无标度网络之间

4、，且重连概率对小世界网络的路由鲁棒性产生了影响，本研究为当前网络拓扑和路由的优化和重新设计提供参考。关键词：复杂网络;信息路由;鲁棒性;级联故障Effect Of Complex NetworkStructure OnInformationRouting RobustnessAbstract：Now the society has become more and more dependent on many large-scale networks, such as Internet, traffic network, logistics network, transportin the ne

5、twork or routing with a lot of information related to human flow. Anetwork routing robustness strength is concerned. Research has shown that，the network structure of the dynamic behavior of it is important,therefore, more and more researchers study the robustness of typical complex network models of

6、 information based routing.This paper outlines the complex networks and complex system, as well as the present situation of information routing robustness. Secondly,introduces the basic theory of complex networks, such as topological structure parameters and the typical network model. Then, three ki

7、nds oftypical complex network model based on small world networks, including WS, BA scale-free network and ER network, matlab simulation study onshortest path routing strategy use, cascading failure behavior of network by random attack and intentional attack caused, the influence of network structur

8、e on information routing robustness analysis detailed. The simulation results show that, in the random attack, scale-free network routing robustness to random networks, in deliberate attacks, is just the opposite, and routing robustness of small world network always between random networks and scale

9、-free networks, and rewiring probability will affact the small world network routing robustness. In this study,in order to optimize thenetwork topologyand routingandtoprovide the reference for the network design.Key words：Complex networks; Message routing; robustness; cascading failur第一章 绪论1.1 课题的研究

10、背景和意义现代社会越来越依赖很多的大规模网络，人们的生活和网络紧密相关，通过这些网络我们可以输送和人类有关的大量信息流。这些信息流从发生点经过网络里面边的承载输送和点的路由分配最终达到目的地，这是网络路由信息的一个完整过程。当然整个网络不可能是永久的安全可靠运行，在使用的过程中也会遇到故障，受到来自各方面的影响，例如自然灾害、人为的破坏等等。此时，网络的路由鲁棒性就会受到影响，整个网络里面的信息流会也许会因此而无法到达目的地，人们对网络路由鲁棒性强弱也非常的关系。整个网络科抽象为点和边，边代表在网络里面的传输介质，例如双绞线、光纤等，这些边承载了大量的信息流，为信息从一点到另一点路由提供条件；

11、点就代表网络里面的路由转发设备，例如交换机、路由器等，这些点利用路由算法来选择合适的边进行信息流的分发。当网络的边受到攻击时，这些边传输信息流的能力也许会下降降低传输能力，也许会失效失去输送信息流的能力。当这些故障发生在这些边上的时候，网络就会发生级联故障，由于一条边受到了影响，它输送信息流的能力和攻击前相比肯定是降低了，里面的信息流无法保证正确的传输到下一个点。因此，会对这些信息流进行重新路由，重新路由后，这些信息流到达了新的边，这些边的输送能力是固定的也许大也许小，当超过了自身的负载能力时就会发生和刚才失效的那些边一样，这样级联故障就进一步的扩大了。由局部到整体，也许会对整个网络造成无法衡

12、量的影响，导致整个网络的失效瘫痪。网络的安全性和可靠性受到影响，依赖于网络的人类因此会深受其影响。网络为我们的生活带来了极大的便利，为我们工作效率的提高也起到了很大帮助，与此同时也给我们带来了负面的影响，任何的东西总有双面性，我们追求完美的同时会尽量避开它不好的一面。在实际中就发生过类似的例子，美国的电网故障最先是由局部的故障引起的，随着时间的推移故障的进一步恶化，导致了整个电网的瘫痪，严重影响了国民的正常生活。还有因特网的故障，这些故障如果没有较好的抵抗能力或者发生后不在短时间内得到控制，那么整个网络就会由于这些故障的蔓延受到影响，使我们生活受到影响，这样一来我们不得不对网络的信息路由鲁棒性

13、投入很多精力去关注它，了解它的本质和规律。之前的研究者们着重研究了复杂网络上信息路由的效率等，而很少有人关注网络上信息路由的鲁棒性，随着社会的发展和需要，人们对信息路由鲁棒性这方面的要求也越来越高。人们渴望有所处在的这些网络有很高的安全性和可靠性，这样一来就使得研究者们对信息路由鲁棒性的热情投入。通过这些研究得出网络结构和其上的信息路由鲁棒性之间的相关性。这对于网络拓扑和路由的优化和重新设计，以提高网络的安全性和可靠性具有重要的理论意义和应用价值。1.2 复杂网络上信息路由的鲁棒性概述 目前人们的生活习惯已经离不开随时可以信息共享具有网络的环境，还有为网络提供条件的像电网、互联网的硬件设施、交

14、通网等等，在这样的网络里面是确实有物质存在来保证信息的传输。好比在互联网网络里面首先要有介质来满足信息流量的通过，其次，这些数据流量就通过这样的介质进行传输等等。我们把这样的的网络叫做网络负载。当然在网络里面进行传输的这些数据流量是随时变化着的。不仅如此，也会存在网络结构的变化比如网络受到有意的破坏或者是随机产生的一个故障，这样网络里面的节点就会受到相应的变化，数据流量也会随网络节点的变化而变化，之前预计的路径和流量分配就会随之改变这样每个点 和边的信息路由就会改变。一般情况下，一个网络里面的节点还有他们之间的路径的信息流量有最大值，在网络结构发生改变后，原来的信息流量分配大小会产生变化路由就

15、会发生改变，在某些节点和路径上可能就会有很少的流量通过，当然也有节点和路径上会接受很多的流量以至于超过了他们自身所能控制的能力。这样一来，负载变大的节点和路径就会变得特别拥塞甚至出现节点和链路的崩溃，网络的路由鲁棒性就变得糟糕。在网络里面一个小小的级联故障如果不及时处理通常情况下会带来更大范围的节点和链路崩溃，这些故障的造成会直接影响到基础网络设施的正常运行，给人们的经济生活带来很大的不便严重的时候会带来巨大的经济损失，给人们的正常生活造成了很大的不方便。由于这些问题的存在，级联故障的这种情况吸引了很多科学家的眼球。目前，在复杂的网络里面，研究级联故障的主要手段是用非线性动力学等理论的知识来进

16、行讨论，在研究中会采用随机故障和蓄意故障的的这两种方式来进行试验，网络里面的一个点超负荷的运行会导致信息路由进行重新分配，这样一来就造成了级联反应。我们把任意去掉的节点或链路或者我们的操作不当以及自然灾害等这一类不可以预测的叫做随机故障，把网络里面那些很关键重要的节点、链路有意的去掉，比如有意毁坏、物理攻击重要网络设施等叫做蓄意攻击，这两者情况都会对网络信息路由的鲁棒性造成一定影响。为了研究清楚节点的传输能力变化造成的级联影响，Motter先后几年里做了很多实验去进一步了解这个问题，他最近的实验结果表明，如果把节点的传输能力定义成以最短路径优先作为路由的策略，那么经过这个节点的信息流量就会发生

17、变化。这样的实验得出了这样一个结论，在蓄意攻击的前提下，节点传输能力如果不是平均的，那么级联的故障发生的概率就会更大。Crutcitti把网络的效率当做是一个参数，如果节点的传输能力已经超过所能承受的限度时，这个节点不被移除，让它继续保持拥塞的情况，那么计划会通过这个节点的数据被分别传输到其他的节点上。该实验证明了传输分布越是不平均化的网络结构，就算移除了传输能力较强的节点，这样仍然会对网络的效率造成影响，最终导致整个网络的级联故障。近年来对于链路传输能力造成的路由鲁棒性影响，很多研究者也做了相对应的实验。Wang对于那些不一样的网络发表了链路的传输力重分布的级联模型，对产生这样的级联故障所满

18、足的条件也做了详细的解答。以Qin为首的一群科学家对移除信息路由量最小的链路进行了实验，这样得出的结论符合了“木桶原理”等。在之前人们对网络级联故障的研究存在一定认知的局限性，把重点放在了基于来自不一样的攻击策略的网络上，这样去观察级联故障产生的原因和整个网络对级联故障的抵抗能力的情况。但是对这样的故障发生的过程里面网络故障的传播扩散所带来的更多影响的关注几乎为零，例如网络的生命周期等等。在21世纪之初，美国北部的电网的瘫痪对美国经济带来了巨大的经济损失，在这次事件的整个发生过程里面我们可以得到一些信息，这次事故先后出现了局部的故障发生，随后波及到邻近的电网，一旦达到一定规模就开始爆发，最终慢

19、慢扩散到整个电网。从这些经验里我们慢慢发现了问题，网络传输能力的改变的级联问题，得到它出现故障的最开始以及到结束的时候时间长度，整个过程会延续多久。在这个级联故障的整个过程里面，每个时间段又是体现了怎么样的特点。我们可以从很多方面去了解网络的运行状态，比如我们可以通过网络里面数据量大小的改变造成的级联问题，去了解互联网里面数据的分配情况，分析各种的参数，路由性能的非静态变化对整个网络的影响。根据网络这些反应出来的一些基本信息我们可以提前意识到网络存在的不正常因素。目前我们研究的重心是对节点和链路的随机和有意攻击等多种不同的情况下进行实验，在几种不同的网络里面进行仿真实验。1.3 课题的提出及主

20、要工作就现在而言我们对复杂网络的研究主要用到了三种方法。第一种，建立一种接近于研究的模型来满足对真实系统里面的宏观的微观生产机制。第二种，利用定义网络的特点来仿真出复杂网络的宏观本质。第三种，在研究他们拓扑上的一些非静态，针对那些不同结构他们之间发生的相互作用的特点。拓扑结构是研究这方面的基石，举个例子我们要模拟病毒在网络里面的传播途径，在我们使用的网络里进行研究是不实际的，我们只能在一个模拟的环境中进行。当然在这种情况下会对我们的实验带来一定的影响，所以要选择正确的拓扑结构是实验成果的重要前提。目前计算机网络受到威胁是无法避免的，网络受到的攻击方式也日益增加，比较保守一点的防护措施在一定程度

21、上增加了一些节点和一部分网络的可靠性。但是这远远不够应对目前网络安全的严峻形势，我们必须梳理网络整个架构，分析各种情况所产生的故障。在硬件方面我们要考虑设备的性能失效时带来的影响。路由鲁棒性的存在是网络处于一定的环境的一个自身特性的体现，如果不指定一个网络条件就去研究鲁棒性的效率是没有必要的。目前拥有的路由转发规则，想表达某个算法的效率很高，那么这样的一个算法必须是在指定的条件下才可以，仍具有以满足性能要求的方式正常传输数据的工作性能。鲁棒性研究的计算时，包含了一些参数变量，如一定的边的传输路由效率，在实验的某个区域选取一些样本，每个单位都路由一个数据流到下一跳看看整个实验对象失效的流量大小反

22、应了边是否处于路由状态，成功路由信息后的这些边占之前路由变得总数比，这样的一个比值就反应了网络的连通率，网络的连通率会影响到信息路由鲁棒性。虽然在我们生活的环境中，复杂网络到处都会存在，但是我们在获取他们研究数据的时候会受到一些限制，就很难得到真实的数据。好比，在因特网中，他具有开放性和异构性，并没有一个管理网络的机构，所以就没有他的统计数据。每个单位以不一样的方式接入，随时会有单位的接入和退出。要得到因特网的拓扑结构，是很难的，因为他一直在变化。不仅如此，每个网络有自己的特性，会有独特的变化。目前没有任何一种模拟能够完全符合在实际生活中我们所面对的真实网络的网络拓扑结构。现在很多的研究都从他

23、们的共性入手，尝试揭示复杂网络的一般规律。随机网络、无标度网络和小世界网络就成为了最重要的复杂网络模型，因为他们是研究中很有代表性的。论文从以下三个大方向展开了研究：1）阐述复杂网络的基本理论，主要包括复杂网络的拓扑参数，基本的网络模型及其性质。2）利用Matlab模拟复杂网络中的三种网络模型的信息路由鲁棒性。3）分析网络拓扑结构对信息路由鲁棒性的影响。 第二章 复杂网络的拓扑结构参数2.1图的基本概念用图的观念对网络结构进行描述，是指有三个参数(,)，V不是空集我们把它叫做顶点集，叫做所有边的集合，是指从到集合里面有序对或者是无序对簇VxV的关系函数，我们把叫做关联函数。网络里的顶点用表示边

24、用表示，用函数表示了点和边的之间的联系。里面包含的系数都是有序对，这样三种函数组成的图我们叫做有向图，我们同公式这样表示(),)。如果里面的参数都是无序的，那么这样生成的网络就叫做无向图，我们用公式这样表示 (),)。 一般情况下，一个图的顶点可以用平面的一个点进行描述，网络的一条边可以在平面上用一条线段来描述，就像下面的图所描绘的。左边的代表顶点的平面点的位置具有随机性，在一个图里可以体现出很多种不同的图示，右边的图又是另外一种体现方式 图2.1 边的表示方法不管是用计算机还是数学的方式对图形进行描绘，都需要一种具体的方法才能够表现出来。不一样的系统描述出来的特性具有不一样的特点，就像有些图

25、的边所占的数量偏少，密度小；另外一些就相反，密度偏大。不同的图形具有不同的表现方法，我们再次用两种办法对图进行数学描述分别叫做邻接矩阵和关联矩阵。下图代表邻接矩阵，里面的vvvv代表节点的序号 a代表顶点和顶点之间边的连接数目，加入节点之间不可以进行重连那么它的取值就是0或者1。假如该网络是无向图那么A(G)=A(G) 。邻接矩阵所需要的存储空间复杂度可以表示为()，为节点数量。这样的矩阵使用与密度较大的图，对比较稀疏的图形则不适合进行描述。 （2-1） A(G)= （2-2）下图表示了关联矩阵，vvvv代表的是点的序号eeee代表图形里面边的序列。在节点的量在固定不变的情况下，关联矩阵所占用

26、的存储大小和边的数量又关联，这样空间的复杂系数为，N表示节点的总数，代表边的数目。这样的矩阵用来表示系数矩阵更合适。M(G)= （2-3）2.2网络的聚类系数在你所有的朋友里面也许有两个朋友他们之间也是相互认识的，我们把这样网络这个性质叫做聚类特性。我们可以用一个系数来对这个特性进行描述，用它来描述网络的密集程度，每个节点和他相邻的点紧密系数我用表示。在网络里面的某点，把用来表示节点的度，理解为节点 有个邻居，这个邻居之间最多存在条边。若其中实际存在的边的数目为，则节点的聚类系数被定义为和的比值： （2-4） 同时聚集系数也表示它和周围的网络的连通性。网络的聚类系数我们用表示，它代表的就是网络

27、中全部节点的聚类系数的平均值： （2-5）和聚类系数接近但是又存在一定差别的是连接率，这个可以同来表示网络里面的节点的连接密度。设定无向无权网包含了点的数量为N，边的数量为。加入有个点里面任意的两个节点都只有一条边进行了连接，那么边的数量就是C C= （2-6）当网络中点之间的连接密度越大，那么整个网络的连通性就越完善如下图 图2.2聚类系数和网络连通性的联系(a) ,(b) ，(c) 当聚类系数等于1的时候，网络极速一个完全的图。当随机网络的N值比较偏大的时侯，系数等于0，没有一条边的连接。聚类系数是网络复杂程度衡量的关键参数，在我们生活的环境中聚类系数的值通常处在大于0和小于1之间。下面这

28、个表格描述了相同大小的随机网络和Internet平均聚类系数的多组数据比较。从下面的表可以得出结论，随机网络的比较小，整个网络所包含的节点都没连成簇；与之进行对比的Internet就相反。 表2.1：不同网络的聚类系数DataNo.of ASsNo.of EdgesC of InternetC of random networkSept.995764111730.38860.0023Mar.007012149850.44170.0019Sept.008613183460.45310.002Mar.0110424224880.46210.0016Sept.0111867253630.46730.

29、0015Jan.0212709273840.45970.00142.3网络的度分布1)节点度图论中节点的用度表示，代表节点所有连接的边的数目。表面上，度值大的节点具有貌似有更重要的功能，第个节点的度用下面的公式表示： （2-7）网络的平均度是指所有的点的度的平均值我们用代表，并可以根据公式来计算 （2-8）网络的平均度代表了整个网络的密集程度越大的网络它的密度越大。2)节点度分布度反应了节点的性质，也反应了网络某个单位的特点，只能从细节反应网络不能够全面的对网络进行描述。节点度的分布可以用函数来进行刻画，我们理解为任意的节点有条边连接的概率。度的分布属于正态分布，随机网络的节点如果限定了那么它

30、也属于正态分布。 （2-9）图2.3 (a)正态分布（b）幂率分布其中为随机网中节点度值的平均值，正态的峰值是，两边逐渐的缓慢下降，比平均值高出很多或者小于很多的节点几乎不存在，我们叫做随大流网络。在过去的几十年里，科学家们把网络都当做是随机网络，随机图论就是为了方便研究数据网络而建立的，最近的研究表明这样是错误的：我们生活的网络里面大部分都是不遵循正态分布是，他们的节点的度的分布更接近于幂率分布 （2-10）当大于2小于3的时候，幂律分布要比指数型的网络要更为缓和一些，所以节点可以有很大的度。遵循了幂律分布的网络，它们几点的度值大小相差很多，存在有极大或者极小的。少数节点的度值很大，但是这样

31、的节点数量很少，在整个网络咯具有很关键作用，被看做是中心节点，连接了绝大部分的节点；很多的节点度值很小，却只连接了一个或者几个节点。在因特网里面度值小于3的占到整个网络的80%。我们得出这样的结论：幂指数越大，异质性就越差；相反，幂指数越小异质性就越是突出。 我们把遵循幂律分布的网络叫做无标度网络，和随机网络截然不同，这也是无标度网络的本质特点。假如在英特网的度值很大的节点上进行攻击，那么这样的攻击会造成整个网络的崩溃，所以要保证这些节点的鲁棒性就非常的重要了。2.4 实际中的网络拓扑大家对www和internet都比较熟悉他们是令我们现在关注的，在过去的短短几十年发展势如破竹，是人们现在信息

32、生活不可以缺少的。他们改变了人们传统的信息发送与接收，对各个领域都有重大影响。2.4.1 InternetInternet是由计算机、路由器和其他的网络设备组成，这些硬件为信息传输提供了条件，internet研究是在AS和ROUTER两个层面进行的图2-7所示。在路由层，我们把每个路由器当做是一个单位，不同路由器之间的连接线路当成边。在AS中我们把很多的路由器和计算机工作机看做一个单位，只要他们间有物理链路我们就可以看做他们的一条边。Topology Generator的设计是因为科学家们要对internet特性进行研究，但是研究者们对internet缺乏很多基本的理解，所以实验结果总是不太满

33、意。在1999年，Faloutsos等对Internet的AS和ROUTER的度分布上做了研究，发现了度分布满足幂律分布 P ( k ) k，并在之前的的两年里计算出了度数在 =2.15和 =2.2之间。2000年，Govindan和Tangmunarunkit对AS上的internet做了更进一步的研究求得 =2.3，如图2.2所示。Internet拓扑BA的发现对究者们开发新的模拟工具带来巨大的动力。Yook和Pastor-Satorras等人对自治系统层进行了研究，研究结果表明了英特网的集聚系数在0.18到0.3中间变化，相同条件下ER网络集聚系数为randC0.001。 图2.4英特网

34、的第三层和AS层 图2.5第三层在英特网上的度的分布2.4.2 wwwWWW是我们可以获得网络拓扑的最大一个，节点是网页，他们的边就是超链接，如图 29。边有方向性，WWW是有向网络具有向量的特性，目前为止该网络的节点早已经大于80亿了。它的度分布大概就是由出度P( k )和入度P( k )两个部分组成的，P( k )表示网页具有K个对外发出连接的概率，Pin ( k )表示发出K连接都连接到同一个网页的几率大小。他们的幂律分布公式可以用下面的表示 ：P( k ) k, P( k )k （2-11）有人利用软件搜集了很多网页链接数据用来实验，很大的数据量表明万维网的出入度指数：=2.38和=2

35、.1。Albert等人研究了WWW的一个子集，即nd.edu域名下的325, 729个节点，得出=2.45和=2.1。2000年，又有人利用其他的一些工具收集了万维网上数以亿计的网页和庞大的连接数据，再次得到了新的数据=2.72和=2.1，如图23所示。一个令人注意的问题是，他们在研究这个时花了接近两年的时间，一个很实际的问题就是万维网的数据量也增大了接近5倍，不过研究结果表明入度指数是毫无变化的。 图2.6 万维网的出入度万维网的边具有有向性，我们不能直接使用公式（2-11）去计算它的集聚系数，我们可以把有向转变无向，让单向变成双向。Lada Adamic研究了深入到了网址层次的万维网，把每

36、个网址作为一个节点，只要存在那么一个指向另一个，我们就认为是相连的。为此他利用了接近15万个网址以及他们的数据，得到网络集聚系数=0.1078。但是包含有一样节点数和平均值的ER他们的系数却为C =0.00023。虽然WWW里面节点数很大，但是它还是体现了小世界的特性。利用robot这个软件能够在万维网里面进行路由，统计里面的连接，根据他的边顺藤摸瓜的找到它的出发点。利用这种方法搜索了接近33万个网页，得到结论研究的这些网络他们的平均路径长度11.2。得到了一个公式L=0.35+2.06 log(N) （2-12）2.4.3 其他网络阅读概述我们生活的世界中也有其他不同类型的网络，像人际关系网

37、、食物链关系网、电力系统网、交通运输等很多不同类型的网络。很大部分的复杂网络都体现了小世界效应和无标度效应的特点，下图2.2和表2.3所示，不仅如此，在实际生活里的无标度网络，他们所拥有的度指数基本是大于2小于3的的区间。每个不同的网络，给了很多不同的参数例如路由器数、他们连接线的平均度值、网络连接线平均路径长度和集聚系数。利用之前的作为对比，我们利用了和物理网络拥有一样节点以及平均度值的ER网络L和C。表2.2几种网络的拓扑数据 下面是几个模拟无标度网络的度指数。指出复杂网络结构的路由器个数和连接线的平均度值。表2.3几种网络在实际中的无标度指数：第三章 复杂网络模型 上面那章介绍了 网络的

38、拓扑特点和路由的基本原则，这个是我们进行研究的前提。想要更深层次研究和处理好这些模型和我们的实际更加的接近那么久要寻找更加好的方法。就当前来说，有学者已经将复杂网络模型规划为很多不同的网络，仍然有不少的学者认为复杂网络不含有随机和规则这两种网络。3.1 随机网络 a) 全局耦合网络 b) 最近邻耦合网络图3.1 两种规则网络在1930年左右，研究者们发现真实系统他们子系统单元之间的关系可以用某些规则的结构代表。这样被称为规则的网络模型。如图3.1a。所以在有一样路由器数的复杂网络结构里面，有值最小的路由路径和值最大。一个有个点的全局耦合网络有条边，但是我们在实际中遇到的很多大型实际网络都没有那

39、么密集，他们的连接链路数量最多就是。有个稀疏模型是经过很多研究而得到的实验结果，任何一个节点会连接与他相邻的点，如图3.1b。最近邻耦合网络由个路由单位他们围成了一个圆形满足周期边界的基本因素，任何的路由单位和他相邻的个邻节点连接。在此值是一个很大的偶数。N个节点组成一个圆形，任何一个节点都和他相邻连接的点，这样的一个网络的聚类系数可以用公式表示为： （3-1）因此，如此的网络的高密度的网络。但是，这样并不是小世界网络，针对于这个不会变化的值，这个网络的均值路由连接线长度为： （3-2）规则网络每个单位包含的连接数量和方式都是一样的。和规则网络对立的是ER网络，数学家Edros和Renyi在2

40、0世纪60年代制作了一个典型的ER模型，他们指出：设想一个网络里面有N个单位，任何两个节点连接的概率为。这样就有个单位，可以估算出接近具有条边模型图。随机图演化过程如图3.2 图3.2 随机图的演化示意图随机图理论的的目标是为了找出到底是哪样的连接方法才会得到概率下，让图产生一种特定的性质。ER的的实验我们发现了如果在给定的概率下这样的条件，那么很多图形都含有一些相同的性质，或者是相反的结果都不含有。随机网络的一些特点我们可以总结出来有一下这么几点：(1)当时，连接线就是0，网络里面的单位都是独立存在的毫无关系可言=0，； (2)当时，边数为，网络所有的单位都有联系相互之间都是直连到网络中任何

41、节点的路径都是1；(3)当(一般情况)时，网络连接数在零和之间，网络中节点度的平均值，度分布为： （3-3）当占的比例很大，每条连接线出现或者消失都互不影响，很多路由器单位拥有的度一致，在这个时候ER模型的度分布可以用以下公式来表示： （3-4）图3.3随机网络的度度分布这样的分布在度的均值出有峰值，两侧呈指数递减，所以该网络也被称作指数网络，因为的值随增长很慢，这么一来虽然不小的网络结构仍然有不大的均值路径长度。3.2 小世界网络模型的构造算法如下：(l)从规则网络开始：设想有个比较近的邻耦合网络含有个单位，所有的单位组成了一个圆圈，任何节点和他相邻的两个单位相互连接，非奇数。想要获得一个密

42、度不大实际上又时刻都是连通状态的网络，可以想到。(2)随机化重连：任意的从网络里面选出节点，一条边上的一个节点不变，连接线的那一头的节点再次重新选取。 图3.4 WS模型里面边的随机重连过程在图3.4中，当=0的时候是完全规则网络的代表，=1对代表了完全随机网络，我们可以改变的值范围就可以掌控从网络处于不同状态的变化。如图3.4所示。图 3.5 WS小世界模型的聚类系数和平均路径长度随重连概率的变化关系上面的算法我们可以知道和的参数特性，有了这两个特点我们就可以把这样看做是重连的结果，图3.4代表了网络的和会跟着重连概率的改变而改变。通过实验还了解到，如果概率P值比较小，他们的平均路径反而变小

43、更为突出。对于的情况，存在一个不小的片区，在此拥有不小的聚类系数和数值不大的最佳连接，即的区域为小世界现象存在的区域。 3.3 无标度网络在研究过程中为了阐述幂律分布的产生原理，有人提出了一个无尺度网络模型，经过一系列的发展演变成为了当今使用的BA模型。现在人们了解到许多以前的模型基本上没有牵扯到一些重要的因素：(1)增长特性：网络在不停扩大，连接也在快速增长，而ER模型是基于几点数目保持不变的条件下。(2)优先连接特性：新加入的单位更容易加入连接数偏大的点。把网络的增长特点和连接方法作为参考，无尺度网络模型的转发规则我们可以用下面的表示：1)增长：选取含有个单位的网络作为对象，只要有新成员加

44、入，然后连接到个早就有的单位上，当。2)优先连接：新加入的单位和一个早就出现的单位相连接的概率与节点的所代表的、路由器信息节点的度满足这样的计算公式：= （3-5）图3.6 无标度网络的度分布经过个经过，这样产生的另一个网络拥有个节点和条边，实验模拟表明这个刚实验的网络的度分布满足，并且。图3.5表明了当这个值BA网络的变化经历。图3.7 BA无尺度网络的演化顶点的度为幂律分布。最近的研究表明，很多真实网络与BA网络有较为相似的特性，比如英特网，电子邮件等等。这说明了BA模型和真实网路更接近了。这样的使用就会让BA网络模型和真实网络的结果有出入当然是正常的。但是在外面实际中的复杂网络却是不一样

45、的，绝大部分都是在2到4之间。所以基于BA的模型研究者们做了很多样式的散发设计。有一部分是经过改变BA模型的优先连接方法得到的，这样一来就更不同了。不管是BA模型还是之前的，没有任何一个是大家都觉得符合条件的，所以这样的结果并不是很理想的。没有一个比较理想比较完美的框架，那么得到的结果始终会偏离真实的结果，在这一方面科学家们正在深入研究找到最适合的模型来解决现在的问题，理想的模型会将更加接近真实的答案，更合理的揭示复杂网络里面信息的传输状况。第四章 三种复杂网络模型上的信息路由鲁棒性仿真分析在这个章节里我们将会利用matlab来实现小世界、无标度以及随机网络的信息路由鲁棒性分析，分析他们在不同攻击下鲁棒性的强弱。4.1 MATLAB软件简介一个用来模拟复杂网络的软件成为了我们研究这门学科的必备条件。现在国内外已经开发了很多用来模拟的软件例如pajek，network