分子生物网络分析崔颖第2章 网络拓扑基本模型及其性质

1、page 1第二章 网络拓扑基本模型及其性质教 师：崔 颖办公室：外语学馆412室e- mail: 分子生物网络分析分子生物网络分析(molecular biology network analysis)page 2n理解网络结构和网络行为之间的关系。n对实际网络结构有深入的了解，考虑改善网络的行为。n在此基础上建立合适的网络结构模型。n本章介绍几类基本的模型：规则网络、随机图、小世界网络、无标度网络、等级网络等模型。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 3nwatts和strogatz关于小世界网络的工作；nbara

2、basi和albert关于无标度网络的开创性工作。n人们对存在于不同领域的大量实际网络的拓扑特征进行了广泛的实证性研究。n从不同角度提出了各种各样的网络拓扑结构模型。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 4分子生物网络分析分子生物网络分析(molecular biology network analysis)page 5分子生物网络分析分子生物网络分析(molecular biology network analysis)page 6分子生物网络分析分子生物网络分析(molecular biology network

3、analysis)page 7分子生物网络分析分子生物网络分析(molecular biology network analysis)page 8有一个中心点，其余n-1个点都只与这个中心点连接。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 9有一个中心点，其余有一个中心点，其余n-1个点都只与这个个点都只与这个中心点连接中心点连接分子生物网络分析分子生物网络分析(molecular biology network analysis)page 101112ijijldnn21iiiieckk请同学分析全局耦合网络的拓扑属性。如

4、：平均路径长度，聚类系数，服从哪种分布。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 11分子生物网络分析分子生物网络分析(molecular biology network analysis)page 12请计算全局耦合网络的紧密度、拓扑系数、介数。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 13n最近邻耦合网络：每个节点都与它左右的k/2个节点相连，k是一个偶数。n对大的n, k, 有：聚类系数c3/4, 平均路径长度l无穷大。请同学分析最近邻耦合网络的

5、拓扑属性。如：平均路径长度，聚类系数，服从哪种分布。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 14n一般地，规则网络具有大的聚类系数和大的平均距离。n这类网络是高度聚类的但不是一个小世界网络。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1513258471069请计算最近邻耦合网络的紧密度、拓扑系数、介数。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 161112ijijldn n21i

6、iiieckk请同学分析星形耦合网络的拓扑属性。如：平均路径长度，聚类系数，服从哪种分布。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 17n 星形耦合网络是比较特殊的一类网络。n 有些文献中定义如果一个节点只有一个邻居节点，那么该节点聚类系数定义为1.n 有些研究文献则定义只有一个邻居节点的节点聚类系数为0，依此定义，星形网络的聚类系数为0. nnncnnnnl1121122聚聚类类系系数数：平平均均路路径径长长度度： 0c 分子生物网络分析分子生物网络分析(molecular biology network analysi

7、s)page 18请计算星形耦合网络的紧密度、拓扑系数、介数。35846917102分子生物网络分析分子生物网络分析(molecular biology network analysis)page 19分子生物网络分析分子生物网络分析(molecular biology network analysis)page 20n与完全规则网络相反的是完全随机网络。n典型的模型是erds和rnyi于40多年前开始研究的er随机图模型。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 21n 假设有大量的纽扣（n1）散落在地上，并以相同的概率

8、p给每对纽扣系上一根线。n 这样就会得到一个有n个点，约pn（n-1）/2条边的er随机图的实例。例如：节点数n=10，p值分别为：0，0.1，0.15，0.25则可以得到er随机图的实例。请同学给出此实例演化过程。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 22n随机演化示意图：n=10，p=0；p=0.1；p=0.15，p=0.25分子生物网络分析分子生物网络分析(molecular biology network analysis)page 23ner随机图具有的性质：涌现或相变性质ner随机图的许多重要性质都是突然涌

9、现的：也就是说，对于任一给定的概率p，要么几乎每一个图都具有某个性质q（比如，连通性），要么几乎每一个图都不具有该性质。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 24n例如，对于上述纽扣网络，如果你捡起一个纽扣，那么将有多少个纽扣也会跟着被拎起来呢？n结果显示，如果概率p有大于某个临界值pc（lnn）/n，那么几乎每一个随机图都是连通的，也就是说，随机地捡起一个纽扣都会拎起地上几乎所有的纽扣。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 25ner随机图的

