基于复杂网络的因特网抗毁性分析毕业设计(论文)

《基于复杂网络的因特网抗毁性分析毕业设计(论文)》由会员分享，可在线阅读，更多相关《基于复杂网络的因特网抗毁性分析毕业设计(论文)（40页珍藏版）》请在装配图网上搜索。

1、南华大学计算机科学与技术学院毕业设计（论文）计算机科学与技术学院毕业设计(论文)论文题目基于复杂网络的因特网抗毁性分析 指导教师职 称博士讲师学生姓名学 号专 业网络工程班 级系 主 任院 长起止时间2013年10月11日至2014年5月23日2014年5月23日南华大学计算机科学与技术学院毕业设计（论文） 目 录 摘 要iAbstractii第一章 绪论11.1研究背景及意义11.2本文的主要工作31.3本文的组织结构3第二章 复杂网络的背景知识42.1从图论到复杂网络42.2复杂网络的结构参数52.3复杂网络的经典模型7第三章 复杂网络抗毁性113.1网络抗毁性的定义113.2网络抗毁性分

2、析12 3.2.1抗毁性度量指标12 3.2.2实证分析与仿真分析13第四章 因特网抗毁性分析164.1因特网的拓扑结构及加权网络介绍164.2考虑信息条件下因特网的加权网络基于节点的抗毁性分析19 4.2.1因特网抗毁性模型描述19 4.2.2局部信息下的抗毁性仿真结果20 4.2.3全局信息下的抗毁性仿真结果234.3考虑信息条件下因特网的加权网络基于边的抗毁性分析26 4.3.1抗毁性模型26 4.3.2抗毁性仿真结果26第五章 总结32参考文献33谢 辞35基于复杂网络的因特网抗毁性分析摘要：自从上世纪末科学家们发现复杂网络的小世界及无标度结构特性以来，复杂网络就一直是最重要的多学科交

3、叉研究领域之一。因特网作为现实世界中重要的复杂网络之一，其与安全性和可靠性相关的结构抗毁性一直是受关注的焦点。本篇文章首先阐明了复杂网络的基础理论，主要包括图论、复杂网络的结构参数、经典复杂网络拓扑模型。其次概述了复杂网络抗毁性研究现状。然后利用仿真软件Matlab，基于经典的加权无标度网络模型对因特网抗毁性开展仿真研究。本实验选定网络中较为常用的测度鲁棒性及网络效率，来评测网络的抗毁性。研究关注于网络在不同的信息条件和攻击方式下的抗毁性表现。从不同角度对因特网抗毁性进行了仿真，有基于节点的抗毁性仿真和基于边的抗毁性仿真。其中，在基于节点的抗毁性仿真中，研究了局部信息条件下遭遇ID攻击（对初始

4、网络按节点的度大小顺序来移除节点）时网络的抗毁性，以及全局信息条件下遭遇IB攻击（对初始网络按照节点的介数大小顺序来移除节点）和RB攻击（每次移除的节点是当前网络中节点或边介数最大的节点）时网络的抗毁性；在基于边的抗毁性仿真中，研究了不同信息获取情况下网络的抗毁性。不同信息条件下基于节点的因特网抗毁性仿真结果表明：在基于局部拓扑信息的各种攻击策略下，权重系数越大，节点移除对于网络效率和连通性的影响越小，网络的抗毁性越强。相比于基于局部拓扑信息的攻击策略，基于全局信息的攻击策略下，网络应对节点移除的鲁棒性要更弱。而不同信息条件下基于边的因特网抗毁性仿真结果表明：当网络信息获取为随机获取时，网络的

5、抗毁性取决于网络信息量的获取程度。其中，当网络的信息获取为零时，网络具有较强的抗毁性。在网络信息为优先获取情况下，只需要获取少量重要的边信息就会导致网络变得异常脆弱。这些研究结果为从信息角度给出因特网更合理有效的保护措施提供了理论依据。关键词：复杂网络；因特网；加权网络；小世界；抗毁性 Invulnerability Based On The Complexity Of The Internet NetworkAbstract：Since the last century that scientists have found that the characteristics of the sm

6、all-world and scale-free structure of complex networks, complex networks has been one of the most important multidisciplinary research field. Internet as one of the important real-world complex networks, and its safety and reliability associated with the structure of invulnerability has been the foc

7、us of attention.This article first clarifies the basic theory of complex networks, including graph theory, the structural parameters of complex networks, classical complex network topology model. Followed by an overview of the complex network of anti-status quo survivability research. Then use Matla

8、b, classic weighted scale-free network model based on Internet invulnerability to carry out simulation studies. In this study, selected the more commonly used measure of the network - network efficiency and robustness to evaluating network survivability. Research focuses on network survivability per

9、formance under different conditions and attacks of the information. From a different perspective on the Internet invulnerability of the simulation, there is a node invulnerability simulation and survivability simulation based on the edge of the anti-Based. Among them, the survivability simulation ba

10、sed on nodes, studied under attack when confronted ID information under local conditions (initial node of the network according to the order to remove the node) network survivability, as well as the conditions encountered IB global information attack (the initial referral network in accordance with

11、the number of nodes in the order to remove the node) and RB attacks (each node in the network to remove the maximum number of nodes or edges mediated current node) network of invulnerability; based side survivability simulation to study the different access to information under the network survivabi

