（计算机应用技术专业论文）无尺度网络模型与相继故障研究.pdf

江苏大学硕士论文 摘要 无尺度网络研究正渗透到数理学科、生命学科和工程学科等众 多不同的领域，对于无尺度网络的定量与定性特征的科学理解已成 为网络时代科学研究中一个极具重要的挑战性课题。 在对无尺度网络的研究中，无尺度网络生成演化模型一直是研 究的重点和热点，目的就是为了更好的理解和模拟网络演化过程， 更好的理解网络结构与网络行为之间的关系，进而考虑有效的改善 网络行为。无尺度网络的相继故障，就是指一个或少数几个节点或 边发生的故障会通过节点之间的耦合关系引起其他节点发生故障， 这样就会产生连锁效应，最终导致相当一部分节点甚至整个网络的 崩溃，也形象的称为“雪崩”。为满足人们对各种关乎国计民生网络 安全性和可靠性的要求，有必要对无尺度网络相继故障的发生机理、 相继故障的预防与控制进行研究。 论文在深入分析现有无尺度网络演化模型和相继故障模型的基 础上，围绕局域世界演化网络改进模型和基于耦合映像格子的局域 世界演化网络相继故障进行研究，主要工作有： ( 1 ) 研究无尺度网络的基本拓扑概念及其性质，以及基于现实 网络性质和现象上的几个重要模型，在此基础上对原有局域世界演 化网络模型进行改进，目的使得改进后网络模型更好的模拟现实网 络的生长过程，主要从三方面进行改进：( 1 ) 引入增边和老边删除 重连机制；( 2 ) 引入节点度最大值控制机制；( 3 ) 引入局域规模增 江苏大学硕士论文 长机制。对于改进前后的模型进行相应的数学推理和模拟仿真，发 现改进后的网络模型在保持原有网络特性外，更加贴近于现实网络 的演化过程。 ( 2 ) 研究现有的一些相继故障模型，并在此基础上对于局域世 界演化网络的相继故障进行探讨，将基于耦合映像格子的相继故障 模型应用到局域世界演化网络，采用随机故障和蓄意攻击两种引发 相继故障策略对局域世界耦合映像格子进行研究。通过仿真发现局 域世界耦合映像格子对于蓄意攻击引发的相继故障比随机故障强烈 的多，并发现局域世界耦合映像格子的相继故障阂值比b a 无尺度网 络耦合映像格子的阂值小的多，说明局域世界演化网络模型相继故 障更容易发生。 关键词：无尺度网络，局域世界演化，耦合映像格子，相继故障， 优先连接 江苏大学硕士论文 a bs t r a c t r e s e a r c h 访s c a l e 一6 r e en e t v 旧r ki ss e e p 洫gi nt h em a t h e m a t i c a l ，l i f e s c i e n c e s ，e n 西n e e r i n ga n dm 御1 yo t h e rd i 彘r e n t d o m a i n s s c i e n t i f i c u u l d e r s t a n d i n go fq u a n t i t a t i v ea n dq u a l i t a t i v ef o rs c a l e 一仔e en e t 、v o r k b e c o m e sa ni m p o r t a n tc h a l l e n g i n gt o p i ci ns c i e n t i f i cr e s e a r c hi nn e t 、v o r k t i i n e i l lt 1 1 es t u d yo fs c a l e - 肌en e t w o 比t h ee v o i v i n gm o d e lo fs c a l e 一舭e n e t v 旧r ka l w a y sb e c o m e st h ek e yp o i n ta n dh o ts p o t t h eg o a lo f n e t w o r km o d e lr e s e a r c hi sm a 虹n gp 印o p l eb e t t e ru n d e r s 切n d i n ga 1 1 d s i n m l a t i n go nm en e 觚o r ke v o l v i n gp r o c e s sa n dt h er e l a t i o n s h i pb e t w e e n n e 觚o r ka r c 王l i t e c t u r ea r l db e h 乏l v i o r ，a n dt h e nc o n s i d e rt h ei 瑚【p o r 0 v e m e n t o i n e 咖r kb e e h a v i o rc o n s e q u e n t l y c a s c a d i n gf a i l u r eo fs c a l e - 舶e n e t 、v o r ki sd e f i n e da so n eo raf e wn o d e so rs i d e sf a i l u i i ew h i c h 、v i l ll e a d o m e rn o d e sf - a i l u r et h r o u g ht h ec o u p l i n gr e l a t i o n s ，a i l di tw i uc a u s et h e c h a i ne 舵c ta n dl o t so fn o d e sf a i l u r e ，e v e nt 1 1 ec o l l a p s eo fm ew h o l e n e t 、v o r k ，a l s ov i v i d l yc a l l e d “a v a l a i l c h e ”a sh u m a ns o c i 啊n e 似o r k i n g i n c r e a s i n g l y p e o p l eb e c o m em o r ea n dm o r es t r i c tw i t ht h es e c u r i t y 甜l d r e l i a b i l i t y o fs c a l e 一能en e t w o r k，a n da l s oh a v em a d el o t so f e 圩o r t s ，h o 、v e v e r l a 唱e s c a l ef a i l u r e ss t i l lo c c u rs o m e t i m e s t h e r e f o r e ，i ti s n e c e s s a 巧t 0d or e s e a r c hf o ro c c u r r e n c em e c h a l l i s m ，p r e v e n t i o na n d c o n t r o lo fc a s c a d i n gf a i l u r e i nt 1 1 eb e g i n n i n go ft h i st h e s i s ，t h eb a s i cc o n c e p to fs c a l e 一6 e e 江苏大学硕士论文 n e t w o r k ，s e v e r a li m p o r t a n tn e t w o r km o d e la n dc a s c a d i n gf a i l u r em o d e l a r es u m m a r i z e d ，a n dt h e nb a s e do nt h o s e ，s e c t i o nt 、v oi l l u s t a t e ss o h 炝 r e s e a r c hf o ri m p r o v e m e n to fl o c a l - w o r l de v o l v i n gn e t w o r km o d e la n d c a s c a d i i 培f a i l u r eo f l o c a l w o d de v o l v i i 培n e t w o r kb a s e do nc o u p l e dm 印 l a t t i c e n l em a i nw o r k sa r l di n n o v a t i v er e s u l t sa r el i s t e da sf 0 l l o w ： f i r s t l y ，i tw i l lr e s e a r c hi nt h eb a s i ct o p o l o g yc o n c e p ta n dp r o p e r t ) r o fs c a l e 一丘e en e t 、v o r k ，a n ds e v e r a li m p o r t a n tm o d e lb a s e do np r o p e r t y a n d p h e n o r n e n o n o fr e a l n e t 、o r k ，t h i e n b a s e d0 nt 量l o s es e v e r a l i m p r o v e m e n t sa r em a d ei n l el o c a l w o d de v o l v i n gn e t w o r km o d e l t h e g o a lo fi m p r o v e m e r 如i sm a l 洫gt h es i m u l a t i n go nt h ee v o l v i n gp r o c e s s o fn e t 、v o r kb e t t e r t h e ei m p r 0 v e m e n t sa r em a d ei nl o c a l - 、v 0 d de v o l v i n g n e t w o r km o d e l ：a d de 趣e ，d e l e t eo l de 起ea n dr e w i r em e c h a n i s m ；c o n t r o l m e c h a n i s mo fn o d ed e g r e e e ；l o c a l 一、r l di n c r e a s i n gm e c h a n i s m a n df o r t h ei m p r o v e dm o d e l ，m a t h e m a t i c a lr e a s o n i i l g 甜l ds i m u l a t i o na r ed o n e l a t e r e x p e r i m e n t a lr e s u l t ss h o wt 1 1 a ti m p r o v e d m o d e li sn o to n l y m a i n t a i n i n gm eo 喀n a lc t e ro fn e t w o r k a i s oc l o s et ot h er e a l i 哆o f n e “v o r ke v o l v i n gp r o c e s s s e c o n d l y ，i tw i l lr e s e a r c hi ns e v e 豫lc a s c a d i f l gf a i l u r em o d e l s ，a n d b a s e do nt h o s e ，w ew i l ld os o m er e s e a r c ho nc a s c a d i n gf a i l u r eo f l o c a l w o d d e v o l v i n gn e “v o r k i n c o n c l u s i o nl o c a l w o r l d e v o l v i n g n e t w o r kb a s e d o nc o u p l e dm a pl a t t i c ei sa d v a n c e da n dt w 0p o l i c i e sa r e u s e di nt t l e1 0 c a l w o r l de v o l v i n gc m l ：r a n d o mf a i l u r e sa n dd e i i b e r a t e l v 江苏大学硕士论文 a t t a c l ( s e x p 舐m e n t a lr e s u l t s s h o wt h a td e l i b e r a t e 酬- a c k s l e a d i i l gt o c a s c a d i n g f a i l u r e sa r ei n t e n st h a nr a n d o mf a i l u r e si nl o c a l w o r l d e v o l v i n gc l 儿，a n dt h r e s h o l do fl o c a l w o r l de v o l v i n gc 卫儿i ss m a l lt h a n b as c a l e 一丘e e s 触lo ft h o s es h o wm a ti t se a s yf o rl o c a l 一、砷r l de v o l v i n g n e t w o r km o d e lt oc a u s ec a s c a d i n gf a i l u r e k e y 舳劝s ：s c a l e 一舶en e t w o r k ，l o c a l 一、v o d de o l v i n g ，c o u p l e dm a p l a t t i c e ，c 2 u s c a d m gf i a i l u r e ，p r e f e r e n t i a lc o r m e c t v 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密圈，在年解密后适用本授权书。 不保密 学位做作者躲避午指导教师躲撕 w 督年f 月7 日k 哩年6 月日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文储硌左缝讳 日期：沙苫年i 月7 目 江苏大学硕士学位论文 1 1 研究背景 第一章绪论 地球上任意两个人之间通过多少个朋友才能互相认识? 万维网( w w w ) 上从一个页面 到另一个页面平均需要点击多少次鼠标? 层出不穷的计算机病毒是如何在互联网上传播 的? 各种传染病( 艾滋病，非典型肺炎和禽流感等) 是如何在人类和动物中流行的? 为什 么流言蜚语会散布得很快? 全球或地区性金融危机是如何发生的? 局部故障是如何触发 大面积停电事故的? 大城市的交通堵塞问题是如何引起的? 应该如何建立合理的公共卫 生与安全网络? 为什么大脑能够具有思维的功能? 这些问题尽管看上去各不相同，但每一 个问题中都涉及很复杂的网络，包括神经网络、嗍、i n t e r 凼t 、社会关系网络、经济网 络、电力网络、交通网络等等n 嘲。更为重要的是，越来越多的研究表明，这些看上去各不 相同的网络之间有着许多惊人的相似之处。 复杂网络理论所要研究的是各种看上去互不相同的复杂网络之间的共性和处理它们 的普适方法。从2 0 世纪末开始，复杂网络研究正渗透到数理学科、生命学科和工程学科 等众多不同领域，对复杂网络的定量与定性特征的科学理解，已成为网络时代科学研究中 一个极其重要的挑战性课题，甚至被称为“网络的新科学( n e ws c i e n c eo fn e t w o r k s ) ( 6 钉 o 1 9 9 8 年6 月，美国康奈尔( c o r n e l l ) 大学理论和应用力学系的博士生w a t t s 及其导师 s t r o g a t z 在n a t u r e 杂志上发表了题为“小世界”网络的群体动力行为的文章，进一步 揭示了复杂网络的小世界特性，并建立了一个小世界网络模型。由此开始了复杂网络的新 纪元，因为在很长时间内人们普遍认为网络生成过程是一个随机过程，生成的网络是随机 网络。 1 9 9 9 年l o 月，美国圣母( n o t r ed a m e ) 大学物理系的b a r a b a s i 教授及其博士生a l b e r t 在s c i e n c e 杂志上发表了题为随机网络中标度的涌现一文，揭示了复杂网络的无尺度 性质，并建立了一个无尺度网络模型。研究发现这种网络的度分布不像随机网和小世界网 那样是对称的泊松分布，而是幂律( p o w e rl a w ) 分布，也称为无尺度( s c a l e f r e e ) 分 布。因此这类具有幂律度分布，并且节点的连接度没有明显的特征长度的网络称为无尺度 网络。随着研究的深入，不同领域的研究者发现，很多网络都是由少数一些具有众多连结 的节点所支配的，某些社会领域、商业领域、好莱坞演员网络、生物学领城、细胞中蛋白 j 1 江苏大学硕士学位论文 质的交互网络也是无尺度的，事实上，科学家研究的网络越多，发现的无尺度结构也越多， 无尺度网络普遍存在于各个领域。如表1 1 所示： 表卜l 无尺度网络的例子嘲 网络节点连接 组织代谢参与消化食物以释放能量的分子 参与相同的生化反应 好莱坞演员出演同一部电影 因特网路由器光纤及其它物理连接 蛋白质调控网络协助调控细胞活动的蛋白质 蛋白质之间的相互作用 研究合作科学家合作撰写论文 万维网 网页连接地址 对于无尺度网络模型的研究主要是为了更好的模拟现实网络演化过程，理解网络结构 与网络行为之间的关系，其最终目的是通过研究结构来了解和解释基于这些网络之上的系 统运作方式，进而预测和控制网络系统的行为。在良好网络模型的基础上，有一类应用性 很强的网络行为研究已经日益引起人们的兴趣，如计算机病毒在计算机网络上的蔓延、传 染病在人群中的流行、谣言在社会中的扩散等等，实际上它们都是一种服从某种规律的网 络上的传播行为。传统的网络传播模型大都是基于规则网络的，有关无尺度网络模型的深 入研究研究使我们重新审视这一问题。 1 2 研究现状 要理解网络结构与网络行为之间的关系，并进一步考虑改善网络的行为，就需要对实 际网络的结构特征有很好的了解，并在此基础上建立合适的网络结构模型。从最早的欧拉 图和随机图，发展到当今最具有代表性的小世界效应( s 腿l l w o r l de f f e c t ) n 9 1 和无尺度 特性( s c a l e f r e ep r o p e r t y ) n 叫1 ，其中最具有代表性的模型有：队( b a r a b 6 s i a l b e r t ) 模型m 1 ，g l p ( g e n e r a li z e dl i n e a rp r e f e r e n c e ) 模型捌，适应度( f i t n e 毫sm o d e l ) 模型n 1 ， 局域世界演化网络( l o c a 卜w 0 r l de v 0 1 y i n gn e t w o r k ) 模型n 毛1 5 1 ，扩展无尺度网络模型 ( e x t e n d e ds c a 卜f r e em o d e l ，e s fm o d e ) n 司等。其中e r 随机图和w s 小世界模型的一个 共同特征就是网络的连接度分布可近似用p o i s s o n 分布来表示，该分布在度平均值 处 有一峰值，然后呈指数快速衰减。这意味着当k 时，度为k 的节点几乎不存在。这与 近年在复杂网络研究上发现许多复杂网络，包括i n t e r n e t 、w w w 以及新陈代谢网络等的连 接度分布函数具有幂律形式不符合，进而提出了对无尺度网络模型的研究。 在对无尺度网络模型的研究中，b a 模型考虑到了以前许多网络模型都没考虑到实际网 2 江苏大学硕士学位论文 络的增长和优先连接特性，但是对b a 无尺度网络模型的构造及其理论分析的严格性等还 存在一些不同看法n “，并且b a 模型只能生成度分布的幂律指数固定为3 的无尺度网络， 而各种实际复杂网络的幂律指数则不甚相同，且大都属于2 至3 的范围内。此外，实际网 络常常具有一些非幂律特征，如指数截断( e x p o n e n t i a lc u t o f f ) 、小变量饱和( s a t u r a ti o n f os 眦1 lv a r i a b l e s ) 等。因此，在b a 模型的基础上人们做了各种各样的扩展，其中一些 重要的扩展模型都是通过修改b a 模型中优先连接方式而获得的，如增加适应度影响因子 的适应度模型( f i t n e s sm o d e l ) 和局域世界中优先选择的局域世界演化网络模型 ( l o c a l _ w o r l de v o l v i n gn e t w o r k ) 。还有就是在增长过程中考虑到现实网络中会出现的一 些现象，如增边、老边删除重连等，提出了扩展无尺度网络模型e x t e n d e ds c a 卜f r e em o d e l ， e s fm o d e ) 。随着研究的不断深入和网络行为现象不断的被发现，新的网络模型还会不断 的被人们提出和应用。 。 有关无尺度网络研究的另一个重要问题，就是在结合更多实际网络特性的情况下，研 究更好模拟网络演化过程模型的基础上，研究相应的网络行为，相继故障( c a s c a d i n g f a i l u r e ) 就是一个重要研究课题，有时也称之为“雪崩( a v a l a n c h e ) n 朝。随着人类社 会日益网络化，人们对各种关乎国计民生网络的安全性和可靠性提出了越来越高的要求， 也作出了很多的努力，但是相继故障仍然时有发生。因此，有必要对相继故障的发生机理、 相继故障的预防与控制作深入的研究。其中相继故障的发生机理、相继故障的预防与控制 研究主要是基于动态模型的分析，先后出现的动态分析模型主要有：负荷一容量模型n 引， 二值影响模型2 ，沙滩模型胁1 ，最优潮流方法模型( o p am o d e l ) 嘲，c a s c a d e 模型州， 基于耦合映像格子模型砼5 1 等等。良好的相继故障动态分析模型的建立，将会为更好的研究 相继故障发生机理、预防和控制奠定良好基础。 1 3 研究内容 在深入研究无尺度网络演化模型以及现实网络行为特性的基础上，对原有局域世界演 化网络模型进行改进，以更好的描述和模拟网络的演化过程。在研究网络演化模型和相继 故障模型的基础上，将耦合映像格子相继故障模型引入局域世界演化网络模型，为进一步 研究相继故障的预防与控制，提高网络的安全性和可靠性奠定基础。论文的主要研究内容 包括以下两个方面： ( 1 ) 研究并改进局域世界演化网络模型 江苏大学硕士学位论文 相对于早先出现的小世界网络和无尺度网络其它模型，局域世界演化网络模型充分考 虑在许多现实的网络中，由于局域世界连接性的存在，每一个节点都有各自的局域世界， 因而也只占有和使用整个网络的局部连接信息，而不是整个网络的连接信息。不过，该模 型并未考虑到现实网络生成过程中老边的删除及重连，对节点最大值的控制等网络生成行 为特性。所以，论文在此基础上提出边可删除重连的局域世界演化网络模型和节点度可控 的局域世界演化网络模型，并考虑局域世界的线性增长，使其更好地模拟网络的演化过程， 为局域世界演化网络的相继故障研究提供模型支持。 ( 2 ) 基于耦合映像格子的局域世界演化网络相继故障研究 在广泛研究各种无尺度网络演化模型和相继故障模型的基础上，利用局域世界演化网 络模型，将耦合映像格子引入到局域世界演化网络拓扑结构中，着重考虑两种引发相继故 障的策略，即随机故障和蓄意攻击，探讨外部扰动的强度对于网络故障规模的影响，以及 局域世界耦合映像格子引发相继故障的阈值，对于进一步研究相继故障的预防与控制，提 高网络的安全性和可靠性提供了必要的条件。 1 4 论文组织安排 本文共分五章展开叙述： 在本章中，介绍论文的研究背景，对无尺度网络研究状况作了简要说明，阐述了课题 的研究现状和主要研究内容，最后说明论文的行文结构安排。 第二章，简要介绍了无尺度网络的出现及发展；接着对无尺度网络的统计特性、网络 特性及应用前景进行介绍；接着，介绍几种无尺度网络基本拓扑模型；最后阐述了常见的 一些相继故障模型。 第三章，在原有局域世界演化网络模型基础上，以现实网络中的行为特性为依据，对 模型进行改进，提出了有边可删除重连的局域世界演化网络模型和节点度可控的局域世界 演化网络模型，并且考虑了局域世界的线性增长，并对改进前后的网络模型进行仿真对比。 第四章，将耦合映像格子引入到局域世界演化网络拓扑结构中，对局域世界网络中的 相继故障进行研究。 第五章，总结全文，给出结论。并且叙述了本领域内有待于进一步研究和探讨的问题。 4 江苏大学硕士学位论文 2 1 无尺度网络 2 1 1 复杂网络 第二章无尺度网络及演化模型 复杂性科学是用以研究复杂系统和复杂性的一门方兴未艾的交叉学科，复杂性科学研 究的复杂系统涉及的范围很广，包括自然、工程、生物、经济、管理、政治与社会等各个 方面：它探索的复杂现象从一个细胞呈现出来的生命现象，到股票市场的涨落、城市交通 的管理、自然灾害的预测，乃至社会的兴衰等等，目前，关于复杂性的研究受到了世界各 国科学家们的广泛关注。1 9 9 9 年，美国科学杂志出版了一期以“复杂系统”为主题的 专辑，这个专辑分别就化学、生物学、神经学、动物学、自然地理、气候学、经济学等学 科领域中的复杂性研究进行了报道。由于各学科对复杂性的认识和理解都不一样，所以该 专辑避开术语上的争论，采用了“复杂系统”这个名词。概括起来，复杂系统都有一些共 同的特点，就是在变化无常的活动背后，呈现出某种捉摸不定的秩序，其中演化、涌现、 自组织、自适应、自相似被认为是复杂系统的共同特征嘲。 随着计算机数据处理和运算能力的飞速发展，科学家们发现大量的真实网络既不是规 则网络，也不是随机网络，而是具有与前两者皆不同的统计特征的网络，其中最重要的是 小世界效应( s i i l a l 卜w o r l de f f e c t ) 和无尺度特性( s c a l e f r e ep r o p e r t y ) 。这样的一些 网络被科学家们叫做复杂网络( s c a l e f r e en e t w o r k s ) ，对于它们的研究标志着第三阶段 的到来。 遗憾的是，就目前而言，科学家们还没有给出复杂网络精确严格的定义，从这几年的 研究来看，之所以称其为复杂网络，大致上包含以下几层意思：首先，它是大量真实复杂 系统的拓扑抽象；其次，它至少在感觉上比规则网络和随机网络复杂，因为可以很容易地 生成规则和随机网络，但就目前而言，还没有一种简单方法能够生成完全符合真实统计特 征的网络；最后，由于复杂网络是大量复杂系统得以存在的拓扑基础，因此对它的研究被 认为有助于理解“复杂系统之所以复杂”这一至关重要的问题。 一般而言，网络系统的复杂性体现在以下几个方面嘲： ( 1 ) 结构复杂性 网络连接结构看上去错综复杂、极其混乱。而且网络连接结构可能是随时变化的，例 江苏大学硕士学位论文 如，w w w 上每天都不停的有页面和链接的产生和删除。此外，节点之间的连接可能具有不 同的权重或方向。例如，神经系统中的突触有强有弱，可以是抑制的也可以是兴奋的。 ( 2 ) 节点复杂性 网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统。例如，基因网络 和j o s e p h s o n 结阵列中每个节点都具有复杂的时间演化行为。而且，一个网络中可能存在 多种不同类型的节点。例如，控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质 和酶。 ( 3 ) 各种复杂性因素的相互影响 实际的复杂网络会受到各种各样因素的影响和作用。例如，耦合神经元重复地被同时 激活，那么它们之间的连接就会加强，这被认为是记忆和学习的基础。此外，各种网络之 间也存在密切的联系，这使得对复杂网络的分析变得更为困难。+ 例如，电力网络的故障可 能会导致i n t e r n e t 流量变慢、金融机构关闭、运输系统失去控制等一系列不同网络之间 的连锁反应。 复杂网络发展过程中出现的三种基本网络拓扑：规则网络、随机图和小世界网络模型。 ( 1 ) 规则网络 从演化规则、平均路径长度( a v l ，a v e r a g ep a t hl e n g t h ) 、聚类系数( c c ，c l u s t e r i n g c o e f f i c i e n t ) 等几个方面对常见的几种规则网络进行对比例，具体如表2 一l 所示： 表2 1 常见几种规则网络对比 名称定义a v l c c 全局耦合网络任意两个点之问都有边相连 l g c 2 l c g c _ l 僖o b a l l yc o u p l c dn 咖呔) 最近邻耦合网络每一个点只和他周围的邻居 k = 尝_ q = 黼a 三 ( n 他蜘n e i g i l b o rc o u p l c d节点相连，( 本表设定为i 沈 ( n 一一) n c m o r n个邻居节点) 星形耦合网络有一个中心节点，其余的n 1 k = 2 筹告坨 ，一。1 l ”一 ( s t a rc o u p i e dn c t w o 暾) 个点都只与中心节点连接，它 ( n 一一)( n 一一) 们彼此之间不连接 ( 2 ) 随机图 e r d o s 和髓n y i 于4 0 多年前开始研究的e r 随机图模型，通过e r 随机图模型生成随 机网络，过程如下：网络从拥有n 个孤立的点开始，以相同的概率p 给每对节点连接一条 6 江苏大学硕士学位论文 边，最终将生成一个有n 个节点，约p n ( n 1 ) 2 条边的e r 随机图网络。 e r 随机图的平均度是 = p ( n 1 ) p n 。设l e r 是e r 随机图的平均路径长度。直观上， 对于e r 随机图中选取的一个点，网络中大约有l 个其他的点与该点之间的距离等于 或非常接近于l e r 。因此有，n o c l 且，即l e r o c l n n 1 n 。这种平均路径长度为网络 规模的对数增长函数的特性就是典型的小世界特性。 e r 随机图中两个节点之间不论是否具有共同的邻居结点，其连接概率均为p 。因此， e r 随机图的聚类系数是c = p = n l ，这就意味着大规模的稀疏e r 随机图没有聚类特性。 不过，实际的复杂网络的聚类系数比相同规模的e r 随机图的聚类系数高得多。 固定e r 随机图的平均度 不变，则对于充分大的n ，由于每条边的出现与否都是独 立的，e r 随机图的度分布可用p o i s s i o n 分布来表示啪1 ： 。 尸( 七) ：( ? ) p t ( 1 一p ) 。二学 ( 2 1 ) 其中，对固定的k ，当n 趋于无穷大时，最后的近似等式是精确成立的。因此e r 随机图也 称为“p o i s s i o n 随机图 。 尽管e r 随机图作为实际复杂网络的规模存在明显的缺陷，在2 0 世纪的后4 0 年代中， e r 随机图理论一直是研究复杂网络拓扑的基本理论，其中的一些基本思想在目前的复杂网 络理论研究中仍然很重要。 ( 3 ) 小世界网络模型 规则网络和随机网络模型都不能再现真实网络的一些重要特征，毕竟大部分实际网络 既不是完全规则，也不是完全随机的，从而推动着小世界网络模型的出现，这种网络的特 点就是既具有较短的平均路径长度又具有较高的聚类系数。在对小世界网络模型的研究 中，有两个典型的演化模型：w a t t s 和s t r o g t z 于1 9 9 8 年提出的的w s 小世界模型脚1 ；n e w m a n 和w a t t s 稍后提出的，被称为n 1 】l 小世界模型1 。 小世界网络模型可以形象的解释朋友关系网络的一种特性，即大部分人的朋友都是和 他们住在同一条街上的邻居或在同一个单位工作的同事。小世界网络模型的一些统计性质 如表2 2 所示： 江苏大学硕士学位论文 表2 2w s 小世界模型和n 1 | 小世界模型对照 w s 小世界模型n w 小世界模型 聚类系 c ( p ) = 黼”p ) 3c ( 加必k 一鬻p + 2 ) 数( c c ) 平均路 地) = 警厂( 脚2 )地) = 警( 脚2 ) 径长度 舢为普适标度函数 删志a r c t a n 压 ( a v l ) 厂( 甜) = 蹴篙1 三 ，“l 厂( x ) 3 n 2 圳4 ，洲 度分布当k k 2 时有：在模型中，每个节点的度至少为k 。 ( p ( k ) ) m i n ( i 一足，2 。r ，2 当k k ，一个随机选取的节点的度的 尸( 七) = ( ：彪) ( 1 一p ) “p 刖2 一 暑o 概率为： 一( 丛2 ) 一r 7 。一雎，2 m ) = 岛) 争雠( 1 一争“ ( 七一( k 2 ) 一刀) ! 当k k 时，p ( 蛉印 当k 堪沈时，p ( k 间 2 1 2 无尺度网络 在无尺度网络中，存在着鲁棒性与脆弱性共存现象洲，也就是说无尺度网络的连通性 对节点去除的鲁棒性，依据不同的去除策略而有着惊人的不同：对于随机故障，即完全随 机去除网络中的一部分节点，该网络有着极高的鲁棒性；对于蓄意攻击策略，即从去除网 络中度最高的节点开始，有意识的去除网络中一部分度最高的节点，网络则具有高度的脆 弱性。主要因为，无尺度网络度分布的极端非均匀性：绝大数节点的度都相对很小，而有 少量节点的度相对很大。 集散节点的存在，让我们认识到了以前的网络理论尚未涉及的问题：各种复杂系统具 有相同的严格结构，都受制于某些基本的法则，这些法则似乎可同等地适用于细胞、计算 机、语言和社会。更迸一步，认识这些法则，会帮助我们解决一系列重要问题，包括开发 更好的药物、防止黑客侵人互联网、阻止致命流行病的传播等等。 2 1 2 1 无尺度网络统计性质 近年来，人们在刻画无尺度网络结构的统计特性上提出了很多概念和方法，其中有五 8 江苏大学硕士学位论文 个基本的概念：平均路径长度( a v l ，a v e r a g ep a t h1 e n g t h ) 、聚类系数( c c ，c l u s t e r i n g c o e f f i c i e n t ) 、度分布( d e g r e ed i s t r i b u t i o n ) 、网络弹性( n e t w o r kr e s i l i e n c e ) 和介 数( b e t w e e n e s s ) 。下面主要是对它们进行简单解释。 ( 1 ) 平均路径长度( t h ea v e r a g ep a t hl e n g t h ) 网络研究时，一般定义两节点间的距离为连接两者的最短路径的边的数目：网络的直 径为任意两点间的最大距离；网络的平均路径长度则是所有节点对之间距离的平均值，它 描述了网络中节点间的分离程度，即网络有多小。网络中两个节点i 和j 之间的距离d u 定义为连接这两个节点的最短路径上的边数。网络中任意两个节点之间的距离的最大值称 为网络的直径( d i 鲫e t e r ) ，记为d ，即 d = m a x 以 ( 2 - 2 ) j ， 网络的平均路径长度l 定义为任意两个节点之间的距离的平均值，即 上= r 二一略 主( 十1 ) 眨 ( 2 3 ) 其中n 为网络节点数。网络的平均路径长度也称为网络的特征路径长度( c h a r a c t e r i s t i c p a t l ：i1 e n g t h ) 。 b a 无尺度网络的平均路径长度为瞰瑚1 ： l o c ! ! 璺型( 2 4 ) l 0 9 1 0 9 表明该网络也具有小世界特性。 ( 2 ) 聚类系数( t h ec l u s t e r i n gc o e f f i c i e n t ) 聚集系数c 用来描述网络中节点的聚集情况，即网络有多紧密，比如在社会网络中， 你朋友的朋友可能也是你的朋友或者你的两个朋友可能彼此也是朋友。一般地，假设网络 中的一个节点i 有k ；条边将它和其它节点相连，这k 。个节点就称为节点i 的邻居。显然， 在这k 。个节点之间最多可能有k 。( k ；一1 ) 2 条边。而这k 。个节点之间实际存在的边数e t 和总 的可能的边数k 。( k 。一1 ) 2 之比就定义为节点i 的聚类系数c 。，即 c ：= 2 巨( 毛( t 1 ) ) ( 2 5 ) 整个网络的聚类系数c 就是所有节点i 的聚类系数c 。的平均值。很明显， 0 c l 。c = o 当且仅当所有的节点均为孤立节点，即没有任何连接边；c = 1 当且仅当网络 9 江苏大学硕士学位论文 是全局耦合的，即网络中任意两个节点都是直接相连。对于一个含有n 个节点的完全随机 的网络，当n 很大时，c = o ( n i ) 而许多大规模的实际网络都具有明显的聚类效应，它们的 聚类系数尽管远小于l ，但却比0 ( n _ ) 要大得多嘲。事实上，在很多类型的网络( 如社会关 系网络) 中，你的朋友的朋友同时也是你的朋友的概率会随着网络规模的增加而去即当n 一时，c = o ( 1 ) 。这就意味着这些实际的复杂网络并不是完全随机的。b a 无尺度网络的聚 类系数为啪1 ： c ：型陋( 盟) 一上】丛丝 ( 2 6 ) 4 r 朋一1 ) 。、坍!m + 1 。f 表明与e r 随机图类似，当网络规模充分大时b a 无尺度网络不具有明显的聚类特性。 ( 3 ) 度分布( t h ed e 弘e ed i s t r i b u t i o n ) 图论中节点i 的度k 。为节点连接的边的总数目，所有节点i 的度k 。的平均值称为网络的 平均度，定义为 。网络中节点的度分布用分布函数p ( k ) 来表示，其含义为一个任意选 择的节点恰好有条边的概率，也等于网络中度数为的结点的个数占网络结点总个数的比 值。常见的度分布有完全随机网络度分布为p o i s s o n 分布，以及无尺度网络的幂率分布， 也叫无尺度分布。无尺度网络的度分布可以用幂率形式p ( k ) o c k l 来更好的描述。常见的两 种度分布如图2 一l 所示： 图2 一l 常见的泊松分布和幂律分布 ( 4 ) 网络弹性( t 舶r kr e s i l i e n c e ) 网络的功能依赖其节点的连通性，称网络节点的删除对网络连通性的影响为网络弹 性，其分析有两种方式：随机删除和有选择的删除，前者称为网络的鲁棒性分析，后者称 为网络的脆弱性分析。a 1 b e r t 等人分别对度分布服从指数分布的随机网络模型和度分布服 从幂律分布的b a 网络模型进行了研究，结果显示i 随机删除节点基本上不影响b a 网络的 平均路径长度，相反，有选择的删除节点后，b a 网络的平均路径长度较随机网络的增长快 l o 江苏大学硕士学位论文 得多。这表明，b a 模型相对随机网络具有较强的鲁棒性和易受攻击性。出现上述现象的原 因在于幂律分布网络中存在的少数具有很大度数的节点在网络连通中扮演着关键角色，一 般也称它们为h u b 节点。 ( 5 ) 介数( b e 拥e e n e s s ) 介数分为边介数和节点介数n 町。节点的介数为网络中所有的最短路径中经过该节点的 数量比例；边的介数含义类似。介数反映了相应的节点或者边在整个网络中的作用和影响 力，具有很强的现实意义。例如，在社会关系网络或技术网络中，介数的分布特征反映了 不同人员、资源和技术在相应生产关系中的地位，这对于在网络中发现和保护关键资源和 技术具有重要意义。 2 1 2 2 无尺度网络特性 无尺度网络具有集散节点的马太效应和网络鲁棒脆弱共存的网络特性，通过了解无尺 度网络的特性，可能导致许多领域出现新的应用。例如，电脑科学家可能据此设计出更有 效的策略，以保护因特网免受电脑病毒的侵害。 ( 1 ) 集散节点的马太效应 大部分节点只有少数几个连结，而某些节点却拥有与其他节点的大量连结，这些具有 大量连结的节点称为“集散节点 ，所拥有的连结可能高达数百、数千甚至数百万。由此 看来，这一特性似乎能说明网络是无尺度的。 成长性和优先连结这两种机制，有助于解释集散节点的存在：当新节点出现时，它们 更倾向于连结到已经有较多连结的节点，随着时间的推进，这些节点就拥有比其他节点更 多的连结数目。这种“富者逾富 的过程，有利于早期节点，它们更有可能成为集散节点。 优先连结的机制常常是线性的。换句话说，如果一个现存节点的连结数是其相邻节点 连结数的两倍，那么新节点与它连结的可能性，也是与邻近节点连结可能性的两倍。美国 波士顿大学的r e n d e r 及同事研究了不同类型的优先连结，他们发现。如果这种机制运行 得比线性更快( 例如，一个节点的连结数是另一个的两倍，而新节点连接到前者的可能性 却是后者的4 倍) ，那就容易出现一个攫取最多连结的集散节点，在这种“赢者通吃”的 情况下，网络最终演变为拥有一个中心集散节点的星型拓扑结构。 ( 2 ) 鲁棒性与脆弱性共存 无尺度网络的另一重要特性就是对随机节点故障具有极高的鲁棒性，但对蓄意攻击具 有高度的脆弱性。随机网络中若有较大部分的节点被去除，网络必然溃散成彼此无法通讯 江苏大学硕士学位论文 的