10、平均度=p(n-1)pn。n设ler是er随机图的平均路径长度。直观上，对于er随机图中随机选取的一个点，网络中大约有 ler个其他的点与该点之间的距离等于或非常接近ler。因此，lerlnn/ln。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 26n这种平均路径长度为网络规模的对数增长函数的特征就是典型的小世界特征。n因为当lnn的值随n增长得很慢，这就使得即使是规模很大的网络也可以具有很小的平均路径长度。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 27n

11、er随机图中两个节点之间不论是否具有共同的邻居节点，其连接概率均为p。n因此，er随机图的聚类系数c=p=/n1，这意味着大规模的稀疏er随机图没有聚类特征。n现实中的复杂网络一般都具有明显的聚类特性，也就是说，实际的复杂网络的聚类系数要比相同规模的er随机图的聚类系数高得多。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 28分子生物网络分析分子生物网络分析(molecular biology network analysis)page 29分子生物网络分析分子生物网络分析(molecular biology network

12、analysis)page 30分子生物网络分析分子生物网络分析(molecular biology network analysis)page 31布朗运动布朗运动分子生物网络分析分子生物网络分析(molecular biology network analysis)page 32分子生物网络分析分子生物网络分析(molecular biology network analysis)page 33ner随机图作为实际复杂网络的模型存在明显的缺陷。ner随机图理论一直是研究复杂网络拓扑的基本理论，其中一些基本思想在目前的复杂网络理论研究中仍然很重要。n可以参考bollobs的著作。分子生物网络

13、分析分子生物网络分析(molecular biology network analysis)page 34n从多角度对er随机图进行扩展以使其更接近真实的网络。n一个推广就是具有任意给定度分布的广义随机图（generalized random graph）。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 35n给定一个度分布p（k），它表示了网络中度为k的节点所占的比例。n基于这一分布按相同概率产生多个度序列为ki（i=1,2,.,n）的由n个节点组成的网络。n这些网络模型的集合称为配置模型（configuration mode

14、l），详细介绍参见newman的综述。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 36这两类网络模型都不能再现真实网络的一些重要特征。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 37n毕竟大部分实际网络既不是完全规则的，也不是完全随机的。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 38nwatts和strogtz于1998年引入了一个有趣的小世界网络模型，称为ws小世界模型，作为从完全规

15、则网络向完全随机图的过渡。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 39n ws小世界模型构造算法如下：1.从规则图开始：考虑一个含有n个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右的各k/2节点相连，k是偶数。2.随机化重连：以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。分子生物网络分析分子生物网络分析(molecular biology network anal

16、ysis)page 40分子生物网络分析分子生物网络分析(molecular biology network analysis)page 41n通过调节p的值就可以控制从完全规则网络到完成随机网络的过渡。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 42分子生物网络分析分子生物网络分析(molecular biology network analysis)page 43分子生物网络分析分子生物网络分析(molecular biology network analysis)page 44nws小世界模型的随机化重连过程：分子生物

17、网络分析分子生物网络分析(molecular biology network analysis)page 45分子生物网络分析分子生物网络分析(molecular biology network analysis)page 462( )(/ 2)nl pf nkpk分子生物网络分析分子生物网络分析(molecular biology network analysis)page 47分子生物网络分析分子生物网络分析(molecular biology network analysis)page 48分子生物网络分析分子生物网络分析(molecular biology network analys

18、is)page 492.nw小世界模型nws小世界模型构造算法中的随机化过程有可能破坏网络的连通性。n另一个研究较多的小世界模型由newman和watts稍后提出的，称为nw小世界模型。n该模型是通过用“随机化加边”取代ws小世界模型 构造中的“随机化重连”而得到的。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 502.nw小世界模型nnw小世界模型构造算法：n1.从规则图开始：考虑一个含有n个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各k/2个节点相连，k是偶数。n2.随机化加边：以概率p在随机选取的一