12、lity. Under different conditions of node-based Internet Information invulnerability simulation results show that: in a variety of attack strategies based on local topology information, the greater the weighting factor, remove the node connectivity for network efficiency and the impact of the smaller

13、 network survivability the stronger sex. Compared to the attack strategy based on local topology information, under attack strategy based on global information network robustness to cope with weaker nodes removed. But under different conditions based on the information side of the Internet invulnera

14、bility simulation results show that: when the network is random access to information access, the network survivability depends on the extent of the network to get the amount of information. Wherein when the information network to get to zero, the network has a strong invulnerability. Priority acces

15、s to network information case, you only need to get a small amount of side information will lead to important network tenuous. The results of these studies give a more reasonable and effective measures to protect the Internet from an information point of view provides a theoretical basis.Key words:

16、complex networks; internet; weighted network; small world; invulnerabilityii第一章 绪论1.1研究背景及意义 自从上世纪九十年代以来，由于总体经济的高速发展，人们逐渐进入了一个以因特网为代表的网络时代，并且在生活中的各个领域因特网都广为普及，与我们的日常生活紧密相关。纵观整个人类的社会生活，无论是政治、经济、教育亦或是其他生活的方方面面，因特网的作用日益突出。离开了因特网，人们会感到无所适从。例如，人们平时搜集信息、网上购物、存储数据等等，都与因特网有关。还有对于银行、政府等重要机构而言，因特网的重要性更是不言而喻。一

17、旦有重要数据流失或泄露将会造成不能挽回的损失。所以，如何加强因特网的安全性，当受到不法分子的恶意攻击时，会给因特网带来何种影响，如何尽量减少恶意进攻给网络带来的不良后果，怎样行之有效的来对因特网进行保护以维持其正常的服务运转等，这一系列问题正日益成为研究者研究的重点。 因特网从出现到如今的快速发展，整个过程十分迅猛。它源于最早的有小型计算机连接而成的实验网络，经过多年的演变发展，成为了今天十分成熟的大型高效网络。而人们对于因特网的研究自其诞生之日起就从未停止并且深入研究的的欲望愈发强烈。早些时候，人们 对于因特网的研究都是停留在它的体系结构、网络协议以及网络服务等方面。而后，随着社会的不断发展

18、，信息技术也在飞速猛进，人们对于因特网的依赖越来越强，因特网的重要性日益出显现。这就使得人们开始将目光更多的转向因特网的结构建模、网络服务的安全性及可靠性等方面。而近些年来，人们在复杂科学及复杂网络领域取得了一系列瞩目的研究成果。而随着人们发现因特网其实就是现实生活中最为常见的复杂网络之一，就开始从复杂性和复杂网络角度对因特网开始了研究工作。 复杂网络遍布在生活各处，从因特网到万维网，从细胞神经网络到蛋白质相互作用网络，从城市公路交通网到航空路线图等。并且人们对于复杂网络的探究已经逐渐进入数理和工程科学范畴当中，在这个以信息为主导的年代进一步深入探索复杂网络的各种特性及功能，已然在科学界演变成

19、为了一个极富挑战性的课题，有的研究者甚至将其作为网络的新科学来进行钻研。人们对于复杂网络的研究最早是建立在图论的基础上的，即使用较为简易的规则网络来做相关的分析。然而受到实验条件的制约，加之缺乏实验数据和一定的对于数据统计分析能力，人们并不了解所研究的复杂网络的具体拓扑信息。后来，由于计算机领域相关技术的继续发展，使得人们可以收集和研究构造庞大的复杂系统的数据，人们开始了对复杂网络的更为深入地研究。随着网络的不断进步与发展，其重要性也日益突出，越来越多的研究人员开始投身于对网络的可靠性的研究当中来。“鲁棒而脆弱”是复杂网络中最重要但又最基本的特性之一。在对于我们的生产和生活都至关重要的因特网上

20、，每天都上演着多种多样的随机故障，并会不定时的遭受不知名的黑客的恶意攻击以及病毒的侵扰。因此，怎样对实际复杂系统的脆弱性和鲁棒性进行较为系统地大范围地研究，成为了时下对于复杂网络的研究中最重要的问题之一。脆弱性和稳健型是无标度网络的一个双重特征，这就使得病毒或黑客只需要破坏少数核心节点便可以彻底击垮整个的网络系统，因而，越来越多的科研机构开始关注复杂网络的抗毁性问题。此外，对于生活中无所不在的各种复杂网络，无论是通信、电力、物流或是金融等等，深入研究整个复杂网络的复杂性以及相关规律，都会对人们的生活带来极大的影响。除去一些处于核心置且数量众多的关键节点以外，网络中还不乏一些容易被人忽略但同时对

