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

第二章 网络拓扑基本模型及其性质,教 师：崔 颖 办公室：外语学馆412室 E- mail: ying.cuiyahoo.cn,学习目标,理解网络结构和网络行为之间的关系。 对实际网络结构有深入的了解，考虑改善网络的行为。 在此基础上建立合适的网络结构模型。 本章介绍几类基本的模型：规则网络、随机图、小世界网络、无标度网络、等级网络等模型。,引言,Watts和Strogatz关于小世界网络的工作； Barabasi和Albert关于无标度网络的开创性工作。 人们对存在于不同领域的大量实际网络的拓扑特征进行了广泛的实证性研究。 从不同角度提出了各种各样的网络拓扑结构模型。,第二章 网络拓扑基本模型及其性质,2.1规则网络模型 2.2随机网络模型 2.3小世界网络模型 2.4无标度网络模型 2.5局域世界演化模型 2.6模块性与等级网络 2.7超家族 2.8复杂网络的自相似性,2.1.规则网络,规则网络（Regular Network）的特征： 如果系统中节点及其与边的关系是固定的，每个节点都有相同的度数，就可以用规则图来表示这个系统。 这样的网络就称为规则网络。,2.1.规则网络,定义：全局耦合网络（globally coupled network），任意两个点之间都有边直接相连。,全局耦合网络 -完全连接,2.1.规则网络,定义：最近邻耦合网络(nearest-neighbor coupled network)，每一个节点只和它周围的邻居节点相连。,最近邻耦合网络 -最近邻连接,2.1.规则网络,定义：星形耦合网络（star coupled network）,有一个中心点，其余N-1个点都只与这个中心点连接。,星形耦合网络 -星形连接,2.1.规则网络,全局耦合网络 任意两个点之间都有边直接相连,最近邻耦合网络 每一个节点只和它周围的邻居节点相连,星形耦合网络 有一个中心点，其余N-1个点都只与这个中心点连接,1.全局耦合网络(Globally coupled network),平均路径长度为L=1 聚类系数为C=1 度分布：Delta函数,请同学分析全局耦合网络的 拓扑属性。如：平均路径长度， 聚类系数，服从哪种分布。,全局耦合网络(Globally coupled network),具有N个节点的全局耦合网络有N(N-1)/2条边； 但是大多数实际网络是稀疏的，边数一般至多是O(N)而不是O(N2),全局耦合网络 -完全连接,1.全局耦合网络(Globally coupled network),请计算全局耦合网络的紧密度、拓扑系数、介数。,2.最近邻耦合网络 (Nearest-neighbor coupled network),最近邻耦合网络：每个节点都与它左右的K/2个节点相连，K是一个偶数。 对大的N, K, 有：聚类系数C3/4, 平均路径长度L无穷大。,请同学分析最近邻耦合网络的 拓扑属性。如：平均路径长度， 聚类系数，服从哪种分布。,2.最近邻耦合网络 (Nearest-neighbor coupled network),一般地，规则网络具有大的聚类系数和大的平均距离。 这类网络是高度聚类的但不是一个小世界网络。,2.最近邻耦合网络 (Nearest-neighbor coupled network),请计算最近邻耦合网络的紧密度、拓扑系数、介数。,3.星形耦合网络(star coupled network),请同学分析星形耦合网络的 拓扑属性。如：平均路径长度， 聚类系数，服从哪种分布。,3.星形耦合网络(star coupled network),星形耦合网络是比较特殊的一类网络。 有些文献中定义如果一个节点只有一个邻居节点，那么该节点聚类系数定义为1. 有些研究文献则定义只有一个邻居节点的节点聚类系数为0，依此定义，星形网络的聚类系数为0.,3.星形耦合网络(star coupled network),请计算星形耦合网络的紧密度、拓扑系数、介数。,2.1.规则网络-小结,全局耦合网络：聚类系数高，平均路径长度小，反映了网络的高度聚类和小世界性质 最近邻耦合网络：聚类系数高，平均路径长度大，此类网络具有高度聚类但是不是小世界网络。 星形耦合网络：聚类系数低（高），平均路径长度小，此类网络为小世界网络,2. 2随机网络,与完全规则网络相反的是完全随机网络。 典型的模型是Erdös和Rényi于40多年前开始研究的ER随机图模型。,2. 2随机网络,假设有大量的纽扣（N1）散落在地上，并以相同的概率P给每对纽扣系上一根线。 这样就会得到一个有N个点，约PN（N-1）/2条边的ER随机图的实例。,例如：节点数N=10，P值分别为：0，0.1，0.15，0.25 则可以得到ER随机图的实例。 请同学给出此实例演化过程。,2. 2随机网络,随机演化示意图：N=10，P=0；P=0.1；P=0.15，P=0.25,2. 2随机网络,ER随机图具有的性质：涌现或相变性质 ER随机图的许多重要性质都是突然涌现的：也就是说，对于任一给定的概率P，要么几乎每一个图都具有某个性质Q（比如，连通性），要么几乎每一个图都不具有该性质。,2. 2随机网络,例如，对于上述纽扣网络，如果你捡起一个纽扣，那么将有多少个纽扣也会跟着被拎起来呢？ 结果显示，如果概率P有大于某个临界值Pc（lnN）/N，那么几乎每一个随机图都是连通的，也就是说，随机地捡起一个纽扣都会拎起地上几乎所有的纽扣。,2. 2随机网络,ER随机图的平均度=P(N-1)PN。 设LER是ER随机图的平均路径长度。直观上，对于ER随机图中随机选取的一个点，网络中大约有 LER个其他的点与该点之间的距离等于或非常接近LER。因此，LERlnN/ln。,2. 2随机网络,这种平均路径长度为网络规模的对数增长函数的特征就是典型的小世界特征。 因为当lnN的值随N增长得很慢，这就使得即使是规模很大的网络也可以具有很小的平均路径长度。,2. 2随机网络,ER随机图中两个节点之间不论是否具有共同的邻居节点，其连接概率均为P。 因此，ER随机图的聚类系数C=P=/N1，这意味着大规模的稀疏ER随机图没有聚类特征。 现实中的复杂网络一般都具有明显的聚类特性，也就是说，实际的复杂网络的聚类系数要比相同规模的ER随机图的聚类系数高得多。,2. 2随机网络,如果节点不是按确定的规则连线，譬如按纯粹的随机方式连线，所得到的网络就成为随机网络（random network）。 如果节点按照某种（自）组织原则方式连线，将演化成各种不同的网络，称为复杂网络（complex network）。,2. 2随机网络,2. 2随机网络,随机网络特征:如果系统中节点及其与边的关系不确定，就只能用随机网络来表示这个系统。 1.节点确定，但边以概率p任意连接； 2.节点不确定，点边关系也不确定,2. 2随机网络,布朗运动,2. 2随机网络,随机网络的度分布服从泊松分布 平均度：k=p(N-1)p*N 平均路径长度Lln(N)/ln 聚类系数: C=p 1 (由于极度稀疏) 一般地，随机网络具有低的 聚集程度和小的平均距离。,2. 2随机网络,ER随机图作为实际复杂网络的模型存在明显的缺陷。 ER随机图理论一直是研究复杂网络拓扑的基本理论，其中一些基本思想在目前的复杂网络理论研究中仍然很重要。 可以参考Bollobás的著作。,2. 2随机网络,从多角度对ER随机图进行扩展以使其更接近真实的网络。 一个推广就是具有任意给定度分布的广义随机图（generalized random graph）。,2. 2随机网络,给定一个度分布P（k），它表示了网络中度为k的节点所占的比例。 基于这一分布按相同概率产生多个度序列为ki（i=1,2,.,N）的由N个节点组成的网络。 这些网络模型的集合称为配置模型（configuration model），详细介绍参见Newman的综述。,2.3 小世界网络,最近邻耦合网络具有高聚类特性，但平均路径长度较大； 随机网络具有小的平均路径长度，但却没有高聚类特性； 这两类网络模型都不能再现真实网络的一些重要特征。,2.3 小世界网络,毕竟大部分实际网络既不是完全规则的，也不是完全随机的。 是否存在一个同时具有高的集聚程度,以及小的最短路径的网络呢?,2.3 小世界网络,Watts和Strogtz于1998年引入了一个有趣的小世界网络模型，称为WS小世界模型，作为从完全规则网络向完全随机图的过渡。 发表在Nature上，常称为：WS model。,2.3 小世界网络,WS小世界模型构造算法如下： 1.从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右的各K/2节点相连，K是偶数。 2.随机化重连：以概率P随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。,2.3 小世界网络,对于传染病模型, 平均集聚程度对应于传播的广度,平均最短距离代表的是传播的深度。 因此,如果实际网络同时存在宽的广度和大的深度的话,在这样的网络上的传染病传播显然将大大高于规则网络与随机网络。,2.3 小世界网络,通过调节P的值就可以控制从完全规则网络到完成随机网络的过渡。,1.WS小世界模型,方法：Watts和Strogatz 发现,只需要在规则网络上稍作随机改动就可以同时具备以上两个性质。 改动的方法是,对于规则网络的每一个顶点的所有边,以概率p 断开一个端点,并重新连接,连接的新的端点从网络中的其他顶点里随机选择，如果所选的顶点已经与此顶点相连,则再随机选择别的顶点来重连。 形成机制： 规则网络以概率p 断开一个端点随机连接,当p=0时，对应的规则网络。两个节点间的平均距离线性地随N增长而增长，集群系数大 当p=1时，系统变为随机网络。对数地随N增长而增长，且集群系数随N减少而减少。 在p等于（0，1）区间任意值时，模型显示出小世界特性，约等于随机网络的值，网络具有高度集群性。,1.WS小世界模型,1.WS小世界模型,WS小世界模型的随机化重连过程：,WS小世界模型性质： 1.度与度分布 WS小世界由于没有改变原来网络的连线数目所以平均度仍为K，但是由于改变的旧线的连接方式，所以每个节点的度数不再保持常数。 WS小世界网络的度分布形态与随机网络的度分布形态相似。,1.WS小世界模型,1.WS小世界模型,2.WS小世界的平均路径长度 迄今还没有精确解析表达式。 不过，利用重正化群方法得到如下公式： 小世界网络的路径长度分布介于最小的路径长度1和最大路径长度N/2K之间，而且随着p的增长，路径长度分布的峰值越来越高。,1.WS小世界模型,1.WS小世界模型,2.NW小世界模型,WS小世界模型构造算法中的随机化过程有可能破坏网络的连通性。 另一个研究较多的小世界模型由Newman和Watts稍后提出的，称为NW小世界模型。 该模型是通过用“随机化加边”取代WS小世界模型 构造中的“随机化重连”而得到的。,2.NW小世界模型,NW小世界模型构造算法： 1.从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各k/2个节点相连，k是偶数。 2.随机化加边：以概率P在随机选取的一对节点之间加上一条边。其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。,2.NW小世界模型,NW小世界模型的随机化加边过程。,2.NW小世界模型,在NW小世界模型中： P=0对应于原来的最近邻耦合网络； P=1则对应于全局耦合网络。 理论分析，NW小世界模型要比WS小世界模型简单一些。当P足够小和N足够大时，NW小世界模型本质上等同于WS小世界模型。,2.NW小世界模型,3.小世界网络模型的统计性质,聚类系数：,3.小世界网络模型的统计性质,3.小世界网络模型的统计性质,4.社会小世界网络,在社会系统中，朋友或熟人关系网络是最基本的，也是研究比较深入的一种网络。 尽管人际关系网络及其庞大而又复杂，然而平均路径（average path length）则是相对短的。 另外，人际关系网络中大多数人都是他们邻居的朋友，表现出很高的集群性。,4.社会小世界网络,规则图中的最近邻耦合网络具有高聚类的特性但是不是小世界网络，在随机图中具有小世界性质但是不具有高聚类特性。两者都与实际的社会网络不一致，原因何在？ 人们发现，在熟人关系网络中，个别人偶尔会有几个远方的朋友。然而，这少数远方朋友的存在很可能根本改变网络的结构。,2.4无标度网络,随机网络中节点总数N是预先给定的，所以它们是静态的、固定的、平衡的网络，也有称为设计网络(designed network) 与此相对应，若网络模型的节点总数不是预先给定的，而是逐步增减的，则它们是动态的、增长的、非平衡的网络，或者称为演化网络(evolving network),2.4无标度网络(Scale-free network),随机网络和小世界网络的一个共同特征就是网络的连接度分布可近似poisson分布，该分布在度平均值处有一峰值，两侧呈指数快速衰减。 当k 时，度为k的节点几乎不存在。因此这类网络也成为均匀网络或指数网络。,2.4无标度网络(Scale-free network),许多复杂网络包括Internet、WWW、以及新陈代谢网络等的连接度分布函数具有幂律(power law)形式。 由于这类网络的节点连接度没有明显的特征长度，故称为无标(尺)度网络。,请同学们回忆什么是幂律分布？ 请同学们思考什么是特征长度？,2.4无标度网络(Scale-free network),特征长度（Characteristic length）是属于分形几何的概念。 对于某个物体, 特征长度通常是指该物体长度中有代表意义的长度, 如我们考察一个球体, 那么它的特征长度就是该球体的半径或直径。,2.4无标度网络(Scale-free network),普通几何学研究的对象，一般都具有整数的维数。比如，零维的点、一维的线、二维的面、三维的立体、乃至四维的时空。 在20世纪70年代末80年代初，产生了新兴的分形几何学（fractal geometry），空间具有不一定是整数的维，而存在一个分数维数。,2.4无标度网络(Scale-free network),自然界中的物体或图形, 要么具有特征长度, 要么不具有特征长度。 对于具有特征长度的物体, 只要其特征长度不变, 其性质就不会发生什么变化。 还有的事物没有特征尺度，就必须同时考虑从小到大的许许多多尺度（或者叫标度），这叫做“无标度性”的问题。,2.4无标度网络(Scale-free network),分开几何：,2.4无标度网络(Scale-free network),分形几何学的基本思想是：客观事物具有自相似的层次结构，局部与整体在形态、功能、信息、时间、空间等方面具有统计意义上的相似性，称为自相似性。 例如，一块磁铁中的每一部分都像整体一样具有南北两极，不断分割下去，每一部分都具有和整体磁铁相同的磁场。 这种自相似的层次结构，适当的放大或缩小几何尺寸，整个结构不变。,2.4无标度网络(Scale-free network),自相似性：,2.4无标度网络(Scale-free network),上世纪80年代初开始的“分形热”经久不息。分形作为一种新的概念和方法，正在许多领域开展应用探索。 美国物理学大师约翰·惠勒说过：今后谁不熟悉分形，谁就不能被称为科学上的文化人。 由此可见分形的重要性。,2.4无标度网络(Scale-free network),近年来，人们在互联网和人际关系网络等社会学网络的研究中都发现了“无标度”特性。 无标度网络中，大部分节点通过少数中心节点连接到一起，这就意味着节点在网络中的地位是不平等的，中心节点在连接网络完整性方面起更加重要的作用。,2.4无标度网络(Scale-free network),定义：无标度网络，是指网络中连通度的分布符合幂率分布，即P(k)k-r的网络，如图2-4 B所示。 这种分布说明，在无标度网络中大部分节点的连通度较低，但存在少数连通度非常高的节点使网络连接在一起。在这种网络中，平均连通度等标度已经不足以描述网络的规模和结构。,2.4无标度网络(Scale-free network),图2-4B无标度网络及其连通度分布和聚类系数函数趋势图 B为无标度网络，其连通度分布符合幂率分布，平均聚类系数函数曲线水平。,1.BA无标度网络,为了解释幂律分布(power law)的产生机理，Barabási和Albert提出了一个无标度网络模型，现在称为BA模型。 他们认为以前的许多网络模型都没有考虑到实际网络的两个重要特征。,1.BA无标度网络,实际网络存在两个重要特征： 1.增长特性（growth）：网络的规模不断扩大。,例如： 每个月都会有大量的生物信息学文章发表； WWW上则每天都有大量新的网页产生；,1.BA无标度网络,实际网络存在两个重要特征： 2.优先连接特性(preferential attachment)：新的节点更倾向于与那些具有较高连接度的“大”节点相连接，这种现象也称为“富者更富（rich get richer）”或“马太效应(Matthew effect)”。,例如：新发表的文章更倾向于引用一些被广泛引用的重要文献； 新的个人主页上的超文本链接更有可能指向新浪、雅虎等著名的站点。,1.BA无标度网络,1.BA无标度网络,BA无标度网络的构造： 基于网络的增长和优先连接特性，BA无标度网络模型的构造算法如下： 1.增长：从一个具有m0个节点的网络开始，每次引入一个新的节点，并且连到m个已存在的节点上，这里mm0；,1.BA无标度网络,BA无标度网络的构造： 2.优先连接：一个新节点与一个已经存在的节点i相连接的概率i与节点i的度为ki、节点j的度Kj之间满足如下关系（所有节点的度之和之间满足关系）：,1.BA无标度网络,经过t步后，该算法程序产生一具有N=t+m0个节点，mt条边的网络。,例: m0 = 3, m = 2,t = 1,t = 2,t = 3,1.BA无标度网络,1.BA无标度网络,BA模型提出了两条重要的网络演化机理：增长和择优。上述两个机理是不可缺少的， 如果将增长取消，网络中节点的数目保持不变而连线不断增加，最终网络中的节点相互连线则变成全局网络； 若将择优连接改为随机，则最终产生的随机网络。增长和择优两条机理同时成立才能产生无标度网络。,1.BA无标度网络,按照这种机制构建起的网络即可得到无标度网络。 例如，在互连网形成的初期，网络中的连接呈现随机特性，而当一个新的节点加入网络时，人们会倾向于访问已经具有一定知名度的网站，也就更有可能与这样的网页建立连接。,1.BA无标度网络,这样随着越来越多的节点引入网络，网络连接便呈现出无标度特性。 这个模型很好地解释了网页连接网络中少数权威网站存在的现象，也为生物分子网络中无标度特性的形成原因提供了很好的启示。,1.BA无标度网络,BA模型存在两点不明确： 1.初始网络没有确定，只是给出节点数目，但节点之间的连线没有阐明，如果假定是孤立节点，择优将无法进行，所以模拟总是从某个联通网络开始。 对于不同的初始网络，演化后的网络不同。,1.BA无标度网络,BA模型存在两点不明确： 2.当m=1时，连线只能一条一条加入，按照BA模型描述可能会出现重复连线，但是我们所讨论的网络不允许有重复连线。,1.BA无标度网络,不同的方法对演化的结果网络会有不同的影响。如何避免这种重复连线？ 为此，Bollábás给出了一个数学上严格的修正模型。但是这种模型已经改变了BA模型，这里不做介绍。,1.BA无标度网络,练习：初始网络含有两个节点，一条边，经过9步,构造BA模型，即m0=2,m=2,t=9.,1.BA无标度网络,1.BA无标度网络,真实网络,1.BA无标度网络,无标度网络的特性： 1.节点的数目不固定（增长性）：网络通过不断增加新的节点扩展。 例如：www每天有新的网页产生，科研引用每月也会有新的科研文章出现。,2.无标度网络特性,2.连接非均匀（优先连接特性）：新添加的节点倾向与度高的节点相连。 例如：新的网页更倾向与著名的网站（如网易, YAHOO, 淘宝等）链接；新发表的文章倾向引用重要的文章。,2.BA无标度网络特性-度分布,无尺度网络的度分布： 服从power law分布即幂率分布 P(k)k-。 Power law分布不同于Poisson分布和指数分布。没有固定的规模，因此称为无标度(scale free)。 服从此分布的网络称为scale free网络。,2.BA无标度网络特性-度分布,BA网络的度分布函数为：,这表明BA网络的度分布函数可由幂指数 为3的幂律函数近似描述。,2.BA无标度网络特性-度分布,2.BA无标度网络特性-度分布,自从BA模型被提出后，出现了推广BA模型的一个小高潮，原因是BA模型的度指数r是一个常数3，而大多数实际网络的度指数在（1，4）之间。,2.BA无标度网络特性-度分布,目前对BA无标度网络的度分布理论的研究主要有三种方法：连续场理论（continuum theory）、主方程法、速率方程法。 这三种方法得到的渐近结果都是相同的，其中，主方程法和速率方程法是等价的。,需要指出的是，对BA无标度网络模型的构造及 其理论分析的严格性等还存在一些不同的看法。,2.BA无标度网络特性-平均路径长度,BA无标度网络具有小世界特性，平均路径长度满足,这表明：无标度网络也具有小世界特性。,2.BA无标度网络特性-平均路径长度,2.BA无标度网络特性-聚类系数,BA无标度网络的聚类系数为：,这表明无尺度网络与ER随机图类似，当网络规模充分大时，无标度网络不具有明显的聚类特征,2.BA无标度网络特性-聚类系数,网络的平均聚类系数与网络大小,3.无标度网络VS随机网络,如果网络中节点间的连接完全是随机的，那么连通度的分布应该符合泊松分布或者在大尺度的情况下近似认为符合正态分布。 即度的分布比较均匀，大部分节点的连通度都与平均连通度相差不多，只有极少数节点具有很低或很高的连通度，如图1-3 A所示。,3.无标度网络VS随机网络,3.无标度网络VS随机网络,随机网络中直径或网络平均距离与节点的数目的对数成正比，即Llog(N)。对于包含大量节点的网络，其直径相对要小得多，任意两个节点间只需要较少的转接即可以连接在一起。 一方面网络中包含有大量节点和边，表现出“大世界”的景象，另一方面，连接任意节点间的距离却相对较小，呈现“小世界”的特征。这种“小世界”网络是复杂系统互作网络的共同特性，因此成为目前网络研究分析一个热点问题。,3.无标度网络VS随机网络,无标度网络对网络的另一个重要影响是使网络的直径相对较小，一般来说直径的大小正比于网络中节点数目的对数值的对数值即Llog(log(N)。 这就使无标度网络比一般小世界网络直径更小，联系更紧密。,A为随机网络，其连通度分布符合泊松分布，在大尺度情况下近似服从正态分布。B为无标度网络，其连通度分布符合幂率分布，平均聚类系数函数曲线水平。C为层次网络，其连通度分布与符合幂率分布，平均聚类系数与连通度的倒数成正比,3.无标度网络VS随机网络,随机网络可以用美国高速公路系统为代表，其中包含一些节点和随机布置的连接。在这种类型的网络中，节点度的分布将遵循钟形曲线分布。按照这种分布，大多数节点拥有的连接的数目都相差不多。,3.无标度网络VS随机网络,无标度网络：可以用美国航空网系统为代表，大部分机场都是小机场，但却存在少量连接众多小机场的非常大的机场（度非常大的节点）。因此在航空网络中大部分的节点都是度很低的节点，只存在极少的度高的节点。这样的网络成为非均匀的网络。,无标度网络小结：,无标度网络定义及特点 BA模型及构造算法 BA模型的特性 1.度分布 2.平均路径长度 3.聚类系数 无标度网络与随机网络的比较,无标度网络小结：,中枢节点出现 鲁棒性 脆弱性,思考题？,无标度网络模型具有哪些特性？ 真实网络中，若某些节点被攻击，会出现什么结果？,4.鲁棒性和脆弱性,引言故事：Achilles' Heel of the Internet,Achilles是古希腊传说中的一位杰出 英雄，身经百战，屡建功勋,据说，Achilles出生时也是一个极普 通的孩子，母亲倒提着他的身体放到 环绕地狱的冥河之中去浸泡，练就一 一副钢筋铁骨，任何凶恶的敌人也不 是对手。,但是，他的一只脚后跟 却因为握在 母亲的手里没有浸泡到冥河之中， 和普通人一样，成为英雄的致命弱点， 最后也死于此。,4.鲁棒性和脆弱性,4.鲁棒性和脆弱性,脆弱性：今天人们常常把系统的脆弱之处称为该系统的“Achilles踵”(Achilles' Heel).,4.鲁棒性和脆弱性,无标度网络服从power law分布即幂律分布； 在无标度网络中存在一个显著的特点就是网络中存在少数度很高的节点（远远超过平均度），这样的节点称为“Hub”；,4.鲁棒性和脆弱性,往往认为这样的节点在网络中具有重要的作用，在这样的节点周围存在保守的网络结构。,4.鲁棒性与脆弱性,这种幂律分布高度影响了网络的拓扑结构。 大多数hubs节点倾向于与度低的节点相连，而这些度低的节点倾向于与度更低的节点相连。,4.鲁棒性和脆弱性,4.鲁棒性和脆弱性,这种网络结构可以允许一些破坏行为。如果干扰随机的发生，网络中大多数的节点度很低，hub节点的数目很少，因此破坏hubs节点的概率很低。 即使hubs节点受到干扰，网络也会因为其他的hubs节点的存留而保留原来的拓扑结构。,4.鲁棒性和脆弱性,另一方面，如果将网络中的大部分hubs节点摘除，这样网络中就会出现一些孤立的点的图。 因此无尺度网络中的hubs节点高度影响网络的鲁棒性。,4.鲁棒性和脆弱性,假设给定一个网络，每次从网络中移走一个节点同时移走与该节点相连的所有的边，这样有可能使得网络中其他节点之间的一些路径中断。,4.鲁棒性和脆弱性,4.鲁棒性和脆弱性,如果网络节点之间存在多条路径，那么中断其中一些路径可能会使两上节点之间的距离变大，从而使整个网络的平均路径增大。,4.鲁棒性和脆弱性,如果移走少量节点后，网络中的绝大部分节点仍是连通的，那么称该网络的连通性对节点故障具有鲁棒性或者稳健性。,4.鲁棒性和脆弱性,4.鲁棒性和脆弱性,去除节点的两种策略： 1.随机故障策略：即完全随机地去除网络中的一部分节点； 2.蓄意攻击策略：即从去除网络中度最高的节点开始，有意识地去除网络中一部分度最高的节点。,4.鲁棒性和脆弱性,假设去除的节点数占原始网络中总节点数的比例为f，可以用最大连通子图的相对大小S和平均路径长度L与f的关系来度量网络的鲁棒性。,4.鲁棒性和脆弱性,当f较小时，随机选取的节点都是度很小的节点，除掉这些节点对整个网络的连通性不会产生大的影响。,4.鲁棒性和脆弱性,研究发现，ER随机图和BA无标网络之间存在极其显著的差异。 1.无标度网络对随机节点故障具有极高的鲁棒性：与随机图相比，最大连通子图的相对大小在相对高得多的f时才下降到零，而其平均路径长度的增长则要缓慢得多。,4.鲁棒性和脆弱性,这种无标度网络对随机故障的高度鲁棒性，来自于网络度分布的极端非均匀性，即绝大多数节点的度相对很小，而有少量节点的度相对很大。,4.鲁棒性和脆弱性,然而，正是这种非均匀性使无标度网络对蓄意攻击具有高度的脆弱性. 只要有意识地去除网络中极少量度最大的节点，就会对整个网络的连通性产生大的影响。,4.鲁棒性和脆弱性,无标度网络与随机网络的鲁棒性的形象比较： 1.即使随机去除网络中的大量节点，无标度网络仍可保持基本的连通性。而随机去除同样多的节点，则可使同样规模的随机网络分成多个孤立的子网。,4.鲁棒性和脆弱性,4.鲁棒性和脆弱性,4.鲁棒性和脆弱性,2.但蓄意去除少量度最高的节点就可破坏无标度网络的连通性。,例：以Internet为例，它的前身是20世纪60年代后期由美国国防部高级研究计划署（ARPA）研制的ARPANET。 目的之一是为了使得在一些子网和网关发生故障的情况下，网络还能维持基本的通信工作。,4.鲁棒性和脆弱性,4.鲁棒性和脆弱性,如今，Internet已经发展成为一个规模巨大的网络，并在人类社会生活中起着越来越重要的作用。 而Internet上每天都在发生各种各样的故障并经常受到黑客的攻击。,这种情况下，Internet能否保持它的功能无疑是一个重要的课题。 Albert、Jeong和Barabasi在文献中研究了两个实际网络对随机故障和蓄意攻击的鲁棒性。,4.鲁棒性和脆弱性,4.鲁棒性和脆弱性,一个是含有6000个节点的自治层Internet结构图; 另一个是含有326000个网页的WWW子网。,4.鲁棒性和脆弱性,他们得到了与BA无标度网络相类似的结果，从而进一步验证了对随机故障的鲁棒性和对蓄意攻击的脆弱性是无标度网络的一个基本特征，并且指出其根源在于无标度网络的度分布是不均匀性。,4.鲁棒性和脆弱性,对随机故障的鲁棒性和对蓄意攻击的脆弱性是无标度网络的一个基本特征,4.鲁棒性和脆弱性,事实上，近些年不同领域科学家的研究表明，“鲁棒但又脆弱（robust yet fragile）”是复杂系统的最重要和最基本的特征之一。,4.鲁棒性和脆弱性,Broder等人研究了更大规模的WWW子网的鲁棒性。他们发现只有删除所有度大于5的节点才能完全破坏其连通性。 由于有些节点的度高达几千，这就意味着要对整个网络实施猛烈的攻击，因此，他们认为该网络对蓄意攻击也具有很高的鲁棒性。,4.鲁棒性和脆弱性,Albert认为WWW对蓄意攻击是呈现脆弱性的，而Broder却认为具有很高的鲁棒性，这初看起来与Albert等人的结论似乎是矛盾的？ 其实不然，因为WWW具有高度倾斜的度分布，所以度数大于5的节点在整个网络中所占的比例还是很小的。,4.鲁棒性和脆弱性,Callaway和Cohen等人运用逾渗理论对网络的鲁棒性作了理论性分析。 Valente等人基于Callaway和Cohen等人的分析，推出对于随机故障和恶意攻击具有最优鲁棒性的网络中的节点的度最多只可能取自三个不同的值。,4.鲁棒性和脆弱性,Bollobas和Riordan则运用随机图理论对无标网络的鲁棒性和脆弱性作了数学分析。 Holme等人研究了基于介数的删除策略，其中一个节点的介数刻画了网络中经过该节点的最短路径的数目。,5.适应度模型,BA无标度网络模型的精彩之处在于它把实际复杂网络的无标度特性，归结为增长和优先连接两个非常简单明了的机制。 这很好地体现了科学研究中的从复杂现象提取简单本质的特点。,5.适应度模型,当然这也不可避免地使得BA无标度网络模型和真实网络相比存在一些明显的限制。 BA模型只能生产度分布幂律指数固定为3的无标度网络，实际网络的幂律指数则不尽相同，且大都属于2至3的范围内。,5.适应度模型,此外，实际网络常常具有一些非幂律特征。 因此，在BA模型的基础上，人们做了各种各样的扩展，其中一些重要的扩展模型都是通过修改BA模型中的优先连接方式而获得的。,5.适应度模型,2000年，Jeng等人在Nature上发表的文章中对43种生物体组织的新陈代谢过程加以研究，他们以各种基质（如ADP）为节点，以基质参与的某种化学反应为边构建了新陈代谢的复杂网络。 结果显示，这些网络的度分布都服从幂律分布，幂指数在2.02.4之间。,5.适应度模型,在BA无标度网络的增长过程中，节点的度也在发生变化并且满足如下幂律关系。,其中 是第i个节点在时刻t的度， 是第i个节点加入到网络中的时刻。,5.适应度模型,上式表明，在BA无标度网络中，越老的节点具有越高的度，那么实际网中也真是这样吗？,在BA无标度网络的增长过程中，节点的度也在发生变化并且满足如下幂律关系。,5.适应度模型,然而，在许多实际网络中，节点的度及其增长速度并非只与该节点的年龄有关。 有时是与节点的内在性质有关的，如个人的交友能力，WWW站点的内容和科研论文的质量等。,5.适应度模型,Bianconi和Barabasi把这一性质称为节点的适应度（fitness）。 据此提出了 适应度模型(fitness model). 并给出了该模型的构造算法。,5.适应度模型,其构造算法如下： 增长：从一个具有m0个节点的网络开始，每次引入一个新的节点并且连到m个已存在的节点上，这里mm0。每个节点的适应度按概率分布 选取 。,5.适应度模型,其构造算法如下： 优先连接：一个新节点与一个已经存在的节点i相连接的概率 ，与节点i的度ki，节点j的度kj和适应度之间满足如下关系:,5.适应度模型,可见，适应度模型与BA无标度模型的区别在于，在适应度模型中的优先连接概率与节点的度和适应度之积成正比，而不是仅与节点的度成正比。,5.适应度模型,这样，在适应度模型中，如果一个年轻的节点具有的较高的适应度，那么该节点就有可能在随后的网络演化过程中获取更多的边。,5.适应度模型,取决于适应度分布的形式，适应度模型表现出两类不同的行为，即：如果该分布具有有限支撑（finite support），那么与原始的BA模型一样，网络具有幂律分布。,5.适应度模型,如果该分布具有无限支撑（infnite support），那么应用度最高的那个点就会获得占整个网络总边数的一定比例的边数，后者是一种所谓的“赢者通吃(winner takes all)”的现象，类似于市场中的寡头垄断。,课堂小结,2.4无标度网络模型 鲁棒性和脆弱性 适应度模型 2.5局域世界网络演化模型,2.5局域世界演化网络模型,在诸多实际的复杂网络中存在着局域世界。 BA网络模型根据其优先连接概率公式来计算每一个节点的优先连接概率值，由此得到幂律分布形式的网络度分布。,2.5局域世界演化网络模型,然而， 在许多实际网络中，由于局域世界连接性的存在，每一个节点都有各自的局域世界，因而也只占有和使用整个网络的局部连接信息。,2.5局域世界演化网络模型,在某些网络中，因其存在着局域世界网络，其优先连接机制不是对整个网络，而是在每个节点各自的局域世界中有效，甚至于在人们的社团组织中，每一个人实际上也生活在各自的局域世界里。,2.5局域世界演化网络模型,在许多实际网络中，每个节点都有各自的局域世界，研究者们建立了局域世界演化网络（local-world evolving network）模型。 其构造算法包括增长和局域世界优先连接两步。,2.5局域世界演化网络模型,其构造算法如下： 增长：网络初始时有m0个节点和e0条边，每次新加入一个节点和附带的m条边。 局域世界优先连接：随机地从网络已有的节点中选取M个节点（ M m ），作为新加入节点的局域世界，新加入的节点根据优先连接概率来选择与局域世界中的m个节点相连。,2.5局域世界演化网络模型,其中LW是由新选择的M个节点组成。,局域世界优先连接：优先连接概率公式,2.5局域世界演化网络模型,在每一时刻，新加入的节点从局域世界M中按照优先连接原则选取m个节点来连接，而不是像BA无标度模型那样从整个网络中来选择。,2.5局域世界演化网络模型,构造一个节点的局域世界的法则依赖于实际不同的局域连接性而不同，上述模型中只考虑随机选择的简单情形。 显而易见，在t时刻,m Mm0+t ，因此上述局域世界演化网络模型有两个特殊情形：M=m和M=t+m0。,2.5局域世界演化网络模型,（1）特殊情形A ： M=m 这时，新加入的节点与其局域世界中所有的节点相连接，这意味着在网络增长过程中，优先连接原则实际上已经不发挥作用了。,2.5局域世界演化网络模型,（1）特殊情形A ： M=m