19、对节点之间加上一条边。其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 512.nw小世界模型nnw小世界模型的随机化加边过程。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 522.nw小世界模型n在nw小世界模型中：p=0对应于原来的最近邻耦合网络；p=1则对应于全局耦合网络。n理论分析，nw小世界模型要比ws小世界模型简单一些。当p足够小和n足够大时，nw小世界模型本质上等同于w

20、s小世界模型。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 532.nw小世界模型分子生物网络分析分子生物网络分析(molecular biology network analysis)page 543.小世界网络模型的统计性质n聚类系数：分子生物网络分析分子生物网络分析(molecular biology network analysis)page 553.小世界网络模型的统计性质分子生物网络分析分子生物网络分析(molecular biology network analysis)page 563.小世界网络模型的统计性质

21、分子生物网络分析分子生物网络分析(molecular biology network analysis)page 57分子生物网络分析分子生物网络分析(molecular biology network analysis)page 58分子生物网络分析分子生物网络分析(molecular biology network analysis)page 59分子生物网络分析分子生物网络分析(molecular biology network analysis)page 60分子生物网络分析分子生物网络分析(molecular biology network analysis)page 61分子生物网

22、络分析分子生物网络分析(molecular biology network analysis)page 62请同学们回忆什么是幂律分布？请同学们思考什么是特征长度？分子生物网络分析分子生物网络分析(molecular biology network analysis)page 63n特征长度（characteristic length）是属于分形几何的概念。n对于某个物体, 特征长度通常是指该物体长度中有代表意义的长度, 如我们考察一个球体, 那么它的特征长度就是该球体的半径或直径。分子生物网络分析分子生物网络分析(molecular biology network analysis)page

23、 64n普通几何学研究的对象，一般都具有整数的维数。比如，零维的点、一维的线、二维的面、三维的立体、乃至四维的时空。n在20世纪70年代末80年代初，产生了新兴的分形几何学（fractal geometry），空间具有不一定是整数的维，而存在一个分数维数。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 65n自然界中的物体或图形, 要么具有特征长度, 要么不具有特征长度。n对于具有特征长度的物体, 只要其特征长度不变, 其性质就不会发生什么变化。n还有的事物没有特征尺度，就必须同时考虑从小到大的许许多多尺度（或者叫标度），这叫做

24、“无标度性”的问题。 分子生物网络分析分子生物网络分析(molecular biology network analysis)page 66n分开几何：分子生物网络分析分子生物网络分析(molecular biology network analysis)page 67n分形几何学的基本思想是：客观事物具有自相似的层次结构，局部与整体在形态、功能、信息、时间、空间等方面具有统计意义上的相似性，称为自相似性。n例如，一块磁铁中的每一部分都像整体一样具有南北两极，不断分割下去，每一部分都具有和整体磁铁相同的磁场。n这种自相似的层次结构，适当的放大或缩小几何尺寸，整个结构不变。分子生物网络分析分子生

25、物网络分析(molecular biology network analysis)page 68n自相似性：分子生物网络分析分子生物网络分析(molecular biology network analysis)page 69n上世纪80年代初开始的“分形热”经久不息。分形作为一种新的概念和方法，正在许多领域开展应用探索。n美国物理学大师约翰惠勒说过：今后谁不熟悉分形，谁就不能被称为科学上的文化人。n由此可见分形的重要性。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 70n近年来，人们在互联网和人际关系网络等社会学网络的研究中