21、整个网络系统性能有着决定性影响的节点。如果这类节点出现差错，就很容易引起级联失效，进而致使网络出现大范围的障碍问题，严重时还会致使网络系统整体陷入瘫痪状态从而引起无法弥补的亏损。而因特网作为生活中必不可少的复杂网络之一，其抗毁性研究也越来越重要。所以，研究和探索因特网的抗毁性具有巨大的理论意义和现实意义。主要有： (1)基于复杂网络基本理论对因特网的拓扑结构进行分析可以对网中的核心节点进行精准的定位，已实现对其的有效管理从而从拓扑结构上优化因网。 (2)在实际的许多网络中，破坏一个或少数几个关键节点可能会引起级联失效严重时甚至会导致整个网络崩溃。这种网络中的相继故障原理使得提高了对于因特网故障

22、的重视，对于预防因特网遭遇外界攻击破坏以及阻止在网络遭到破坏后受到更大的损失都具有十分重要的现实意义。(3)研究分析因特网的抗毁性，对于更加合理地规划构建因特网、科学地制定管理因特网的方法策略、更为高效的激发因特网的信息服务能力、更大程度上提高网络的安全性以及可靠性等方面都具有重要的理论意义和现实意义。 1.2本文的主要工作结合已有的研究成果，本文主要从以下几方面对研究因特网的抗毁性展开了工作： (1)系统介绍复杂网络理论的基础知识（主要包括复杂网络的结构度量、经典拓扑模型及其性质、结构抗毁性）；(2)介绍已提出的经典因特网拓扑模型、攻击模型及抗毁性测度指标；(3)介绍复杂网络的抗毁性及已有的

23、抗毁性仿真与实证分析；(4)利用Matlab仿真工具，基于经典的模型网络对不同信息条件下的加权复杂网络抗毁性进行仿真分析，主要有考虑信息条件的加权因特网基于节点的抗毁性分析、考虑信息条件的加权因特网基于边的抗毁性分析、考虑信息条件的加权因特网基于节点的抗毁性分析、考虑成本和性能的加权因特网抗毁性分析。1.3本文的组织结构本文后续部分内容如下：第二章 ，复杂网络背景知识。首先介复杂网络的相关基础知识。其中重点介绍了因特网的三个典型模型：随机图模型，小世界模型，BA无标度模型。第三章 ，复杂网络抗毁性。重点说明网络抗毁性的定义以及之前人们对于研究网络抗毁性所做的仿真分析和实证分析。第四章 ，因特网

24、抗毁性分析。首先，简单介绍因特网拓扑结构和加权网络。之后从三个角度对因疼的抗毁性进行仿真，分别是考虑信息条件的加权因特网基于节点的抗毁性分析，考虑信息条件的加权因特网基于边的抗毁性分析以及考虑成本与性能的加权因特网抗毁性分析。并且得出在相对应的条件下，因特网的抗毁性随着拓扑参数的变化会有怎样的变化。第五章，总结。对本文所研究的内容进行总结。第二章 复杂网络的背景知识2.1从图论到复杂网络在产生图论理论之后，又有人提出了随机图理论。在之后的内容中将为大家 详细介绍ER模型以及其他的一些复杂网络的模型。与其他的数学家相同，随机图论的提出者Erdos研究的也是基于经典图论的网络模型，而随着一系列复杂

25、网络如万维网等的出现，一大批研究者开始思考传统网络模型以外的问题，像诸如互联网之类的复杂网络，它们的网络结构会是什么样子的呢？在对社会网络进行了近半个世纪的研究后，人们取得了显著地成果。但是对于复杂网络方面的研究，还要追溯到1998年6月。美国康奈尔大学的博士生导师Steven H.Strogat和其学生Duncan J.Watts联合发表了一篇论文：Collective dynamics ofsmall worldnetworks，在这片文章中首次提出了小世界模型（WS模型），该模型从规则网络出发，以概率（重连概率）将每条边断开并重新连接到网络上的其他节点，如果改变的大小，网络将会发生变化，

26、由规则网络（）向复杂网络（在0.001到0.1之间）变化，最后会向着随机网络（）变化。1990年10月15日，由美国圣母大学教授A.L.Barabasi与他的学生R.Albert联合发表了一篇论文Emergence of Scaling in Random Networks.这篇论文指出了复杂网络中的无标度性质，并提出了无标度模型（BA模型），该模型的度分布符合幂律分布。他们指出了实际网络中的两个重要特性：网络的规模总是不断在增长的、新加入到网路中的节点比较倾向于连接到度大的节点。 以上的两篇文章都提出了较为简单易懂的模型和严格的数学推导来给我们展示复杂网络的生成机制，同时阐述了复杂网路的基本

27、特征，这两篇论文的发表标志着对于复杂网络的研究从此走进了一个全新的时代。随着科学时代的发展，复杂网络理论已逐渐渗透到诸多领域，如物理、生物、社会等研究领域。对于现实网络而言，研究复杂网络对于研究其稳定性、容错性和抗攻击能力等，都具有决定性意义。2.2复杂网络的结构参数复杂网络是涉及到很多交叉学科的的一门新科学，近几年来吸引着越来越多的来自各领域的研究者，主要有社会学、生物学、数学、物理学等学科。我们日常比较熟悉的领域应该莫过于生物学了。接下来先从人们比较熟悉的生物学角度入手，来说明复杂网络的某些基本特征。众所周知，生物系统之间的相互作用错综复杂，所以用传统的方法进行研究时遇到了瓶颈，但是随着复

