第二章 网络拓扑基本模型及其性质.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 网络拓扑基本模型及其性质,2.1,引言,2.2,规则网络,2.3,随机图,2.4,小世界网络模型,2.5,无标度网络模型,2.6,局域世界演化网络模型,2.7,模块性与等级网络,2.8,复杂网络的自相似性,2.1,引言,要理解网络结构与网络行为之间的关系，并进而考虑改善网络的行为，就需要对实际的网络的结构特征有很好的了解，并在此基础上建立合适的网络结构模型。本章介绍几类基本的模型，包括规则网络、随机图、小世界网络、无标度网络、等级网络和局域世界演化网络模型。此外，进一步介绍复杂网络的模块化和自相似性等特征。,2.2,规则网络,在一个,全局耦合网络,中，,任意两个点之间都有边直接相连。,因此，全局耦合网络具有最小的,平均路径长度,L,gc,=1,和最大的,聚,类系数,C,gc,=1.,最近邻耦合网络,中每一个节点只和周围的邻居节点相连。具有周期边界条件的最近邻耦合网络包含,N,个围成一个环的点，其中每个点都与它左右各,K/2,个邻居节点相连，这里,K,是一个偶数。对于较大,K,值，最近邻耦合网络的,聚类系数,为：,C,nc,=,因此这样的网络是高度聚类的。然而，最近邻耦合网络不是一个小世界网络，相反对固定的,K,值，该网络的,平均路径长度,为：,L,nc,星形耦合网络,，它有一个中心点，其余的,N-1,个点都只与这个中心点连接，而他们彼此之间不连接。星形网络的,平均路径长度,为：,L,star,=,星形网络的,聚类系数,为,：,C,star,=,2.3,随机图,假设有大量的纽扣（,N1,）散落在地上，并以相同的概率,P,给每对纽扣系上一根线。这样就会得到一个有,N,个节点，约,pN(N-1)/2,条边的,ER,随机图的实例。,（,a,）,p=0,给定的,10,个孤立点；（,b,）,（,d,）分别以连接概率,p=0.1,、,p=0.15,和,p=0.25,生成的随机图,（,a,）（,b,）（,c,）（,d,）,随机图理论的一个,主要研究课题,是：当概率,p,为多大时，随机图会产生一些特殊的属性？,Erdos,和,Renyi,系统性地研究了当,N,时，,ER,随机图的性质与概率,p,之间的关系。他们采用如下定义：,如果当,N,时产生一个具有性质,Q,的,ER,随机图的概率为,1,，那么就称几乎每一个,ER,随机图都具有性质,Q,。,Erdos,和,Renyi,最重要的发现是,ER,随机图有如下的涌现或变相性质,：,ER,随机图的许多重要的性质都是突然涌现的，也就是说，对于任一给定的概率,p,，要么几乎每一个图都具有某个性质,Q,，要么几乎每一个图都不具有该性质。,ER,随机图,平均路径长度,为,:,L,ER,lnN/ln,。,这种平均路径长度为网络规模的对数增长函数的特性就是典型的小世界特征,。,ER,随机图的,聚类系数,是,:C=p=/NK,时，一个随机选取的节点的度为,k,的概率为：,而当,k=K/2,时有：,而当,kK/2,时,P(k,)=0,。,类似于,ER,随机图模型，,WS,小世界模型也是所有节点的度都近似相等的均匀网络。,2.5,无标度网络模型,2.5.1 BA,无标度网络,近年来在复杂网络研究上的另一个重大发现就是许多复杂网络，包括,Internet,、,WWW,以及姓陈代谢网络等的连接度分布函数具有幂律形式。由于这类网络的节点的连接度没有明显的特征长度，故称为,无标度网络,。,为了解释幂律分布的产生机理，,Barabasi,和,Albert提出了一个无标度网络模型，现被称为,BA,模型。他们认为以前的许多网络模型都没有考虑到实际网络的如下两个重要特性：,增长特性：即网络规模是不断扩大的。例如每个月都会有大量的新的科研文章发表，而,WWW,上则每天有大量新的网页产生。,优先连接特性：即新的节点更倾向于与那些具有较高连接度的“大”节点相连接。这种现象也被称为“富者更富”或“马太效应”。例如新发表的文章更倾向于引用一些已被广泛引用的重要文献，新的个人主页上的超文本链接更有可能指向新浪、雅虎等著名的站点。,基于网络的增长和优先连接特性，,BA,无标度网络模型的,构造算法,如下：,增长：从一个具有,m,0,个节点的网络开始，每次引入一个新的节点，并且连接到,m,个已存在的节点上，这里,m=m,0,。,优先连接：一个新节点与一个已经存在的节点,i,相连接的概率 与节点,i,的度,k,i,、节点,j,的度,k,j,之间满足如下关系：,在经过,t,步后，这种算法产生一个有,N=t+m,0,个节点、,mt,条边的网络。,BA,无标度网络的演化,(m=m,0,=2),1.,平均路径长度,BA,无标度网络的,平均路径长度,为：,这表明该网络具有小世界特性。,2.,聚类系数,BA,无标度网络的,聚类系数,为：,这表明与,ER,随机图类似，当网络规模充分大时,BA,无标度网络不具有明显的聚类特征,3.,度分布,BA,网络的,度分布函数,为：这表明,BA,网络的度分布函数可由幂指数为,3,的幂律函数近似描述。,2.5.2,鲁棒性与脆弱性,对于一个给定的网络，如果在移走少量节点后网络中的绝大部分节点仍是连通的，那么就称该网络的连通性对节点故障具有,鲁棒性,去除节点对网络连通性的影响,下面比较,ER,随机图和,BA,无标度网络的连通性对节点去除的鲁棒性。现考虑两种去除策略：一是随机故障策略，即完全随机地去除网络中的一部分节点；二是蓄意攻击策略，即从去除网络中度最高的节点开始，有意识地去除网络中一部分度最高的节点。假设去除的节点数占原始网络总节点数的比例为,f,，可以用最大连通子图的相对大小,S,和平均路径长度,l,与,f,的关系来度量网络的鲁棒性。研究发现，,ER,随机图和,BA,无标度网络之间存在极其显著的差异。无标度网络对随机节点故障具有极高的鲁棒性：与随机图相比，最大连通子图的相对大小在相对高得多的,f,时才下降到零，而其平均路径长度的增长则要缓慢得多。无标度网络的这种对随机故障的高度鲁棒性，来自于网络度分布的极端非均匀性：绝大多数节点的度都相对很小，而有少量节点的度相对很大。然而正是这种非均匀性使得无标度网络对蓄意攻击具有高度的脆弱性：只要有意识地去除网络中极少量度最大的节点就会对整个网络的连通性产生大的影响。,方块对应随机故障，圆点对应蓄意攻击,2.5.3,适应度模型,BA,无标度模型把实际复杂网络的无标度特性归结为增长和优先连接这两个非常简单明了的机制。但这也不可避免地使,BA,无标度网络模型和真实网络相比存在一些明显的限制。例如，,BA,模型只能生成度分布的幂律指数固定为,3,的无标度网络，而各种实际的复杂网络的幂律指数则不甚相同，而且大都属于,2,至,3,的范围内。此外，实际网络常常具有一些非幂律特征。,在,BA,无标度网络的增长过程中，节点的度也在发生变化并且满足如下幂律关系：,其中，,k,i,(t,),为第,i,个节点在时刻,t,的度，,t,i,是第,i,个节点加入到网络中的时刻。上式表明，在,BA,无标度网络中，越老的节点具有越高的度。然而在许多实际网络系统中，节点的度及其增长速度并非只与该节点的年龄有关。例如，社会关系网络中的某些人具有较强的交友能力，他们可以较为容易地把一次随机相遇变为一个持续的社会连接。显然，这些例子都是与节点的内在性质相关的。,Bianconi,和,Barabasi,把这一性质称为节点的适应度，并提出了,适应度模型,，其构造算法如下：,增长：从一个具有,m,0,个节点的网络开始，每次引入一个新的节点，并且连接到,m,个已存在的节点上，这里,m=m,），作为新加入节点的局域世界。新加入的节点根据优先连接概率,来选择与局域世界中的,m,个节点相连接，其中,LW,由新选的,M,个节点组成。,显而易见，在,t,时刻，,m=M1.1Nrand,i,。,网络模体检测示意图,2.7.2,等级网络,为了说明许多实际系统中同时存在的模块性、局部聚类和无标度拓扑特性，需要假设模块以某种迭代方式生成一个等级网络。研究表明，一些网络中的拓扑模块确实是按等级组织起来的。,等级模块性的一个最重要的量化标志是节点聚类系数服从幂律,C(k,)k,-1,。这表明度很小的节点具有高的聚类系数且属于高度连接的小模块。相反，度很高的,hub,节点具有低的聚类系数，其作用只是把不同的模块连接起来。需要注意的是，,ER,随机图和,BA,无标度网络都不具有等级拓扑；在这两类网络中节点聚类系数,C(k,),与该节点的度,k,无关。,2.7.3,超家族,小世界和无标度是许多实际网络的共同全局结构特征，那么不同德网络是否也有可能具有相似的局部结构特征？网络模体的研究有助于人们从局部结构上来理解复杂网络的设计原理。在此基础上，,Milo,等人提出了基于重要性剖面,(SP),比较网络局部结构的方法。计算,SP,的基本思想仍然是把一个实际网络与其对应的随机化网络作对比，这样就可避免不同网络的规模和度序列的影响。,网络中每个子图,i,的统计重要性用,来描述，其中,Nreal,i,和,Nrand,i,仍然分别表示该子图在实际网络和对应的随机化网络中出现的次数，,和,std(Nrand,i,),分别是,Nrand,i,的均值和标准方差。对,Z,i,作规范化处理就得到对应的,SP,i,：,研究表明，相同类型的网络不仅具有相同的网络模体，而且各个模体在网络中的相对重要性也是相似的。此外，一个网络超家族中可能包含着规模差异很大的功能极其不同的网络。,2.8,复杂网络的自相似性,左图中的等级网络看上去有一个非常明显的特征，那就是该网络的部分与整体具有很明显的相似性；而局部在某种意义上与整体相似，即自相似性，正是分型的一个基本特征。,与自相似性密切相关的一,个概念是分数维。计算自相似分形的维数的一种常用方法是盒记数法。该方法的基本思想是用边长为,l,B,的盒子来覆盖该图形，并统计完全覆盖该图形所需要的最少的盒子数,N,B,(l,B,).,这里的盒子在一位情况下是线段，二维情况下是正方形，三维情况下是立方体，,l,B,是盒子的尺寸。图形的维数的近似计算公式为：,等价地有幂律标度公式,一般情况下，在理论上只有当盒子尺寸,l,B,趋于零时，才能由公式等到维数的精确值。人们通常在对数坐标系中画出,N,B,(l,B,),和,l,B,之间的关系，拟合直线的斜率的负值就是,d,B,盒记数法用于复杂网络的只要困难是：对于大多数实际网络并不存在包含这些网络的自然地欧式空间，而且复杂网络上两个节点之间的距离，并不是指这两个节点之间的欧式距离，而是指连接这两个节点的最短路径包含的边的数目。也就是说，不能直接用上面介绍的欧式空间中的盒子来覆盖复杂网络。,Song,等人对于用于覆盖复杂网络的尺寸为,lB,的盒子的规定为：盒子中任意两个节点之间的距离都小于,l,B,。这样就可以把一个网络分割成一组布重叠的盒子，也就是说网络中的每一个节点都属于某个盒子，并且一个节点只能属于一个盒子。但是存在的问题是，对大规模的网络存在不同德分割方式，如下图所示。,在,l,B,=2,的情形下，一个包含,8,个节点的网络的两种分割方式,Song,等人进一步通过重整化过程，揭示出自相似性和无标度的度分布在网络的所有粗粒化阶段都成立。在把所有节点都分配到盒子中之后，再把每个盒子用单个节点来表示，这些节点称为重整化节点。如果在两个未重整化盒子之间至少存在一条边，那么两个重整化节点之间就有一条边相连。这样就等到一个重整化网络。这种重整化过程可以一直进行下去，直到整个网络被规约为单个节点。,一个包含,8,个节点的网络在不同的,l,B,情形下的重整化,重整化网络的度分布,P(k,),在重整化下具有不变性：,重整化网络中每个节点的度,k,与未重整化网络的每个盒子中的节点最大度,k,之间满足标度律：,经验观察表明，标度因子,s(1),与,l,B,之间满足具有幂指数,d,k,的幂律关系：,Song,等人还推出，在幂律度分布公式 中的幂指数 与幂律标度变换公式 和式 中的两个幂指数 和 之间存在如下的关系：,值得指出的是，对一个网络存在多种粗粒化方法。在一种粗粒化过程下具有自相似性的一个网络在另一种粗粒化过程下却可能具有非自相似性。,