26、都发现了“无标度”特性。n无标度网络中，大部分节点通过少数中心节点连接到一起，这就意味着节点在网络中的地位是不平等的，中心节点在连接网络完整性方面起更加重要的作用。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 71n定义：无标度网络，是指网络中连通度的分布符合幂率分布，即p(k)k-r的网络，如图2-4 b所示。n这种分布说明，在无标度网络中大部分节点的连通度较低，但存在少数连通度非常高的节点使网络连接在一起。在这种网络中，平均连通度等标度已经不足以描述网络的规模和结构。分子生物网络分析分子生物网络分析(molecular b

27、iology network analysis)page 72n 图2-4b无标度网络及其连通度分布和聚类系数函数趋势图n b为无标度网络，其连通度分布符合幂率分布，平均聚类系数函数曲线水平。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 73分子生物网络分析分子生物网络分析(molecular biology network analysis)page 74例如：每个月都会有大量的生物信息学文章发表；www上则每天都有大量新的网页产生；分子生物网络分析分子生物网络分析(molecular biology network ana

28、lysis)page 75例如：新发表的文章更倾向于引用一些被广泛引用的重要文献；新的个人主页上的超文本链接更有可能指向新浪、雅虎等著名的站点。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 76分子生物网络分析分子生物网络分析(molecular biology network analysis)page 77分子生物网络分析分子生物网络分析(molecular biology network analysis)page 78分子生物网络分析分子生物网络分析(molecular biology network analysis

29、)page 79jjiikk分子生物网络分析分子生物网络分析(molecular biology network analysis)page 80例例: m0 = 3, m = 2t = 1t = 2t = 3分子生物网络分析分子生物网络分析(molecular biology network analysis)page 81分子生物网络分析分子生物网络分析(molecular biology network analysis)page 82n按照这种机制构建起的网络即可得到无标度网络。n例如，在互连网形成的初期，网络中的连接呈现随机特性，而当一个新的节点加入网络时，人们会倾向于访问已经具有一

30、定知名度的网站，也就更有可能与这样的网页建立连接。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 83n这样随着越来越多的节点引入网络，网络连接便呈现出无标度特性。n这个模型很好地解释了网页连接网络中少数权威网站存在的现象，也为生物分子网络中无标度特性的形成原因提供了很好的启示。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 84分子生物网络分析分子生物网络分析(molecular biology network analysis)page 85分子生物网络分析分