28、杂网络理论的发展，研究者的探索手段也在不断进化逐渐产生了许多新的想法，这种头脑风暴就使得其他领域的一些专家开始跨界在生物领域发展。这期间，也有许多重要的研究成果问世。如下图2.1和图2.2,这是两张较为典型的生物网络拓扑图。 图2.1酵母蛋白质相互作用网络 图2.2 转录调节网络(1)度和度分布网络节点的度（或称连接度）是最基本的一个网络测度，节点度反应的是一个节点所具有的邻居数。基本上所有的网络拓扑结构都是主要按照其节点度分布来进行分类的。 (2.1) 网络的平均度指的是全部节点度的平均值，记为， (2.2) 度是网络节点的属性，反映的是网络中个体的属性，属于微观层面，不能反映整体特性，可以

29、通过微观量的分布来研究宏观特性，由此引出度分布。网络中节点的度分布用分布函数来表示,其含义为一个任意选择的节点恰好有条边的概率,也等于网络中度数为的节点的个数占网络节点总个数的比值。(2)网络的聚类系数在实际系统中，节点往往会显示出集群倾向，此时网络的特性可以用聚类系数来进行量化，集聚类特性这一拓扑测度可以反映出网络上的某一节点与其邻居节点之间的连接程度。节点i的聚类系数的定义如下： (2.3) 表示节点与个邻居节点之间相互关联的链路数目。所以，平均聚类系数可以定义为： (2.4) (3)网络的平均路径长度在大部分的网络中，随意2个节点间可能不单单连着1条通路，而最短的那一个通路的长度是一个非

30、常有用的测度。平均路径长度的定义如下，其中，表示最短路径长度，和表示任意两个节点： (2.5) (4)介数节点的度虽然能够在一定程度上反映一个节点的重要性，但是两个度相同的节点其重要性在实际网络中的差别可能会很大，例如一个节点的度很小，但是它是网络中的一个割点，删除它以后会将网络分割成不连通的两部分，因此这个度很小的节点在网络中的作用十分关键。另外因特网中节点之间的流量传输主要依赖于最短路径。所以提出了介数之一概念来反映节点或边的重要程度。节点u的介数定义为网络中所有的最短路径之中，经过u的数量所占的比例，它反映了节点u在整个网络中的影响力。记之间的最短路径的集合为。则节点u的介数定义为： (

31、2.6) 2.3复杂网络的经典模型(1)随机网络 最早的时候由于受到实际研究条件的制约，人们的研究方向集中在规则网络。然而随着探索的不断深入，构造较为随意的随机图开始受到科学家的喜爱，这种网络图模型能够更为简洁明了地实现复杂网络的模拟。在那个年代，很多研究者都提出了自己独有的模型，而这些模型中最为突出的要数Erods和Renyi所建立的随机图模型，后人简称为ER模型。根据随机图模型（ER模型），以个节点开始以概率连接各节点，创建出约个随机分布的链路。网络中度分布的均值为,在平均度固定的情形下，当N很大时，就会变得很小。所以也将ER随机图称作泊松随机图。如下图所示：黑色圆点表明的是时的度分布，而

32、实线部分则表示的是与其相似的泊松分布。同时该图还表明大多数的节点有着近似相同数目的链路。 （泊松分布函数） (2.7) 图2.3 ER随机图的度分布与泊松分布的比较随机图的连通性有两种极端情况：时对应N个孤立的节点；时对应全耦合网络。直观上看来，连边概率增加则所生成的随机图的变数也会随着增加，网络的连通性也就越好。下图给出了不同的值下所生成的随机图的例子。粗略地算一下，若，则每次生成的ER随机图会有边数大约为 (2.8) 图2.4 不同连接概率的随机图实例(2)小世界网络小世界模型(WS)是由Watts和Strogatz(WS)建立的，描述了一个局部有序的系统是如何转化成为随机网络的。小世界模

33、型是从包含N个节点的一维网络开始的，网络中的节点和距离它最近和以及次近的邻点连在一起，每个边再根据概率p从新进行连接起来。并且以节点和节点间没有重复的边并且不会自行成环为约束条件。WS模型由一个规则网络经过一些演变而成的，经过逐步地一边接一边的重新连接，直到演化为随机网络。如下图：当时，对应的是规则网络图。两节点的平均距离与节点数目N之间是成线性相关的，当N增加后也跟着变大，同时集群系数也会跟着变大；当时，对应的是随机图，此时与N成对数关系，随着的增加而以对数的程度变大，而由于N的不断增加，集群系数也会逐渐增大。当在（0,1）之间时，系统表现为小世界特征，此时，的值近似和随机网络的相同，网络表

34、现出高度集群性质。 图2.5 WS模型中边的随机重连过程严格来说，即使是在时WS模型与包含同样节点和边数的ER模型还是会有区别的：在WS模型中每个节点的度至少是,但是在ER随机图中，并没有对单个节点的度的最小值进行任何限制。 如果要使得WS模型在时等同于ER随机图，则要在WS的生成算法中完全随机地对选取的每一条边的两个节点进行重新配置。下图为给定参数的情况下，和 的变化情况。图中将和 做了归一化处理，即和 ，这样就可以使两个变量在时的最大值都为1。其中：表示平均聚集系数，表示平均最短路径，表示重连概率。 图2.6 WS小世界模型的和随的变化关系 (3)无标度网络上个世纪九十年代以来，科学技术取

