（计算机应用技术专业论文）基于有向复杂网络的节点失效对网络状态影响的研究.pdf

基于有向复杂网络的节点失效对网络状态影响的研究 摘要 随着人类社会的飞速发展，复杂网络已经融入到现代社会的方方面面。在 一些大规模的网络中，如i n t c r n e t 、电力网络中，单个或少数节点发生故障失效 会由于连锁反应而影响到网络中的其他节点，最终导致大规模的节点故障甚至 是网络崩溃。这种级联失效现象尽管不是经常发生，但旦发生则会在很大范 围内影响到网络的结构和性能。因此，对复杂网络中的节点失效所引发的级联 失效进行建模与分析具有重要意义。 本文首先在对当前一些典型的复杂网络模型进行比较的基础上，提出了一 个针对有向网络的加权复杂网络模型，通过理论分析和实验模拟，发现在该有 向加权复杂网络模型中，不论是节点的出入强度还是出入度，均服从幂律分布。 然后在上述有向加权网络模型的基础上，提出了一个节点的级联失效模型， 考察了不同属性的节点发生故障失效后对网络状态的影响。并在此基础上提出 了一个新的节点负荷再分配策略。实验结果表明，该策略可在一定程度上减缓 级联失效的产生，增加网络应对节点级联失效的鲁棒性。 关键词：b b v 网络；有向加权复杂网络；级联失效；负荷再分配 r e s e a r c ho ft h ei n f l u e n c eo fn o d ef a i l u r e t on e t w o r ks t a t u sb a s e dd i r e c t e dc o m p l e x n e t w o r k s a b s t r a c t a l o n gw i t ht h er a p i dd e v e l o p m e n to fh u m a ns o c i e t y , c o m p l e xn e t w o r k sh a v eb e e n a l l e s s e n t i a lp a r to fm o d e m s o c i e t y f o rs o m el a r g es c a l en e t w o r k s ，s u c ha si n t e r a c ta n dp o w e r 鲥d ，s o m en o d e sm a yb ea f f e c t e db yf a i l u r eo fo n e o raf e wn o d e sb e c a u s eo fc h a i nr e a c t i o n ， a n de v e n t u a l l yl a r g es c a l en o d e sb e c o m ei n v a l i de v e nt h ee n t i r en e t w o r km a yb ec o l l a p s e d a l t h o u g ht h i sp h e n o m e n o no fc a s c a d ef a i l u r er a r e l yh a p p e n e d ，b u ti fi td i d ，t h es t r u c t u r e a n df u n c t i o no fan e t w o r kw o u l db ei n f l u e n c e dt oal a r g ee x t e n t t h e r e f o r e ，i ti so fg r e a t i m p o r t a n c et om o d e la n di n v e s t i g a t et h ec a s c a d ef a i l u r ec a u s e db yn o d ef a i l u r ei nc o m p l e x n e t w o r k s i nt h i st h e s i s ，w ef i r s t l yi n t r o d u c es o m et y p i c a lc o m p l e xn e t w o r km o d e l s ，a n dt h e nw e p r o p o s eaw e i g h t e dc o m p l e xn e t w o r km o d e lf o rd i r e c t e dn e t w o r k s w eg e tt h ea n a l y t i c a l e x p r e s s i n go fp o w e r - l a wd i s t r i b u t i o no f b o t ho u t - i ns t r e n g t ha n do u t - i nd e g r e ei nt h i sm o d e l ， a n dt h en u m e r i c a ls i m u l a t i o ni si ng o o da g r e e m e n tw i t ht h ea n a l y t i c a le x p r e s s i o n f i n a l l y , w ep r o p o s eac a s c a d ef a i l u r em o d e lb a s e dt h ed i r e c t e dw e i g h t e dn e t w o r k m o d e la b o v e - m e n t i o n e d ，a n di n v e s t i g a t et h ee f f e c to fd i f f e r e n ta t t r i b u t e so fn o d e sf a i l u r et o t h en e t w o r ks t a t u s t h e nw ep r o p o s ean e ws t r a t e g yo fl o a dr e a l l o c a t i o n t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tt h es t r a t e g yc a ns l o wd o w nt h ec a s c a d ef a i l u r et os o m ee x t e n t ，a n d i n c r e a s et h er o b u s t n e s so fn e t w o r ka g a i n s tt h en o d ec a s c a d i n gf a i l u r e k e y w o r d s ：b b vn e t w o r k ；d i r e c t e dw e i g h t e dc o m p l e xn e t w o r k s ；c a s c a d ef a i l u r e ； l o a dr e a l l o c a t i o n n 插图清单 图2 1 几种规则网络6 图2 2e r 随机图网络7 图2 3w s 小世界模型8 图2 5n w 小世界模型9 图2 6b a 无标度网络模型的度分布1 1 图2 7 强度s 的分布情况1 4 图2 8 不同6 下c ( k ) 与k 的关系图1 4 图3 1 级联失效结束时g 与。的关系图1 7 图3 2 无标度网络( a ) 和自治层i n t e r n e t ( b ) 中的级联失效1 8 图3 3 均匀网络( 外图) 与非均匀无标度网络( 内图) 的级联失效比较1 9 图3 4 网络有最大连通子图的概率p g 与网络平均负荷 时，度为k 的节点几乎不存在。而1 9 9 9 年的一个 关于w w w 的研究却表明：w w w 基本上是由少数具有高链接数的页面串联起 来的，8 0 以上页面的链接数不到4 个，然而只占节点总数不到万分之一的极 少数中心节点( h u bn o d e s ) ，却具有高达上百万甚至更多的链接，整个网络的 的链接数分布具有幂律( p o w e r 1 a w ) 形式。由于这类网络的节点的连接度没有 明显的特征长度，故称为无标度( s c a l e f r e e ) 网络1 4 】。 为了解释幂律分布的产生机理，b a r a b d s i 和a l b e r t 予1 9 9 9 年提出了一个无 标度网络模型b a 模型【4 】。在b a 网络模型中，节点的度服从幂律指数在【2 ，3 】 之间的幂律分布。b a 无标度网络模型的提出，开创了复杂网络研究的新纪元。 自此，复杂网络的研究在b a 网络模型的基础上走向深入。 考虑到在复杂网络中，节点之间除了有无连接以及如何连接的关系之外， 还存在着连接的强弱问题，b a r r a t ，b a r t h 6 1 e m y 和v e s p i g n a n i 于2 0 0 4 年提出了 一个加权的复杂网络模型，称为b b v 模型【5 1 。在b b v 模型中，不仅节点的度 满足幂律分布特性，节点的权值及节点强度也同样满足幂律分布。 虽然b b v 模型将加权复杂网络的研究引入一个新的阶段，但是在现实生活 中，除了要考虑节点之间联系的强弱之外，还需要考虑这种联系的方向，如引 文网络，w e b 页面网络，i n t e r n e t 上的信息流网络等。在这些网络中，联系是有 明确方向并且可能并不对等的，因此，在考察这些网络时，除了考虑权值之外， 方向性的考虑也是十分必要的。而现阶段对于有向复杂网络的研究仍处于百家 争鸣，百花争放的阶段，还没有一个得到普遍认可的较具权威的有向复杂网络 模型出现，对有向复杂网络的研究仍有大量工作需要进行。 1 1 2 复杂网络中的基本概念 现实中的一个具体网络可以被抽象为一个图g 来进行描述，其中g ( v ，e ) ， v 为图中所有顶点的集合，e 为图中所有边的集合，每条边e e e 都有i e v ，je v 对应。如果任意点对( i ，j ) 与( j ，i ) 都对应同一条边，则称该图为无向图，所对应的 网络为无向网络，否则称为有向图及有向网络。如果e 中每条边都有相应的权 值，则称对应的网络为加权网络，否则称为无权网络。当然，无权网络也可看 成是每条边的权值都为1 的等权网络。 人们在刻画复杂网络结构的统计特性上提出了许多概念和方法，其中有三 个基本的概念是平均路径长度、聚类系数和度分布【6 1 。实际上最初w a t t s 和 s t r o g a t z 就是试图构造一种具有较小的平均路径长度( 与随机网络类似) 和较大 的聚类系数( 与规则网络类似) 的网络，最后得到了小世界网络模型。b a r a b d s i 和a l b e r t 所提出的b a 无标度网络模型则是用于刻画现实网络中度分布所具有 的幂律形式特性的。因此这三个概念在复杂网络的研究中起到了至关重要的作 用，接下来就对这几个概念做简单说明( 注：均针对无向网络) 。 l 平均路径长度( a v e r a g ep a t hl e n g t h ) 网络中两个节点i 和j 之间的距离d i j 定义为连接这两个节点的最短路径 上的边数。网络中任意两个节点之间的距离的最大值称为网络的直径，记为d ， 即 d = m a x 西 ( 1 一1 ) 网络的平均路径长度l 定义为任意两个节点之间的距离的平均值，即 p 南苓西 ( 1 - 2 ) 其中n 为网络节点数，d i j 为节点i 和j 之间的距离，为了便于数学处理， 2 在该公式中包含了节点到自身的距离( 当然该距离为零) ，如果不考虑节点到自 身的距离，那么则要在上式的右端乘以因子( n + 1 ) ( n 1 ) ，在实际的应用中，这 么小的差别是完全可以忽略不计的。一个有趣的发现是，在很多大规模的复杂 网络中，平均路径长度相对都很小，印使在节点间连接很稀疏的网络中情况也 是如此。由此可见，在复杂网络中是具有小世界效应的。 2 聚类系数( c l u s t e r i n gc o e f f i c i e n t ) 在社会网络中，我们常说“物以类聚，人以群分”，而实际的复杂网络在某 种程度上也具有类似特性，称之为聚类特性。般地，假设网络中的一个节点 i 有k i 条边将它与其他节点相连，这k i 个节点称为节点i 的邻居。显然，这k i 个节点也可能互为邻居节点，并且在这k i 个节点之间最多可能存在k i ( k i 1 ) 2 条边。将节点i 的k i 个邻居节点之间实际存在的边数e i 与总的可能的边数 k i ( k i 1 ) 2 的比值称为节点i 的聚类系数c i ，即 c i = 2 e i ( k i ( k 广1 ) )( 卜3 ) 整个网络的聚类系数c 就是所有节点i 的聚类系数c i 的平均值，即 c 2 专；。 ( 1 - 4 ， 其中n 为网络中的节点数。很明显，o c 1 。c = o 当且仅当所有的节点 均为孤立节点，c = i 当且仅当网络是全耦合的，即网络中任意连个节点之间都 有边直接连接。在很多类型的网络中，当n 一时，c = o ( 1 ) ，也就是说，当网 络规模足够大时，邻居节点互为邻居的概率会趋向某个非零常数。 3 度分布( d e g r e ed i s t r i b u t i o n ) 对于网络中的单个节点来说，度是非常重要的一个属性。节点i 的度是与 节点i 相关联的边的数目，记为k i 。网络中所有节点i 的度k 的平均值称为网 络节点的平均度，记为 。网络中节点的度的分布情况可用分布函数p ( k ) 来 描述。p ( k ) 表示的是随机选择的一个节点度恰好为k 的概率，也即度为k 的节 点占所有节点的比例。无标度网络中节点的度服从幂律分布，可用形如p ( k ) k 吖来描述。 1 2 复杂网络上的节点失效问题 对于复杂网络的研究并不仅仅局限于网络的静态结构，对网络中节点的动 态行为以及耦合节点之间的相互影响也是研究的一个重要方面。在很多实际网 络中，一个或少数几个节点或边发生故障( 这种故障有可能是随机发生的，也 可能是蓄意攻击造成的) 会通过节点之间的耦合关系引起其他节点的故障，最 终导致整个网络的崩溃。这种现象称为相继故障，也称为级联失效，有些文献 称之为“雪崩效应”。例如，在i n t e r n e t 中，对少数路由器进行病毒攻击会导致 路由器过载，迫使数据包重新路由，从而接连引起其他路由器过载，产生级联 失效【7 8 】。在电力网络中，断路器故障或是电站发电单元故障等经常会导致大 范围的停电事故。虽然这种大规模的级联失效事故不会经常发生，但是一旦发 生，往往具有极强的破坏力和影响力。例如，2 0 0 6 年1 1 月，由于德国有关方 面切断了两条高压线，造成欧洲电力网东部电力输出负荷过重，西部电力输入 不足，从而导致欧洲多个国家发生大规模断电事故，至少有千万人受到此次 断电事故的影响。除此之外，2 0 0 8 年席卷全球的金融危机也是在社会与经济网 络中发生类似雪崩效应的一个典型例子。 随着人们科技手段的提高，网络安全意识的增强，各种防范手段和工具在 一定程度上提高了网络的健壮性，可是大规模的网络故障仍时有发生。因此， 有必要对复杂网络上的级联失效的发生机理、预防与控制作深入的研究。同时， 需要考虑到网络的有向性，在有向复杂网络中考察单个节点失效对整个网络的 影响。在世界范围内，结合复杂网络对级联失效的研究还仅仅处于起步阶段， 因此，在有向复杂网络中研究节点的失效既具有一定的理论意义，也有现实意 义。 1 3 研究任务与论文内容安排 本课题主要研究内容是在阅读大量文献的基础上，提出一个新的加权有向 复杂网络模型，并对模型进行仿真验证。、然后在该模型的基础上，研究加权有 向复杂网络中的节点失效对整个网络状态的影响，比较了在不同的节点失效方 式下网络的有效性，同时提出了一种新的负荷再分配方式，并仿真验证了其有 效性。论文的内容将作如下安排： 第一章阐述了复杂网络的基本研究概况、基本概念以及论文的研究背景。 第二章系统概述复杂网络模型的研究情况，介绍了几种经典的有较大影响 力的复杂网络模型，如e r 随机网络模型，b a 模型，b b v 模型。 第三章概述了当前复杂网络级联失效的研究现状，介绍了几种已有的级联 失效模型，如负荷容量模型，沙堆模型和基于c m l 的相继故障模型等。 第四章提出了一个基于b b v 的加权有向复杂网络模型，详细介绍了该模型 的算法及理论验证，并从多方面进行仿真验证。 第五章在第四章所提出的有向复杂网络模型中考察了不同的节点失效方式 对网络的影响，提出了有向复杂网络中的节点失效模型，并仿真验证了一种新 的负荷分配方式对增强网络鲁棒性的效果。 第六章是对本课题所做工作的总结，并对今后的工作进行了展望。 4 2 1 引言 第二章复杂网络模型研究概述 现实世界存在着形形色色的网络，要理解这些网络结构与网络行为之间的 关系，并进而考虑改善网络的行为，就需要对实际网络的结构特征有很好的了 解，并在此基础上构建合适的网络结构模型。在复杂网络研究的进程中，人们 对网络的拓扑结构的认识经历了从简单到复杂，从不符合到越来越贴切的阶段。 从下一节开始，我们将认识几种典型的复杂网络模型。 2 2 几种典型的复杂网络模型 2 2 1 规则网络 几种经常研究的规则网络模型是全局耦合网络及其变形。 一、全局耦合网络 全局耦合网络模型如图2 - 1 ( a ) 所示。在全局耦合网络中，任意两个节点间 都有一条边直接相连。容易得知，在有n 个节点的该种模型中，网络拥有最小 的平均路径长度l = i 和最大的聚类系数c = i ，并且所有节点具有相同的度n 1 ， 节点之间完全无差别。虽然全局耦合网络很好地反映了许多真实世界网络的小 世界特性和聚类特性，但是实际网络往往是稀疏的，所包含的边数远远少于全 局耦合网络的n ( n - 1 ) 2 ，一般至多是o ( n ) ，并且节点之间也不可能完全相同。 因此，将该模型作为真实世界的网络模型显然具有很大的局限性。 二、最近邻耦合网络 最近邻耦合网络模型如图2 1 ( b ) 所示。与全局耦合不同的是，在该种网络 模型中，n 个节点排成环状，每一个节点只和它左右最靠近自己的“2 个邻居 节点相连，k 为偶数。最近邻耦合网络的聚类系数c = ( 3 k 3 ) ( 4 k 2 ) ，当k 足够大 时，c 3 4 ，因此，这样的网络是高度聚类的。然而，最近邻网络却并不满足 小世界特性，当n 一。o 时，该网络的平均路径长度l o 。 三、星型耦合网络 星型耦合网络模型如图2 1 ( c ) 所示。在该种网络模型中，有一个中心节点， 其余的n 1 个节点都只与这个中心节点连接，而它们彼此之间不连接。当n o o 时，星型耦合网络的平均路径长度l 一2 ，聚类系数c 一1 。这说明该种网络 模型同时具有小世界特性和聚类特性，用它来描述现实网络要比最近邻网络好， 但是现实网络显然并不具有精确的星形形状。 一。 图2 1 几种规则网络 ( a ) 全局耦合网络( b ) 最近邻耦合网络( c ) 星型耦合网络 2 2 2e r 随机网络 与完全规则网络相反的是完全随机网络，如前所述，一般认为最早提出随 机图网络的是两位匈牙利数学家e r d 6 s 和r 6 n y i 。他们发表了一系列关于随机 网络的文章，奠定了复杂网络模型研究的基础，所以将他们所提出的随机图网 络模型称为e r 模型。 如图2 - 2 ( a ) 所示，在e r 模型中，假设网络有n 个节点，每个节点对( i j ) 以相同的概率p 相连接，这样就可以得到包含约p n ( n 1 ) 2 条边的e r 随机图网 络。随机图理论的一个主要研究目标是：当概率p 为多大时，随机图会产生一 些特殊的属性? e r d 6 s 和r 6 n y i 研究发现，当概率p 达到或超过一个临界值p c ( 1 n n ) n 时，几乎所有的e r 随机图都是完全连通的。 不难发现，e r 随机网络的度分布服从二项分布： p ( k ) ：f ! 一11 ( 1 - p ) 一七一1 ( 2 - p ( 2 - 1 ) p ( k ) = i ，i ( ) “ 1 ) ，( 且其平均度 = p ( n 1 ) 。由于当n o o 时，二项分布近似于p o i s s o n 分布， 故对充分大的n ，( 2 1 ) 式可化为： v ( k ) - 芒；e “t ( 2 2 )= 一e 一7( 2 2 ) 庀! 故e r 随机图的度分布如图2 2 ( b ) 所示，在 处有一个峰值，然后呈指数 衰减。 设l r 为e r 随机网络的平均路径长度。对于在随机图中随机选择的一个节 点，网络中大约有 圳个其他的点与该点之间的路径长度等于或非常接近于 l r 。因此，n 圳，也即l r i n n i n 。这说明随即图网络的平均路径长 度与网络的规模的对数同阶。由于i n n 的值的增长随网络的规模n 的增长相对 很缓慢，这就使得即使规模很大的网络也可以有很小的平均路径长度，这种平 均路径长度以网络规模的对数增长的特性正是典型的小世界特征。 6 e r 随机图中两个节点之间不论是否具有共同的邻居节点，其连接概率均为 p 。因此，e r 随机图的聚类系数c 一- p = n k 。 ( 2 )随机化重连：以概率p 随机地重新连接网络中的每条边，即将边的一 个端点保持不变，而另一个端点取为网络中随机选择的一个节点。但是规定任 意两个不同的节点之间至多只能有一条边，且每个节点都不能与自身相连，即 网络中不含重复边和自环。 7 在上述模型中，通过随机化过程引入了大约p n k 2 条长程边，通过调节概 率p 的值就可以控制从完全规则网络到完全随机网络的过渡，如p = 0 对应于完 全规则网络，p - - 1 对应于完全随机网络。如图2 3 所示。 o 回移 p 2 0 _ p 2 l 图2 3w s 小世界模型 对于w s 小世界网络模型来说，其平均最短路径长度和聚类系数均可表示 成概率p 的函数，分别记为l ( p ) 和c ( p ) 。图2 4 显示了网络的聚类系数和平均 最短路径长度随重连概率p 的变化关系( 图中对两个值进行了归一化处理) 。由 图中可以看出，一个完全规则的最近邻耦合网络( 对应于p = o ) 是高度聚类的( c ( 0 ) 3 4 ) ，但是平均路径长度很大( l ( 0 ) - n 2 k i ) 。而当p 较小时，重新连线后 得到的网络与原始的规则网络的局部属性几乎相同，因此网络的聚类系数变化 也不大( c ( p ) c ( o ) ) ，但其平均路径长度却下降很快( l ( p ) k 。 ( 2 )随机化加边：以概率p 在随机选取的一对节点之间加上一条边，但是 任意两个不同的节点之间至多只能有一条边相连，且节点与其自身无连接。 在n w 小世界网络模型中，p = 0 对应于原来的最近邻耦合网络，p = l 则对 应于全局耦合网络。如图2 5 所示。 0 p = 0 p = l 图2 - 5n w 小世界模型 在理论分析上，n w 模型比w s 模型要简单一些，当p 充分小和n 充分大 时，n w 模型和w s 模型本质上是等价的。对n w 小世界网络，其度分布和聚 类系数【1 3 1 分别为： 9 毗，= ( - k ( 等广龟一等) - ”聊 c 2 埘 c ( p ) 。砸面3 ( 面k - 瓦2 ) 而 ( 2 9 ) 小世界网络模型在社会网络中是有根据的。比如在社会关系网络中，大部 分的人的朋友都是他们的邻居或同事，但另一方面，有些人也有一些远方的朋 友，甚至是远在异国他乡的朋友，这就是在w s 模型中通过重新连线或在n w 模型中通过加入新的连线所产生的长程连接。 2 2 4b a 无标度网络 前面所介绍的e r 随机图和小世界网络模型的一个共同特征就是网络的连 接度分布是均匀的，可以近似用p o i s s o n 分布来表示，这种分布在平均值处有 一峰值，然后呈指数衰减。具有这种指数衰减的连接度分布函数的网络也称为 指数网络。而近年的研究却发现，在很多现实的复杂网络中，如i n t e r n e t ，w w w ， 科研合作网络以及新陈代谢网络等的连接度的分布函数却具有幂律形式。由于 这类网络的节点的连接度没有明显的特征长度，故称为无标度网络。 为了解释幂律分布的产生机理，b a r a b d s i 和a l b e r t 提出了一个无标度网络 模型。在该模型中，他们考虑到了许多现实网络所具有的两个特征：增长性和 择优连接性。增长性表明网络的规模在不断的扩大，不断有新的节点连入原网 络。例如w w w 上每天都会有大量新的网页产生，每个月都会有大量的科研文 章发表。当新的节点进入原网络时，就改变了原网络的节点的连接数。优先连 接性是指新接入的节点与原网络节点连接的概率与原网络节点自身的连接数有 关，其原有连接数越多，成为目标节点的可能性越大。这种现象也称为“富者 愈富 现象。例如，新的网页更倾向于与y a h o o 等知名网站上已经包含了大量 链接的页面相连，新发表的文章也更倾向于引用一些已被广泛引用的重要文献。 b a 模型的建立就是节点不断加入原有网络的过程。具体的模型构造算法 如下： ( 1 ) 增长：从一个具有m o 个孤立节点的网络开始，每个演化时间步引入一 个新的节点加入到网络中，并让该新节点与原有的m ( m o ) 个节点相连。 ( 2 ) 优先连接：节点i 与新节点连接的概率i 与节点i 的连接度正向相关， 即设节点i 的度为k i ，在新节点与它相连的概率为： t 1 - i i = 再( 2 1 0 ) 厶勺 1 在时刻t ，网络中含有n = t + m o 个节点和m t 条边。网络的平均度为2 m 。 l o 利用平均场方法最后可得b a 无标度网络的度分布为： p ( k 卜2 t n z t 去 ( 2 1 1 ) 州n 十fe 。 由此式可知，b a 无标度网络的度分布服从幂律分布，幂律指数v 为3 ，且 独立于m 。此外，b a 无标度网络的平均晟短路径长度为 1 4 - 15 ： l 些!( 2 1 2 ) i o g l o g n 这表明该网络也具有小世界特性。 研究也同样得出了b a 无标度网络的聚类系数为： c 一絮等呻c 半一嘉，半 c z - 这表明与随机图模型一样，当网络规模充分大时，b a 无标度网络不具有 明显的聚类特性。 对于b a 无标度网络来说，最显著的特征是虽然从局部看网络中的节点和 边l ；直时都会变化，但在整体上节点的度分布却表现为一个简单的幂律函数形式， 函数中仅有一个参数v ，这个参数与网络的规模以及网络的边数都无关，与网络 的初始参数n l o 也无关。为了更加直观地了解b a 网络度分布的幂律特性，可将 数值仿真结果表示在双对数坐标下，则得到的是一条下降的直线，直线的斜率 体现了y 值的大小，如图2 - 6 所示。 2 25 b b v 加权网络 f r 妒 一 矿 矿 气广1 r 1 圉2 - 6b a 无标度网络模型的度分布 前面所介绍的几种网络模型，虽然在网络演化算法上各不相同，但针对的 都是无权网络，即不考虑网络中各个连接的相异性，也就是认为网络中各个节 点和各条边都是同等重要的。而在现实的很多网络中。如科研台作网络，根据 知名程度以及所做贡献的不同，各个学者在网络中的影响是不同的，也即权重 不同。因此，针对这种情况，b a r r a t ，b a r t h 6 l e m y 和v e s p i g n a n i 提出了一个边 和节点权值都动态演化的b b v 加权网络模型。由于下一章节将要介绍一个新的 基于b b v 的有向加权网络模型，故以下将对b b v 模型进行详细介绍。 在b b v 网络模型中，设w i j 为节点i ，j 之间的边权值且w i i w j i ，如果i ， j 之间无连接，则w i j = 0 ，i ，j = l ，2 ，n ，n 为节点总数。一个比较直观的例子是 世界航空网络( w a n ) ，w i i 代表两个机场i 和j 之间直通航班上的座位数，显然 i 和j 无直通航班时w i j = 0 。另设s i 为节点i 的强度( 或称为点权) 且有： s 产w 扩 ( 2 1 4 ) ，e r ( ，) 其中r ( i ) 为与节点i 相连的所有节点的集合。这样设定i 的权值( 或强度) 是 有依据的，还是以世界航空网络为例，s i 就与通过机场节点i 的总的旅客量相 关，并且也因此代表了机场节点i 的重要程度。 则b b v 模型的构建基于以下两点进行：拓扑增长和权值演化。具体步骤如 下： ( 1 ) 初始设定：初始网络是包含m o 个节点的全局耦合网络，并且节点之间 边的权值初始均设为w o 。 ( 2 ) 增长：每个时间步加入一个新节点1 1 ，1 1 与网络中原有的m ( m o ) 个节 点相连接，原有节点i 被选中与n 相连接的概率与i 自身的权值成正比，为： 兀= 旦 ( 2 1 5 ) 肛研 酊 j ( 3 ) 权值的动态演化：每次新加入的一条边( n ，i ) 初始均被赋予权值w o 。为 了简单起见，假设新加入的边( n ，i ) 只会局部引起i 以及i 的邻居节点j 的边权值 的动态调整。调整按照如下规则进行： w ，专w u + a w i ( 2 _ 1 6 ) 其中，aw i j 是与本地的动态演化相关的，可以是个与不同参数相关的函 数，如与权值w “相关，与i 的度k i 或是i 的强度s i 相关等等。不防设： w “ m i = 岛二 ( 2 1 7 ) j s i 6i 为给i 新增一条边给i 带来的额外的流量负担，简单起见，都设6i = 6 = l 。 而与i 相邻的各条边则会按照它们自身权值w i i 的大小来分担一定的流量。故同 时可得节点i 的强度调整为：s i s i + w o + 6j 。权值更新过后，进入下一个时间 步，加入新的节点，循环往复，直到达到设定的网络规模为止。 1 2 对于b b v 加权网络中的节点i 来说，当有新的节点1 1 加入到网络中时，i 有可能会从两个方面受到影响：一方面，节点i 以式( 2 15 ) 中的概率被选中与n 直接相连，则其度k i 增1 ，强度s i 增1 + 6 ；另一方面，i 的一个邻居节点j 被 选中与新节点n 直接相连，则i 的度不会发生变化，但是w i j 却会根据式( 2 - 1 6 ) 进行相应调整，根据式( 2 1 7 ) ，即i 的强度s i 会增加6w i j s j 。而s i 和k i 的这种动 态变化过程可用如下公式表示： 瓦d s _ f = 聊厕s i ( t ) ( 1 旧+ 磊，聊厨s j ( t ) 万丽w g ( t ) 堕：所盟( 2 1 8 ) d t e l 西( f ) 由于每添加一个新节点就会添加m 条边，则在时刻t 时的总的度数可以如 下近似表示：岛( r ) 2 r o t 。与此类似，每一条新添加的边将会让总强度增加 2 + 26 。故可得： 毋( f ) 2 m ( 1 + a ) t ( 2 - 1 9 ) 结合式( 2 18 ) 和( 2 - 1 9 ) ，可得 d s ，2 8 + 1 墨( f ) 一= 一 刃2 万+ 2t 堕：业 ( 2 2 0 ) 一= 一 二。 衍 2 ( 1 + 8 ) t 将上式结合初始条件设定k i ( t = i ) = s i ( t = i ) = m ，可得： 荆：m ( 三1 丽 ( 2 2 1 ) 颤力= 1 s , ( t ) 瓦+ 2 _ m 8 ( 2 - 2 2 ) 由于节点i 进入网络的时间是在【0 ，t 】上均匀分布的，因此，可以得到b b v 网络中的度分布可如下表示： 毗垆志f m 叫嘞以 ( 2 2 3 ) 其中，6 ( x ) 为d i r a cd e l t a 函数。结合式( 2 2 1 ) 、( 2 - 2 2 ) 可得，当t o o 时， b b v 网络的度分布p ( k ) - - - , k v 且有： v ：4 d + 3( 2 2 4 ) v = 一 二一 2 j + 1 由于强度s 和度k 是同阶成比例的，故同样也可得强度s 的分布为p ( s ) k 一，丫值同式( 2 2 4 ) 且根据参数万的不同取值在【2 ，3 之间。如果添加一条新边进 入网络的时候不会带来额外的流量负担( 6 - - o ) ，则该模型退化为y = 3 的b a 模型。 随着6 的增加，丫的值越来越靠近2 ，当6 呻o 。时，丫一2 。图2 7 为双对数坐 标下b b v 模型的度分布和强度分布情况，由图中可看出，它们的幂律指数是相 同的。而图2 8 则是聚类系数与度之间的相互关系。由图中可以看出，对于较 小的6 ，网络的聚簇系数较小并且c ( k ) 比较平坦。然而随着6 的增加，网络 聚簇系数随之增长并且呈现出幂律特性。 l 矿1 。、 罐 卜0 01 0 。 毒 l o 。 图2 - 7 强度s 的分布情况 取自文献5 】 0 猢i 口糊5 夺缸i a 越 十赫 睾1 0 k 图2 - 8 不同5 下c ( k ) 与k 的关系图 取自文献5 2 3 本章小结 这一章我们介绍了复杂网络模型的研究发展情况，对复杂网络模型的发展 1 4 过程中产生重要影响的几个网络模型进行了说明，包括：规则网络，e r 随机网 络，小世界网络和无标度网络，以及对加权网络研究有重要意义的b b v 网络模 型。对于模型的研究是复杂网络研究的重要一个方面，包括复杂网络的动力学， 传播学以及相继故障的研究等等，都必须基于一个特定的网络模型进行考察， 因此可以说，复杂网络模型的研究发展在一定程度上决定了复杂网络的研究进 程。 1 5 3 1 引言 第三章复杂网络中的级联失效研究概述 随着科技的进步和技术的提高，人们对网络的依赖性越来越强，现实生活 中也随处可见复杂网络的身影，如城市交通网，电力网，i n t e r n e t 等等。这些复 杂网络到底有多可靠，单个或是少量节点发生失效会不会导致整个网络的瘫 痪? 这个问题已经得到越来越多的关注。 以电力网为例，电力网络给人们带来极大的福音和便利，它具备了将电能 输送到数百、上千公里以外的能力，但不容忽视的一点是，电力网络上局部故 障的发生有可能会蔓延到很多区域甚至造成整个网络的崩溃。近年来，国内外 电力系统曾发生多次大规模的停电事故。1 9 9 6 年7 8 月，美国西部接连发生了 两次大停电事故，切断了西部1 1 个州超过4 0 0 万人的电力供应【1 7 】。2