31、子生物网络分析(molecular biology network analysis)page 86分子生物网络分析分子生物网络分析(molecular biology network analysis)page 87n练习：初始网络含有两个节点，一条边，经过9步,构造ba模型，即m0=2,m=2,t=9.分子生物网络分析分子生物网络分析(molecular biology network analysis)page 88分子生物网络分析分子生物网络分析(molecular biology network analysis)page 89分子生物网络分析分子生物网络分析(molecular b

32、iology network analysis)page 90分子生物网络分析分子生物网络分析(molecular biology network analysis)page 91分子生物网络分析分子生物网络分析(molecular biology network analysis)page 92分子生物网络分析分子生物网络分析(molecular biology network analysis)page 93nba网络的度分布函数为：322)2)(1() 1(2)(kmkkkmmkpn这表明ba网络的度分布函数可由幂指数为3的幂律函数近似描述。分子生物网络分析分子生物网络分析(molecu

33、lar biology network analysis)page 94分子生物网络分析分子生物网络分析(molecular biology network analysis)page 95分子生物网络分析分子生物网络分析(molecular biology network analysis)page 96n目前对ba无标度网络的度分布理论的研究主要有三种方法：连续场理论（continuum theory）、主方程法、速率方程法。n这三种方法得到的渐近结果都是相同的，其中，主方程法和速率方程法是等价的。需要指出的是，对需要指出的是，对ba无标度网络模型的构造及无标度网络模型的构造及其理论分析的

34、严格性等还存在一些不同的看法。其理论分析的严格性等还存在一些不同的看法。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 97nnllogloglog分子生物网络分析分子生物网络分析(molecular biology network analysis)page 98分子生物网络分析分子生物网络分析(molecular biology network analysis)page 99分子生物网络分析分子生物网络分析(molecular biology network analysis)page 100网络的平均聚类系数与网络大小分

35、子生物网络分析分子生物网络分析(molecular biology network analysis)page 1013.无标度网络vs随机网络n如果网络中节点间的连接完全是随机的，那么连通度的分布应该符合泊松分布或者在大尺度的情况下近似认为符合正态分布。n即度的分布比较均匀，大部分节点的连通度都与平均连通度相差不多，只有极少数节点具有很低或很高的连通度，如图1-3 a所示。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1023.无标度网络vs随机网络分子生物网络分析分子生物网络分析(molecular biology net

36、work analysis)page 1033.无标度网络vs随机网络n 随机网络中直径或网络平均距离与节点的数目的对数成正比，即llog(n)。对于包含大量节点的网络，其直径相对要小得多，任意两个节点间只需要较少的转接即可以连接在一起。n 一方面网络中包含有大量节点和边，表现出“大世界”的景象，另一方面，连接任意节点间的距离却相对较小，呈现“小世界”的特征。这种“小世界”网络是复杂系统互作网络的共同特性，因此成为目前网络研究分析一个热点问题。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1043.无标度网络vs随机网络n无标

37、度网络对网络的另一个重要影响是使网络的直径相对较小，一般来说直径的大小正比于网络中节点数目的对数值的对数值即llog(log(n)。n这就使无标度网络比一般小世界网络直径更小，联系更紧密。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 105na为随机网络，其连通度分布符合泊松分布，在大尺度情况下近似服从正态分布。b为无标度网络，其连通度分布符合幂率分布，平均聚类系数函数曲线水平。c为层次网络，其连通度分布与符合幂率分布，平均聚类系数与连通度的倒数成正比分子生物网络分析分子生物网络分析(molecular biology net

38、work analysis)page 106分子生物网络分析分子生物网络分析(molecular biology network analysis)page 107分子生物网络分析分子生物网络分析(molecular biology network analysis)page 108分子生物网络分析分子生物网络分析(molecular biology network analysis)page 109无标度网络小结：n无标度网络定义及特点nba模型及构造算法nba模型的特性1.度分布2.平均路径长度3.聚类系数n无标度网络与随机网络的比较分子生物网络分析分子生物网络分析(molecular b

39、iology network analysis)page 110分子生物网络分析分子生物网络分析(molecular biology network analysis)page 111思考题？n无标度网络模型具有哪些特性？n真实网络中，若某些节点被攻击，会出现什么结果？分子生物网络分析分子生物网络分析(molecular biology network analysis)page 112n引言故事：achilles heel of the internetachilles是古希腊传说中的一位杰出英雄，身经百战，屡建功勋据说，achilles出生时也是一个极普通的孩子，母亲倒提着他的身体放到环绕

40、地狱的冥河之中去浸泡，练就一一副钢筋铁骨，任何凶恶的敌人也不是对手。但是，他的一只脚后跟 却因为握在母亲的手里没有浸泡到冥河之中，和普通人一样，成为英雄的致命弱点，最后也死于此。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 113分子生物网络分析分子生物网络分析(molecular biology network analysis)page 114n脆弱性：今天人们常常把系统的脆弱之处称为该系统的“achilles踵”(achilles heel).分子生物网络分析分子生物网络分析(molecular biology netw

41、ork analysis)page 115分子生物网络分析分子生物网络分析(molecular biology network analysis)page 116分子生物网络分析分子生物网络分析(molecular biology network analysis)page 117分子生物网络分析分子生物网络分析(molecular biology network analysis)page 118分子生物网络分析分子生物网络分析(molecular biology network analysis)page 119分子生物网络分析分子生物网络分析(molecular biology netw

42、ork analysis)page 120分子生物网络分析分子生物网络分析(molecular biology network analysis)page 121分子生物网络分析分子生物网络分析(molecular biology network analysis)page 122分子生物网络分析分子生物网络分析(molecular biology network analysis)page 123分子生物网络分析分子生物网络分析(molecular biology network analysis)page 124分子生物网络分析分子生物网络分析(molecular biology netw

43、ork analysis)page 125分子生物网络分析分子生物网络分析(molecular biology network analysis)page 126n去除节点的两种策略：n1.随机故障策略：即完全随机地去除网络中的一部分节点；n2.蓄意攻击策略：即从去除网络中度最高的节点开始，有意识地去除网络中一部分度最高的节点。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 127n假设去除的节点数占原始网络中总节点数的比例为f，可以用最大连通子图的相对大小s和平均路径长度l与f的关系来度量网络的鲁棒性。分子生物网络分析分子生物

44、网络分析(molecular biology network analysis)page 128n当f较小时，随机选取的节点都是度很小的节点，除掉这些节点对整个网络的连通性不会产生大的影响。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 129n研究发现，er随机图和ba无标网络之间存在极其显著的差异。n1.无标度网络对随机节点故障具有极高的鲁棒性：与随机图相比，最大连通子图的相对大小在相对高得多的f时才下降到零，而其平均路径长度的增长则要缓慢得多。分子生物网络分析分子生物网络分析(molecular biology netwo

45、rk analysis)page 130分子生物网络分析分子生物网络分析(molecular biology network analysis)page 131n这种无标度网络对随机故障的高度鲁棒性，来自于网络度分布的极端非均匀性，即绝大多数节点的度相对很小，而有少量节点的度相对很大。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 132n然而，正是这种非均匀性使无标度网络对蓄意攻击具有高度的脆弱性.n只要有意识地去除网络中极少量度最大的节点，就会对整个网络的连通性产生大的影响。分子生物网络分析分子生物网络分析(molecula

46、r biology network analysis)page 133分子生物网络分析分子生物网络分析(molecular biology network analysis)page 134n无标度网络与随机网络的鲁棒性的形象比较：n1.即使随机去除网络中的大量节点，无标度网络仍可保持基本的连通性。而随机去除同样多的节点，则可使同样规模的随机网络分成多个孤立的子网。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 135分子生物网络分析分子生物网络分析(molecular biology network analysis)page

47、 136n2.但蓄意去除少量度最高的节点就可破坏无标度网络的连通性。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 137分子生物网络分析分子生物网络分析(molecular biology network analysis)page 138n例：以internet为例，它的前身是20世纪60年代后期由美国国防部高级研究计划署（arpa）研制的arpanet。n目的之一是为了使得在一些子网和网关发生故障的情况下，网络还能维持基本的通信工作。分子生物网络分析分子生物网络分析(molecular biology network an

48、alysis)page 139n如今，internet已经发展成为一个规模巨大的网络，并在人类社会生活中起着越来越重要的作用。n而internet上每天都在发生各种各样的故障并经常受到黑客的攻击。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 140n这种情况下，internet能否保持它的功能无疑是一个重要的课题。nalbert、jeong和barabasi在文献中研究了两个实际网络对随机故障和蓄意攻击的鲁棒性。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1

49、41n一个是含有6000个节点的自治层internet结构图;n另一个是含有326000个网页的www子网。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 142n他们得到了与ba无标度网络相类似的结果，从而进一步验证了对随机故障的鲁棒性和对蓄意攻击的脆弱性是无标度网络的一个基本特征，并且指出其根源在于无标度网络的度分布是不均匀性。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 143n对随机故障的鲁棒性和对蓄意攻击的脆弱性是无标度网络的一个基本特征分子生物网络分

50、析分子生物网络分析(molecular biology network analysis)page 144n事实上，近些年不同领域科学家的研究表明，“鲁棒但又脆弱（robust yet fragile）”是复杂系统的最重要和最基本的特征之一。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 145nbroder等人研究了更大规模的www子网的鲁棒性。他们发现只有删除所有度大于5的节点才能完全破坏其连通性。n由于有些节点的度高达几千，这就意味着要对整个网络实施猛烈的攻击，因此，他们认为该网络对蓄意攻击也具有很高的鲁棒性。分子生物网络

51、分析分子生物网络分析(molecular biology network analysis)page 146nalbert认为www对蓄意攻击是呈现脆弱性的，而broder却认为具有很高的鲁棒性，这初看起来与albert等人的结论似乎是矛盾的？n其实不然，因为www具有高度倾斜的度分布，所以度数大于5的节点在整个网络中所占的比例还是很小的。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 147ncallaway和cohen等人运用逾渗理论对网络的鲁棒性作了理论性分析。nvalente等人基于callaway和cohen等人的分析

52、，推出对于随机故障和恶意攻击具有最优鲁棒性的网络中的节点的度最多只可能取自三个不同的值。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 148nbollobas和riordan则运用随机图理论对无标网络的鲁棒性和脆弱性作了数学分析。nholme等人研究了基于介数的删除策略，其中一个节点的介数刻画了网络中经过该节点的最短路径的数目。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1495.适应度模型nba无标度网络模型的精彩之处在于它把实际复杂网络的无标度特性，归结

53、为增长和优先连接两个非常简单明了的机制。n这很好地体现了科学研究中的从复杂现象提取简单本质的特点。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1505.适应度模型n当然这也不可避免地使得ba无标度网络模型和真实网络相比存在一些明显的限制。nba模型只能生产度分布幂律指数固定为3的无标度网络，实际网络的幂律指数则不尽相同，且大都属于2至3的范围内。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1515.适应度模型n此外，实际网络常常具有一些非幂律特征。n因此，

54、在ba模型的基础上，人们做了各种各样的扩展，其中一些重要的扩展模型都是通过修改ba模型中的优先连接方式而获得的。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1525.适应度模型n2000年，jeng等人在nature上发表的文章中对43种生物体组织的新陈代谢过程加以研究，他们以各种基质（如adp）为节点，以基质参与的某种化学反应为边构建了新陈代谢的复杂网络。n结果显示，这些网络的度分布都服从幂律分布，幂指数在2.02.4之间。分子生物网络分析分子生物网络分析(molecular biology network analysi

55、s)page 1535.适应度模型n在ba无标度网络的增长过程中，节点的度也在发生变化并且满足如下幂律关系。21)()(iitttk其中 是第i个节点在时刻t的度， 是第i个节点加入到网络中的时刻。)(tkiit分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1545.适应度模型n上式表明，在ba无标度网络中，越老的节点具有越高的度，那么实际网中也真是这样吗？21)()(iitttk在ba无标度网络的增长过程中，节点的度也在发生变化并且满足如下幂律关系。分子生物网络分析分子生物网络分析(molecular biology net

56、work analysis)page 1555.适应度模型n然而，在许多实际网络中，节点的度及其增长速度并非只与该节点的年龄有关。n有时是与节点的内在性质有关的，如个人的交友能力，www站点的内容和科研论文的质量等。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1565.适应度模型nbianconi和barabasi把这一性质称为节点的适应度（fitness）。n据此提出了 适应度模型(fitness model).n并给出了该模型的构造算法。分子生物网络分析分子生物网络分析(molecular biology network

57、 analysis)page 1575.适应度模型n 其构造算法如下：n 增长：从一个具有m0个节点的网络开始，每次引入一个新的节点并且连到m个已存在的节点上，这里mm0。每个节点的适应度按概率分布 选取 。)(分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1585.适应度模型n 其构造算法如下：n 优先连接：一个新节点与一个已经存在的节点i相连接的概率 ，与节点i的度ki，节点j的度kj和适应度之间满足如下关系:ijjjiiikk分子生物网络分析分子生物网络分析(molecular biology network analy

58、sis)page 1595.适应度模型n可见，适应度模型与ba无标度模型的区别在于，在适应度模型中的优先连接概率与节点的度和适应度之积成正比，而不是仅与节点的度成正比。jjjiiikk分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1605.适应度模型n这样，在适应度模型中，如果一个年轻的节点具有的较高的适应度，那么该节点就有可能在随后的网络演化过程中获取更多的边。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1615.适应度模型n取决于适应度分布的形式，适应度

59、模型表现出两类不同的行为，即：如果该分布具有有限支撑（finite support），那么与原始的ba模型一样，网络具有幂律分布。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1625.适应度模型n如果该分布具有无限支撑（infnite support），那么应用度最高的那个点就会获得占整个网络总边数的一定比例的边数，后者是一种所谓的“赢者通吃(winner takes all)”的现象，类似于市场中的寡头垄断。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1

60、63课堂小结n2.4无标度网络模型n鲁棒性和脆弱性n适应度模型n2.5局域世界网络演化模型分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1642.5局域世界演化网络模型n在诸多实际的复杂网络中存在着局域世界。 nba网络模型根据其优先连接概率公式来计算每一个节点的优先连接概率值，由此得到幂律分布形式的网络度分布。分子生物网络分析分子生物网络分析(molecular biology network analysis)page 1652.5局域世界演化网络模型n然而， 在许多实际网络中，由于局域世界连接性的存在，每一个节点都有各自