35、得了巨大进步，这就使得研究大规模的实际网络成为一种可能，人们可以借助计算机对真实网络进行模拟。在先进技术的支持下，人们逐渐意识到真正存在于我们身边的网络多数都存在另外的一些统计特性而并非是彻底随机的并且在构造的过程中它们会遵循某种规律并且具有随机网络模型所不具有的网络动力学特性，而在这些个迥异特性中当属小世界与幂律分布最为独特。无标度网络模型是由与（BA）联合建立的，实际网络中的无标度特征来自2种普遍的形成机制：第一，由于添加新节点而使得网络不断扩大；第二，新节点会优先与度最大的节点连接。受到这两点的启发 BA模型得到了建立，这网络研究史上最先阐明了节点度分布符合幂律函数的模型，因而意义非凡。

36、实际网络中的许多信息交换网、社交网、生物网络都遵循幂律分布特性。第三章 复杂网络抗毁性3.1网络抗毁性的定义虽然抗毁性应用极为广泛，但其定义大致可从两个角度进行表述：定性和定量。这也是人们在研究一个新的特性时常用的定义方法，这样可以让后来者对其有更加清晰的认识。下面从这两个角度来说明一下什么是抗毁性。(1)定性的定义定义1：Ellision等人针对信息系统的抗毁性提出：网络的抗毁性是在网络遭受意外事故、故障或者攻击时，系统能够及时提供完成其关键任务的能力。定义2;Louca等人针对通信网络提出：网络的抗毁性包括两方面内容: 1)在出现故障情况下，系统还能够维持或恢复到被用户所接受的性能的能力。

37、2)组织或转移潜在服务故障的能力。上述定义给出了抗毁性的定性描述，但是并未给出精确地描述，缺乏相应的具体性能指标，难以准确的判定系统的抗毁性。因此，针对这种情况，又有了定量的抗毁性定义。(2)定量的定义定义3：Knight和Sullivan针对信息系统提出:如果一个系统满足抗毁性规范，则认为这个系统是抗毁的。这个抗毁性规范是一个四元。1) E是抗毁系统运行环境的描述。2) R是网络提供的、具有可接受服务质量的指标集。3) P是遍布指标集R的概率分布，并且其概率之和是1。4) M是一个有限状态机，用四元组来表示。在M中，S表示有限状态的集合；表示初始状态或者优选状态；V表示用户值的集合；T表示转

38、移状态矩阵。该四元组明确的定义了网络什么时候以及如何从正在提供的一种服务状态转移到另外一种服务状态。在该定义中，抗毁性可以视为系统在某一环境中可以提供的具体服务的概率。定义4:对于分布式网络，抗毁性定义必须包括一下几个方面：1)系统定位：对于不同的网络系统，抗毁性是不同的。如果抗毁性定义有变化，那么必须要说明。例如，在军事网络中，抗毁性定义为：在遭受敌人攻击时，能够保持军事武器或设备或其他军事力量性能的能力。而在通信网络系统中，抗毁性定义为：网络容错并持续提供服务的能力。另外，系统是有界还是无界的也要说明。2)威胁： 对网络的威胁可能会影响网络（系统）在规定时间内继续为它的用户提供服务。网络的

39、威胁可以归为偶然的、故意或恶意的和灾害的这三类。偶然因素包括软件的错误，硬件错误，以及人为失误。故意或恶意的威胁包括故意毁坏，黑客入侵，以及恐怖袭击。灾害威胁指的是由于自然灾害（洪水，台风，飓风，雷电，地震，海啸等）、战争行为和停电事故的发生，造成了物理设备的损坏，致使网络没有办法再给用户提供服务。3)适应性：在系统受到威胁时，系统应该有适应能力和继续提供服务的能力。例如，电力系统应有能力适应短期内局部过载等突发状况，防止大面积停电事故的发生。4)服务的持续性：服务对用户应该是可用的，即使在破坏发生时，网络的性能不应该退化。5)时效性：服务应该在系统要求的时间内让用户接收到。3.2网络抗毁性分

40、析3.2.1抗毁性度量指标(1)鲁棒性度量连通性是网络的重要性能指标之一。网络鲁棒性用来衡量网络遭受攻击时剩余节点之间仍能保持连通的能力。由此，网络鲁棒性可定义为移除任意节点后，网络中仍连通的节点对与网络总节点对的比值。用来表示受到节点删除后的网络，网络的鲁棒性有如下表示： (3.1)为连通系数，若和之间连通，当节点和之间连通时，否则=0。网络鲁棒性描述了网络在遭受外界干扰或破坏时的连通性，反映了网络结构本身对于攻击的抵御能力，克服了最大连通子图的相对大小不能反映网络受到攻击后子网络的连通情况的缺点。均存在某种程度上的损坏几率，所以要让鲁棒性高至峰值，纵然网络能够做到全连通也是不可能的。(2)

41、网络效率度量 有效性度量说明的是网络在某时段内能够正常运转并发挥功效的程度，可以刻画出网络传递信息的效率。计算全网效率的方法如下： (3.2) 上式反映出：信息传递的路程越长，传输距离越大传播过程所消耗的时间越多，网络的传输效率就越低。反之，网络传输效率越高。3.2.2实证分析与仿真分析复杂网络抗毁性研究最早开始于2000年Albert等的工作，他们开始关注拓扑结构对复杂网络抗毁性的影响。他们分别把随机网络（ER模型）和无标度网络（BA模型）至于两种类型的打击策略之下：一是随机失效，在这种打击中，随机移除网络中的节点，这与网络中的随机故障相对应；二是选择性攻击，按照节点连接度从大到小的顺序移除

42、节点，即仅仅拿掉网络中的活动中心。Albert等分别研究了不同网络面对不同打击条件下极大连通片尺寸与网络规模之比、极大联通片平均最短路径与节点移除比例的关系，研究结果如下图3.1所示。 图3.1 不同网络面对不同打击条件下和与的关系从上图可以看出，在第一种打击手段下，无标度网络明显有着更好的抗毁性。而在第二种方式下，相比于随机网络而言，无标度网络会更加迅速地走向了崩溃，并且一旦删除那些关键节点就会致使网络进入瘫痪状态。对比之下会发现此时的它异常脆弱。后来人们在WWW和Internet上所做的实证分析证实了艾伯特的这一论断。之后的布罗德等人又通过对www的实证研究得出在目标性的打击下，网络会表现

43、出比平时更为强大的抗毁性。由于前人的研究使得后来人愈来愈对这方面感兴趣，吸引着他们不断对其进行学习和探讨，并且所得结论与艾伯特的大体相同。而仿真研究方面，最为权威的当是以霍姆为首的科研工作者所做的。他在前人的基础上又进行了移除边的实验，在攻击方法上又新增了这对介数的打击，也取得了可喜的成就，为该领域的研究做出了不小的贡献。此后，很多学者对其他现实世界中的复杂网络抗毁性问题进行了研究，总体结构几乎均与Albert等的结果一致，大多数为了对于随机的节点删除都表现出抗毁性，而面对以最大度节点为目标的选择性攻击就相当脆弱。例如Jeong等的蛋白质网络研究，Dunne等的食物链网络研究，Newman等的

44、电子邮件网络研究，Magoni等的Internet，Samant等的P2P网络研究。有关攻击策略对复杂网络抗毁性影响的仿真研究中，比较全面的要数Holme等的研究工作。他们将攻击策略分为节点攻击与边攻击两种方式。每种攻击又包括四种不同的策略：ID移除策略（对初始网络按节点或边的度大小顺序来移除节点或边）、IB移除策略(对初始网络按照节点或边的介数大小顺序来移除节点或边)、RD移除策略（每次移除的节点或边是当前网络中节点或边的度最大的节点）和RB移除策略（每次移除的节点或边是当前网络中节点或边介数最大的节点）。ER模型对节点的基于度的攻击比基于介数的攻击效果好，使用重新计算的信息比基于原始信息的

45、危害性更强；而对边的攻击RB远比其他策略更具破坏性。无尺度网络对节点移除比ER模型更敏感，在攻击初期四种策略的差异性不明显，随着移除的继续进行，攻击对网络的破坏程度按以下顺序排列：RBRDIDIB；而且对边的攻击情况同节点攻击相似。他们还对因特网等真实网络作了数字分析，验证了Albert等的结论。 第四章 因特网抗毁性分析4.1因特网的拓扑结构及加权网络介绍(1)因特网的拓扑结构因特网是按照一个统一的标准将不同规模和类型、不同地理位置的网络连接在一起所组成的一个整体，可以相互之间进行各种信息的交换。这是个由数十万网络连接而构成并呈现出一致性的复杂网络形式。由于在因特网上主机有随机接入和断开的情

46、况，所以因特网的整体拓扑机构就应该随之具有均匀分布的特征，进而因特网各节点的从表面上看起来像是均匀分布的。然而大量的实验结果证明，因特网连通度的实际分布是服从幂律分布的，这就说明因特网节点连通度的分布是标度无关的。我们所熟悉的WWW是定义在Hyperspace上的虚拟网络，而因特网不同于WWW，它是由路由器、计算机以及其连接其中的其他通讯设备组成的硬件网络，在这个硬件网络中，由光纤等物理链路将这些路由器与各设备连接起来。人们研究了两个不同层次的因特网拓扑结构，它们分别是自治系统层与路由器层。如4.1所示。在路由层，每个路由器都可以被看成是网络中的一个节点，连接在不同路由器之间的物理链路则可以被

47、看做是边。在自治系统层，一个自治系统由成百上千的计算机与路由器组成，这个自治系统可以被看做是一个节点，并且，只要在两个自治系统之间有路径，那么就可以认为它们之间存在一条边。等研究了因特网两个不同层次上的度分布发现它们均满足幂律分布。到了2000年，和进一步深入研究了路由层面上的因特网拓扑，并且得出了度指数为。同时因特网的平均路径长度比较长并且它的集群系数比较大，根据之前因特网数据，Yook和Pastor-Satorras等分析了自制系统层，并且得出因特网的聚集系数的取值在0.18到0.3之间。在自治系统层因特网的平均路径长度介于3.70和3.77之间。 图4.1 Internet 的路由器层和

48、自制系统层 图4.2 路由器层上Internet的度分布在所有的因特网拓扑特征研究成果中，最重要的发现就是因特网是一个典型的无标度网络。因为因特网的发展过程完全符合上述无标度网络形成所需具备的两个前提条件：一是因特网是一个到目前为止仍在不断发展的复杂巨系统，不断有新的路由器节点、自治域和用户加入这一系统当中；二是因特网的发展过程中普遍存在“优先连接”现象。新加入的路由器总是倾向于连接那些连接数较多的路由器，以便获得到其它路由器最短的距离和较大的带宽；因特网的新用户也更倾向于访问知名度较高的网站。随着时间的推移，尽管系统中的节点和边在不断增加，但网络拓扑结构特性却不会发生很大的变化，网络中必然存

49、在一些连接数远远高于平均连接数的集散节点，从而形成了因特网的无尺度特征。另外，因特网还具有递阶结构。这种结构通常可以分为4层：国际网络，国家中枢网络，区域网络以及局域网络。在这样的组织构架中，网络节点的平均度比较小，平均路径长度也比较小。递阶结构使得网络节点之间具有关联，因而关联性是因特网不容忽视的一个特性。此外，在因特网中，当加入新的连接时，路由器总是乐意通过最短距离进行连接，从而导致在同一个地区的路由器之间有更多的连接，而不同地区路由器之间的连接相对来说比较少。所以同一地区内的路由器间有较大的聚类系数。例如，在亚洲地区有个度很大的节点，在欧洲地区有一个新节点加入，按照以往优先连接的原则，欧

50、洲新加入的节点和亚洲这个节点连接的概率很大。然而事实上，新加入欧洲地区的节点更可能是和欧洲某个度很大的节点相连，而不会选择漂洋过海来连亚洲这个节点。这正体现了上述因特网拓扑结构的区域化特性。分析因特网的层次结构可知，无论在哪个层次，都有少量的连接度较高的核心节点，大量的连接度较低的非核心节点。也就是说，在因特网宏观拓扑结构的各个层次，都呈现出明显的无尺度特征。并且，在不同尺度上观察因特网，可以发现其结构具有自相似性。鉴于因特网是具有无标度网络的特性的，接下来对于因特网的研究都以无标度网络为模型来进行分析。 (2)加权网络介绍人们对复杂网络的早期研究主要集中在无权网络方面，然而，在实际网络中，节

51、点之间的关系呈现出丰富的多样性，如果忽略了节点之问相互作用的差异性，就会失去很多重要信息。给网络中的每条边都赋予相应的权值，无权网络就成为加权网络。加权网络为描述节点之间的关系和相互作用提供了更加细致的刻画手段，且权重及其分布也会对网络的性质和功能产生重要影响。因此，加权网络已经成为复杂网络的一个重要的研究领域。加权网络可以用图G=(V,E)来表示，其中，是一个无向连通图，有个节点和条带权重的边。节点集，边集。一般用权重邻接矩阵表示加权网络的权重，其中元素表示节点与为端点的边的权重，权重，当网络中各条边的权值都相同时，加权网络即退化为无权网络。加权网络研究需要考虑的第一个问题就是边权的赋予方式

52、。权重代表的是节点问相互作用的关系与强度，以往的权重模型主要有YJBT模型、AK模型以及BBV模型等。4.2考虑信息条件下因特网的加权网络基于节点的抗毁性分析4.2.1因特网抗毁性模型描述首先，构建加权复杂网络。本节的分析是基于加权BA无标度网络的，按照文献17给出的方法构建BA网络，其初始节点数。网络的构建依赖于择优吸附机制。之后，给BA网络中的边赋予权值，并且的取值在集合当中选择。本节考虑了一种将无权网络的性质转化为边权的赋权模型，在文献9的基础上，边权的赋予方式为：假设、分别表示、的度值，两个节点之间的边为，则边的权重就表示如下：=，用来控制边权的强度称为权重系数。边权的这种赋值方式是建

53、立在实际网络的观测数据基础上的，另外，在加权网络中，边的介数和其两端节点度的乘积呈正相关的关系。其次，选取攻击方式。攻击方式的选择是加权网络抗毁性分析的关键，攻击者往往是会依照自己所掌握的网络结构信息，选择对网络破坏最为严重的方式已达到最高的费效比。根据攻击者对网络信息的掌握程度，把攻击方式划分为两类：基于网络局部信息和全局信息攻击。节点的度和介数是网络节点重要性的两个常用测度，而介数较大的节点对于保持网络的传输效率具有重要作用。因此，攻击者通常会选择度和介数作为节点重要性度量指标，对加权网络中的节点进行重要性排序并依此进行攻击。本节根据霍姆等提出的四种攻击策略分别对加权网络抗毁性进行仿真，显

54、然，当网络受到攻击时，网络效率及连通性都会减小，在一定的节点移除比例下，其减小的幅度越小，则说明网络的抗毁性越强。霍姆等利用了以下四种网络攻击策略：(1)ID移除策略。对初始网络按节点的度大小顺序来移除节点或边。(2)IB移除策略。对初始网络按照节点的介数大小顺序来移除节点或边。(3)RD移除策略。每次移除的节点是当前网络中节点或边的度最大的节点。(4)RB移除策略。每次移除的节点是当前网络中节点或边介数最大的节点。加权网络的性能变化是与权重系数密切相关的，其抗毁性分析较为复杂，要给出精确的解析分析十分困难。因此，采用数值仿真的方法来研究加权复杂网络的抗毁性与网络参数的关系。4.2.2局部信息

55、下的抗毁性仿真结果节点的度刻画的是节点的局部特性，基于局部信息的攻击方式就是依据度值对节点进行攻击，其中又分为初始节点度（ID)和重新计算节点度(RD)2种方式。在ID攻击方式下，加权网络效率及连通性的变化情况如图4.3(1)和图4.3(2)所示，仿真结果为10次仿真的平均值。其中，记为移除节点的比例,为网络效率下降比率，为网络连通性。由图4.3和4.4可知，在确定权重系数的情况下，网络效率和连通性随着节点移除比例的增大而不断下降。在大约移除45%的节点后，网络的效率和连通性均下降0。 图4.3 ID攻击下随变化的曲线 图4.4 ID攻击下随变化的曲线另外，ID攻击初始阶段网络效率与连通性的变

56、化曲线如图4.5和4.6所示，若取定网络效率的下降阈值为10%，可以看出在网络的连通性被完全破坏前，权重系数越大，节点移除对于网络效率的影响越小，网络的抗毁性越强。比如在移除10%的节点后，的网络效率下降了38%，而的网络效率仅下降16%。若取定网络的连通性阂值为90%，则在移除比例小于5%之前，权重系数的变化对于网络连通性的影响不大，仅在节点移除比例大于5%时有细微的差别。 图4.6 ID攻击初始阶段随变化的曲线 4.2.3全局信息下的抗毁性仿真结果节点的介数刻画的是节点的全局影响力，基于全局信息的攻击方式就是依据介数对节点进行攻击，其中又分为初始节点介数(IB)和重新计算的节点介数(RB）

57、2种。在IB攻击方式下，加权网络效率及连通性的变化情况分别如图4.7和图4.8所示，仿真结果为10次仿真的平均值。其中，记为移除节点的比例,为网络效率下降比率，为网络连通性。由图4.7和图4.8可以看出：随着节点移除比例的增大，权重系数对于网络连通性的影响呈现出两极分化的趋势；当时，节点移除比例达到48网络连通性下降为0，节点移除对网络连通性的影响最大，而其他取值之间的差别很小；权重系数对于网络效率的影响也呈现出非常复杂的关系，当时，节点移除对网络效率和连通性的影响要小于其他值。经过进一步研究发现：当时网络对节点移除最不敏感，网络效率与连通性随节点移除比例增大的变化率较小，表明对应的加权网络抗

58、毁性最优。 图4.7 IB攻击下随变化的曲线 图4.8 IB攻击下随变化的曲线在RB攻击方式下，加权网络效率及连通性的变化情况分别如图4.9和图4.10所示。由图可知：节点移除对于网络效率和连通性的影响更为复杂；当节点移除比例小于40%时，权重系数的加权网络效率下降最快，对于其他取值的网络，节点移除对其网络效率的影响没有明显的规律；对于网络的连通性而言， 的网络下降最快，随着的不断增大，节点移除对网络连通性的影响不断减小，网络抗毁性不断增强。 图4.9 RB攻击下随变化的曲线 图4.10 RB攻击下随变化的曲线RB攻击初始阶段网络效率的变化如图4.11所示：在早期阶段，权重系数的网络效率对于节

59、点移除的敏感性最低，抗毁性最强。 图4.11 RB攻击初始阶段的随变化的曲线4.3考虑信息条件下因特网的加权网络基于边的抗毁性分析4.3.1抗毁性模型由于网络中边的承载能力及在网络中的作用也不同,因此在对一个网络进行攻击时,攻击不同的边对网络的影响也是不同的,例如如果攻击的是一条核心的边,承担着网络中较多的流量,则攻击该边将会对网络产生较大的影响。如果攻击的是一条承担着较少流量的边,则该边的失效对网络的影响也会相应地偏小。另外在实际对网络进行打击时,掌握的网络信息的多少对网络的攻击策略的制定也有一定的影响。基于以上事实，可以设计如下模型来探索基于边的网络抗毁性。对于一个有N个节点，条边的加权网

60、络，定义基于边的网络抗毁性模型为： (4.1)其中， 的值为已知信息的边数与总边数的比值 ,并且值愈大，表示网络被攻击者了解愈多的信息。很明显的值在0和1之间变化。当取两个边界值时，分别表示网络受到了外界完全不了解网络信息的随机攻击以及了解所有信息的故意攻击。I代表了受到攻击的那个边的介数，可它以表明该边于网络中所担当的角色是否重要。在特定的打击下，为已被破坏的边的数目与总边数的比值，f愈大则网络的抗毁性愈不好。在信息获取上，用来表示攻击者所能够得到多少有用信息。当=0时，即所有边被获取信息的可能性相同,我们称这种情况下的信息获取为随机信息获取；而=表示最重要的信息总是优先被获取到，称为优先信息获取状态。的值愈大就说明攻击者所得到的网络信息越重要，那么他对网络造成的伤害也就