（运筹学与控制论专业论文）复杂网络的演化及传播模型研究.pdf

摘要 摘要 近年来复杂网络已成为学术界研究的焦点课题之一。复杂网络的演化模型 和复杂网络上病毒传播的免疫与控制问题是复杂网络研究的两个重要研究方 向。在过去的几年里，学者们作了大量的实证研究，提出了许多反映真实网络 演化特征的网络演化模型、反映真实网络中病毒传播与控制的病毒传播模型以 及复杂网络中病毒传播的各种控制策略，包括预防、免疫、杀毒、隔离等各种 实际的应对措施，并在这两大研究中取得了重要的成果。但这些成果与我们的 实际要求相比，还只能算是冰山的一角，还有许多需要研究和解决的问题。本 文主要是在这两个研究方向中做了进一步的研究工作，具体工作与创新点如下： 1 关于无标度网络的演化机制问题，根据朋友网络的演化特征，提出了一 个“朋友机制”网络演化模型，并对该模型的主要性质进行了理论分析与数值仿 真，理论分析与仿真结果都表明：该模型的生成方法简单，不需要掌握网络中 节点度的信息，所生成网络的平均聚集系数比著名的b a 网络模型更接近于真实 社会网络的特征。该演化模型可为真实网络的演化共性及模型分析提供一些参 考和借鉴； 2 结合真实网络中常见的“富者愈富 现象及网络中度的几何均值性质， 提出了设计通用型无标度网络模型的一种新方法，该方法可以生成满足任意幂 律指数要求的无标度网络，对设计满足其它特征的无标度网络模型具有一定的 参考价值： 3 提出了一个最大传染能力限定的病毒传播模型，得出了一个新的与传统 病毒传播模型不同的结论。通过对该模型的理论分析与数值仿真，都证明了在 最大传染能力限定的无限大无标度网络上，病毒传播阈值是存在的；同时，作 者也分析了最大传染能力限定下非零传播阈值与有限规模网络下非零传播阈值 的本质区别。其理论分析方法也可为其它病毒传播模型的分析提供可用的借鉴 与参考。 4 提出了一种新的病毒传播静态免疫策略一随机游走策略，与目标免疫策 略不同的是：该策略并不需要网络中节点度的任何信息，也能达到与目标免疫 策略相近的免疫效果。 摘要 5 提出了不相关指数网络中病毒传播的一个动态控制模型一s g i r 模型。在 免疫强度与当前网络中感染个体的密度线性相关的条件下，作者对病毒的传播 阈值和病毒对网络的感染程度进行了理论分析和数值仿真，得到的结论是：与 没有动态控制的传统病毒传播模型相比，s g i r 模型可以使网络的感染程度大大 降低。尽管作者所提出的动态控制模型带有一定的条件限制，使得模型在普适 性方面还有一定的局限性，但相信作者所提出的理论分析方法可以为相关研究 内容提供一定的借鉴与参考。 6 提出了不相关复杂网络上一个带有隔离机制的病毒传播动态控制模型。 该模型与前一个动态控制模型有很多类似的地方，例如模型的分析方法和所得 结论都很相近，但相比之下该模型更接近于真实情况，因为该控制模型是建立 并应用于无标度复杂网络、而不是指数网络上的。模型中所运用的理论分析方 法也可为相关研究内容提供一定的借鉴与参考。 关键词：复杂网络，小世界网络，无标度网络，网络演化模型，病毒传播模型， 免疫策略与控制 a b s t r a c t a b s t r a c t c o m p l e xn e t w o r kh a sb e c o m eo n eo ft h em o s tc o n c e r n e dr e s e a r c h e si ns c i e n t i f i c c i r c l e s t h ee v o l v i n gm o d e l so fc o m p l e xn e t w o r k s t h ee p i d e m i cc o n t r o la n d i m m u n i z a t i o ns t r a t e g yo fd i s e a s e so nc o m p l e xn e t w o r k sa r et w oi m p o r t a n tr e s e a r c h s u b j e c t s i nt h ep a s tf e wy e a r s ，r e s e a r c h e r so ft h ef i e l dh a v ec a r r i e do u tc o n s i d e r a b l e p r a c t i c a ls t u d i e so nt h et w os u b j e c t sa n dp r o p o s e dm a n yn e t w o r ke v o l v i n gm o d e l s w h i c hm a yr e f l e c tt h ee v o l v i n gf e a t u r e so ft h er e a lw o r l dn e t w o r k s ，a tt h es a m et i m e ， v a r i o u sk i n d so fe p i d e m i cs p r e a d i n gc o n t r o lm o d e l sa n di m m u n i z a t i o ns t r a t e g i e s o n n e t w o r k sh a v ea l s ob e e np r o p o s e di n c l u d i n gp r e v e n t i v em e a s u r e s ，i m m u n i z i n go r q a u r a n t i n i n gt h ei n d i v i d u a l s ，k i l l i n gt h ev i r o u se t c a l t h o u g hm a n yi m p o r t a n tr e s u l t s h a v e b e e na c h i e v e d ，c o m p a r e dw i t ht h ed e m a n dt oa b s t r a c ta n dd e s c r i b ep r e c i s e l yo f t h ee v o l u t i o n so fr e a ln e t w o r k sa n dt h es p r e a d i n gb e h a v i o ro fd i s e a s e so nt h e m ，t h e o b t a i n e dr e s u l t sc a no n l yb ev i e w e da sat i po fi c e b e r gi nt h er e s e a r c h t h e r ea r es t i l la l o to fp r o b l e m st ob es t u d i e da n ds o l v e d n l ep a p e rm a i n l yd e a l sw i t ht h ea b o v et w o s u b j e c t sa n dt h em a i nw o r ki ss u m m a r i z e da sf o l l o w s ： 1 o nt h e e v o l v i n g m e c h a n i s m so fs c a l e f r e en e t w o r k s a “f r i e n d s h i p m e c h a n i s m o fn e t w o r ke v o l v i n gm o d e li sp r o p o s e da c c o r d i n gt ot h ee v o l v i n gf e a t u r e o ft h ef r i e n d s h i pn e t w o r k t h em a i np r o p e r t i e so ft h em o d e la r ea n a l y z e d t h e o r e t i c a l l ya n dn u m e r i c a l l yb ys i m u l a t i o n s t h er e s u l t ss h o wt h a tt h ee v o l v i n g m e t h o di sv e r ys i m p l e ：o n ed o e sn o tn e e dt ok n o wt h ed e g r e ei r a f o r m a t i o no fn o d e so f t h ec u r r e n tn e t w o r ka st h a to ft h ef a m o u sb an e t w o r km o d e l ，b u tt h ec h a r a c t i s t i co f t h ea v e r a g ec l u s t e rc o e f f i c i e n to ft h ee v o l v e dm o d e li sm o r ec l o s et ot h er e a ls o c i a l n e t w o r k sc o m p a r e dw i t ht h a to ft h eb am o d e l t h en e wm o d e lm a yp r o v i d es o m e u s e f u le x p e r i e n c e sf o r t h ea n a l y s i so ft h ec o m m o nc h a r a c t e r so fr e a lw o r l dn e t w o r k s a n dn e t w o r km o d e l s 2 c o m b i n e dw i t ht h ec o m m o n “r i c hg e t t i n gr i c h e r p h e n o m e n o no ft h er e a l w o r l dn e t w o r k sa n dt h eg e o m e t r i c a lp r o p e r t i e so fs c a l e f r e en e t w o r k s ，an o v e l a p p r o a c ho fd e s i g n i n gs c a l e f r e en e t w o r k si sp r o p o s e d t h ea p p r o a c hc a np r o d u c e s c a l e f r e en e t w o r k sw i t ha n yr e q u i r e dp o w e r l a wd e g r e ed i s t r i b u t i o n s ，w h i c hm a y o f f e rs o m eu s e f u le x p e r i e n c e sf o rd e s i g n i n gg e n e r a ls c a l e f r e en e t w o r km o d e l s i i i a b s t r a c t 3 a ne p i d e m i cs p r e a d i n gc o n t r o lm o d e lw i t hf i n i t es p r e a d i n ga b i l i t yi sp r o p o s e d ，a n da d i f f e r e n tc o n c l u s i o nf r o mt h ec l a s s i c a le p i d e m i cs p r e a d i n gm o d e l si s g i v e n b y t h e o r e t i c a la n dn u m e r i c a la n a l y s i st ot h en e wm o d e l ，i ti sp r o v e dt h a tt h ee p i d e m i c t h r e s h o l do fad i s e a s eo ni n f i n i t es c a l ef r e en e t w o r k se x i s t su n d e rt h ec o n d i t i o nt h a t t h en e t w o r k sh a v eaf i n i t es p r e a d i n ga b i l i t t y a tt h es a m et i m e ，t h en a t u r a ld i f f e r e n c e s o ft h en o n - z e r oe p i d e m i ct h r e s h o l d sb e t w e e nt h ef i n i t es c a l ef r e en e t w o r k sa n dt h en e t w o r k s w i t hf i n i t es p r e a d i n ga b i l i t yw e r ea l s oa n a l i z e d t h em e t h o dp r o p o s e dm a yp r o v i d es o m e e x p e r i e n c e sf o rt h ea n a l y s i so fo t h e re p i d e m i cs p r e a d i n gm o d e l s 4 an o v e ls t a t i ce p i d e m i ci m m u n i z a t i o ns t r a t e g y r a n d o mw a l ks t r a t e g yi s p r o p o s e d c o m p a r e dw i t ht h et a r g e t e di m m u n i z a t i o ns t r a t e g y , t h en e ws t r a t e g y p r o p o s e dd o e sn o tn e e da n yi n f o r m a t i o no ft h en e t w o r k ，y e ti t se f f e c t i v e n e s si sv e r y c l o s et ot h a to ft h et a r g e t e di m m u n i z a t i o ns t r a t e g y 5 ad y n a m i c a le p i d e m i cc o n t r o lm o d e l s g i rm o d e lo nt h eu n c o r r e l a t e d e x p o n e n t i a ln e t w o r k si sp r o p o s e d u n d e rt h ec o n d i t i o nt h a tt h ei n f e c t i o ns t r e n g t hi s 1 i n e a r l yr e l a t e dt ot h ed e n s i t yo ft h ei n f e c t e dn o d e si nt h ec u r r e n tn e t w o r k ，t h e e p i d e m i ct h r e s h o l do ft h em o d e ia n dt h ei n f e c t i o u sa b i l i t yo f ad i s e a s et ot h en e t w o r k a r ea n a l y z e dt h e o r e t i c a l l ya n dn u m e r i c a l l y t h er e s u l t ss h o wt h a tt h es g i rm o d e lc a l l c o n s i d e r a b l yr e d u c et h ei n f e c t i o no ft h ed i s e a s e st ot h en e t w o r k s e v e nt h o u g ht h e c o n c l u s i o ni so b t a i n e du n d e rs o m ec o n d i t i o n ，w h i c hm a yl i m i tt h eg e n e r a l i t yo ft h e m o d e l ，t h ea u t h o rb e l i v e s t h a tt h ea n a l y s i sm e t h o dp r o p o s e dm a yd r a ws o m e i m p o r t a n te x p e r i e n c ef o ro t h e r s t ot h es t u d yo nt h ed y n a m i c a le p i d e m i cc o n t r o l m o d e l s 6 ad y n a m i c a le p i d e m i cc o n t r o lm o d e lw i t hq u a r a n t i n i n gm e c h e n i s m - q s i r m o d e lo nu n c o r r e l a t e dc o m p l e xn e t w o r k si sp r o p o s e d t h em o d e li ss i m i l a ri nm a n y a s p e c t st ot h es g i rm o d e lp r o p o s e di nt h ea b o v es t u d y , s u c ha st h ea n a l y s i sm e t h o d a n de v e nt h ef i n a lc o n c l u s i o n s h o w e v e r ，c o m p a r e dw i t ht h es g i rm o d e l ，q s i r m o d e li sb a s e do nt h ec o m p l e xs c a l e f r e en e t w o r k s ，b u tn o to nt h ee x p o n e n t i a lo r h o m o g e n e o u sn e t w o r k s ，w h i c hi s m u c hc l o s e rt or e a ls i t u a t i o n s t h et h e o r e t i c a l m e t h o dp r o p o s e di nt h em o d e lm a ya l s od r a ws o m ei m p o r t a n te x p e r i e n c ef o ro t h e r s r e l a t e ds t u d i e s k e yw o r d s ：c o m p l e xn e t w o r k ，s m a l l w o r l dn e t w o r k ，s c a l e f r e en e t w o r k ，n e t w o r k e v o l v i n gm o d e l ，e p i d e m i cs p r e a d i n gm o d e l ，i m m u n i z a t i o ns t r a t e g ya n dc o n t r o l i v 南开大学学位论文版权使用授权书 本入完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：攀6 p ， 州罗年，月 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 各密级的最长保密年限及书写格式规定如下： 内部5 年( 最长5 年，可少于5 年) 秘密l o 年( 最长1 0 年，可少于1 0 年) 机密2 0 年( 最跃2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 砌孑年r 月 日 第一章绪论 第一章绪论 我们的世界是一个充满了各种各样复杂网络的世界。从i i l t e m e t 到w w w 网、 从大型的电力网到复杂的交通运输网、从生物的大脑神经网到各种新陈代谢网、 从科研合作网到各种各样的经济网、政治网、社会关系网就连我们书写文 章所用的语言也是由语法串连起来的文字网。作为探索复杂系统拓扑结构、系 统功能与行为的有效工具，复杂网络的研究已经引起了国际科学界的高度重视， 近年来己成为了数理科学、生命科学、社会科学、技术科学及各种交叉学科研 究的热点，对复杂网络进行定量与定性特征的科学理解是当今科学界一个极为 重要的挑战性课题i l 以2 。 本章内容是这样安排的：第1 1 节简要介绍复杂网络研究的进展情况和主要 研究内容：第1 2 节介绍复杂网络的定义以及与本文研究内容相关的几个复杂网 络特征量的定义及性质；第1 3 节介绍几个复杂网络模型及其主要特征，其中第 1 3 5 4 , 节将涉及本文研究的两个网络演化模型的介绍；第1 4 节介绍两个传统的 病毒传播模型及其传播性质、几个主要的病毒免疫与控制策略，并在该节中每 小节的最后部分，介绍本文将要研究的相关内容。 1 1复杂网络研究概况 人们通常把1 9 9 8 年w a t t s 和s t r o g a t z 发现了小世界网络( s m a l l w o r l d n e t w o r k ) 以及19 9 9 年b a r a b 6 s i 和a l b e r t 发现了无标度网络( s c a l e f r e en e t w o r k ) 作为兴起复杂网络研究的标志，虽然只有短短的十年时间，但其所涉及的研究 内容与研究领域之广泛、其潜在的应用价值和不断出现的新成果正吸引着越来 越多的人加入到这个研究队伍中来。 1 1 1 复杂网络研究进展 网络在数学上也叫图。1 8 世纪著名数学家欧拉( e u l a r ) 首次提出了图的概 念，他把“哥尼斯堡( k o n i g s b e r g ) 七桥问题抽象为由节点和边组成的图，将 实际问题转化成了一种数学问题来求解。图的意义是不言而喻的，因为真实世 界中许多问题都可以转化为由节点和边组成的图来研究，因此，欧拉对七桥问 第一章绪论 题的抽象方法和论证思想，开创了数学中的一个分支一图论( g r a p ht h e o r y ) 。 在欧拉之后的一百多年里，图论并没有得到进一步发展，直到1 9 3 6 年才有 了第一部图论专著，然而，图论总是倾向于用某种规则的拓扑结构一规则网络 来模拟真实网络。1 9 6 0 年，两位匈牙利数学家e r d 6 s 矛l i r d n y i 建立了随机图理论【l 3 】 ( r a n d o mg r a p ht h e o r y ) ，从此开创了复杂网络理论的系统性研究，他们所建 立的随机图模型也被称为随机网络【1 4 j ( 简称e r 网) 。在接下来的近四十年中， 随机网络理论一直是研究各种复杂网络的基本理论。随机网络的两个显著特征 是网络的小平均聚集系数和小平均距离，而规则网络的两个显著特征却是网络 的大平均聚集系数和大平均距离。直到上世纪末，随着计算机数据处理和运算 能力的飞速发展，科学家们才逐渐发现大量真实网络的统计特征与随机网络及 规则网络都不相同，1 9 9 8 年，w a r s 并l ：i s t r o g a t z 在n a t u r e 杂志上发表的文章中构造 出了一种小世界网络模型【i5 】( 简称w s 模型) ，这种网络在统计特征上既有与规 则网络相类似的大平均聚集系数，又有与随机网络相类似的小平均距离，后来物 理学家把这两种特征合在一起称为小世界特征。1 9 9 9 年，b a r a b 6 s i 和a l b e r t 在 s c i e n c e 上发表的文章中又构造出了一种无标度网络1 1 6 1 ( 简称b a 模型) ，这种网 络与随机网络和规则网络都不同的一个显著特征是：在随机网络和规则网络中， 节点的度分布区间非常狭窄，几乎找不到偏离节点平均度较大的节点，故其平 均度可以被看作节点度的个特征标度；而无标度网络中节点的度服从幂律分 布，在这种网络中，大部分节点的度值都很小，但存在少量的节点，其度值远 远大于平均度，故平均度不能作为节点度的一个特征标度，因此人们把这种特 征称为网络的无标度特征，具有该种特征的网络叫做无标度网络。 近年来人们发现越来越多的真实网络都具有小世界特征和无标度特征，例 如在朋友关系网中，一个人朋友的朋友之间是朋友的概率远比随机选出的两个 人是朋友的概率大，这体现了网络的聚集性，即：该网络具有较大的平均聚集 系数；在网络中任意选出两个人，这两个人可以通过很少几层关系而拉上关系， 我们会经常遇到某种场合下两个陌生人通过交谈，发现原来他们是同个人的 朋友，从而感叹这个世界真是太小了，这反映了朋友之间的距离是很小的，说 明朋友关系网络具有较小的平均距离；此外，朋友关系网络还有这样的特征： 大多数普通人都只有少量的朋友，而少数著名人物却有大量的朋友。综上可见， 朋友关系网络确实具有小世界特征和无标度特征，具有上述两种特征的网络已 越来越多地为人们所发现，如社会网络中的演员合作网【】、科研合作网【| 7 1 、性 2 第一章绪论 关系n t i s 】、公司董事网【1 9 2 0 1 ，信息网络中f 拘w w w n t 2 1 1 、科研引用网【2 2 1 、语言 网【2 3 2 4 1 ，技术网络中的i n t e m e t 【2 5 1 、电力网【1 5 ，2 6 _ 2 引、航空网【2 9 - 3 0 1 ，生物网络中的 新陈代谢网【3 l j 与蛋白质1 4 , 3 2 】等等显然，用随机网络或规则网络来描述这些 实际网络已经不够准确了，寻找具有小世界特征和无标度特征、能够准确描述 各种真实网络的复杂网络也就成了必然的结果，这正是近十年来科学界掀起研 究复杂网络热潮的原因之一。 1 1 2 复杂网络的主要研究内容和研究方向 复杂网络所研究的内容正渗透到数理学科、生命学科、工程学科等众多不 同的学科领域，因为复杂网络的研究具有很强的跨学科特色，且新的问题和研 究成果不断涌现，因此本文只简述目前人们正在研究的主要内容和研究方向， 包括：网络的结构与网络的特征量、网络的演化模型、网络的稳定性以及网络 上的动力学行为。 ( 1 ) 网络结构与网络的特征量 要理解网络结构与网络行为之间的关系，并进而考虑改善网络的行为，就 需要对实际网络的结构特征有很好的了解，并在此基础上建立起合适的网络模 型，而反映网络结构特征的统计量称为网络的特征量。 真实复杂网络的拓扑结构一般都是非常复杂的，网络中节点的个数有时要 数以亿计，因此，要想得到网络结构的一个清晰的图形是根本不可能的。以 i n t e m e t 为例，即使不考虑终端用户，使用路由器的用户也有上万人，可以说至 今为止还没有任何一个人知道互联网上所有的路由器是怎样联结在一起的，也 就是说，我们没有一张清晰的互联网连结的结构图形。现实生活中这样的例子 比比皆是，如前面所提到的电力网、航空网、新陈代谢网等等。正因为复杂网 络结构的复杂性，使我们很难直观地画出它们的结构图形，从而也很难建立起 这些真实网络的网络模型，这就要求我们就必须想办法寻找一些能够描述网络 特征的统计量，即：网络的特征量，以实现对复杂网络定量刻画的目的。 自从1 9 9 8 年小世界网络模型和1 9 9 9 年无标度网络模型出现以来，不同领域 的科学家们在对复杂网络结构特征的研究上己经取得了突破性的进展，发现了 许多可以用来描述网络特征的特征量，目前，被人们广泛使用的网络特征量有 三个，它们分别是： 3 第一章绪论 度分布( d e g r e ed i s t r i b u t i o n ) 。利用度分布可以使我们粗略地划分出所研究 的网络大概属于哪种类型，例如，如果我们所研究的网络的度分布服从幂律分 布，则该网络就是一种无标度网络：如果网络的度分布服从泊松( p o i s s o n ) 分 布，则该网络就是一种随机网络；规则网络的度分布是单点分布：星型网络的 度分布是两点分布，等等。利用度分布可以分析网络的连接状态，比如节 点之间的连接是否均匀，节点的地位是否平等等等。例如，以朋友关系网 为例，如果把某个人所拥有的朋友个数看成度的话，则有些人的度很大，而大 多数人的度都很小，显然这是不平等的，节点之间的连接也是不均匀的。因此， 朋友关系网是一个不平等的网络，也是一个连接状态不均匀的网络。 平均聚集系数( a v e r a g ec l u s t e r i n gc o e f f i c i e n t ) 。它是衡量网络集团化程度的 一个重要特征量【1 5 1 。还是以朋友关系网为例，网络中的集团表示网络中的朋友 圈，朋友圈中的成员之间往往也是朋友，这种现象也叫群聚现象，因此，平均 聚集系数是描述网络群聚程度或集团程度的一个特征量。 平均距离( a v e r a g ep a t hl e n g t h ) 。它描述的是网络中所有节点对之间的平均 最短距离1 1 5 j 。在无权网络中，两节点之间的距离通常指从一个节点到另一个节 点所要经历的边的最小数目，其中所有节点对之间的最大距离称为网络的直径 ( d i a m e t e r ) 。平均距离可以用来分析网络的某种性能，例如，在交通运输网络 中，网络的平均距离和直径可用来衡量网络的传输性能，平均距离和直径越小， 该网络的传输能力也就越强。 度分布、平均聚集系数和平均距离是描述复杂网络结构特征的三个重要特 征量，然而，对于真实世界中各种各样的复杂网络而言，这三个特征量还不能 描述一个复杂网络的全部特征，因此，人们也用其它一些重要的量来描述网络 的结构特征，并正在努力发现新的网络特征量。例如：介数( b e t w e e n n e s s ) 可 用来描述网络中某个节点或边的重要性f 3 3 】：最大连通分量( g i a n tc o m p o n e n t ) 可用来描述受到破坏时网络的稳定程度【3 4 】；度相关指数( d e g r e ec o r r e l a t i o n i n d e x ) 可用来描述网络中任意两个节点相互连接的倾向性。如果一个网络的度 相关指数大于零，则表示度大的节点倾向于和度大的节点连接，这类网络也称 为正相关的，并称这类网络具有同配( a s s o n a t j v e n e s s ) 性；如果一个网络的度 相关指数小于零，则表示度大的节点倾向于和度小的节点连接，这类网络也称 为负相关的，并称这类网络具有异配( d i s a s s o r t a t i v e n e s s ) 性1 3 孓驯；如果一个网 4 第一章绪论 络没有明显的同配性，也没有明显的异配性，则称这类网络为不相关网络。此 外，人们还在不断寻找其它新的统计量来描述复杂网络的各种特征，如描述网 络模块结构的模块( m o d u l a r i t y ) 特征【3 8 4 3 j ( 也叫社区或社团( c o m m u n i t y ) 特 征) ；描述网络等级结构的等级特征1 1 ，3 7 】，描述网络异质结构的基尼系数与结构 熵 4 4 - 4 5 】等等这充分说明了现有的网络特征量还不能全面刻画复杂网络的结 构特征，寻找并发现新的、能够更全面地描述网络结构特征的特征量仍然是一 项重要的研究内容。 ( 2 ) 网络的演化模型 在复杂网络的研究中，最常被提到和用到的网络模型有：规则网络模型、 随机网络模型、小世界网络模型和无标度网络模型。规则网络模型中主要包括 一维链、一维环网以及二维平面上的欧几里德格网等，其中最常用的是一维环 网，它是由个节点构成的网络，其中每个节点只与它最临近的k 个节点连接； 最常用的随机网络模型是e r 网，它也是由个节点构成的网络，其中每对节点 连接与否都是等可能的；最常用的小世界网络模型是w s 网和n w 网，它们都是 在一维环网的基础上通过增加少量的“远程连接”而形成的：最常用到的无标 度网络模型是b a 网，它是根据增长与偏好连接机制动态演化而形成的网络。“本 文将在后面更具体地介绍这些网络模型。 规则网络模型、随机网络模型和小世界网络模型还不能归属于网络的演化 模型，因为这些模型并没有考虑真实网络的演化机制，也即没有考虑真实网络 是如何演化成现在这种结构的。还是以i n t e r n e t 为例，如果让我们去建立起它的 网络模型，而不考虑i n t e m e t 的演化机制的话，我们首先想到的可能就是用某种 规则网络来描述它，比如，我们可能假定任意两个路由器都彼此相联，或者是 把路由器看成平面网格上的点，每个点都与它周围的四个点相联等等，显 然这样建立起来的高度规则的网络都不符合实际情况，因为实际中不可能任意 两个路由器都相连，也不可能每个路由器都只与它周围的四个路由器相连：那 么我们也可能还会想到另外一个极端，就是用完全随机的网络来描述i n t e r n e t 的 结构，即假定任意两个路由器之间是否联结都是等可能的，要靠抛硬币的方法 来决定，这显然也不符合实际情况，因为网络服务供应商选择他们的路由器和 外面的路由器相联的时候，显然不是通过抛硬币的方法来决定的。因此，要建 立真实网络的网络模型，就必须考虑真实网络的演化机制。 5 第一章绪论 b a 模型是无标度网络模型中最重要、也是最常用到的一个演化模型，它抓 住了许多真实网络所共有的两个重要演化特征一增长与偏好连接的特征，因此 它也就抓住了许多真实网络所共有的一个重要特征一无标度特征。b a 模型的演 化方法为我们提供了研究复杂网络演化模型的新视角，并从此出现了许许多多 的无标度网络演化模型，可以说，正是因为b a 模型的出现，才有了今天科学界 研究复杂网络的热潮。 无标度网络演化模型大都属于随机性演化模型，这是因为随机性演化模型 更符合大多数真实网络的形成特性，但在随机性演化模型的研究中也存在着很 多困难，主要表现在人们很难从理论上分析、推导演化模型的各种重要特征量， 如平均聚集系数、平均距离、介数等等。因此，与之相对应的确定性网络 模型也成为了复杂网络研究中的一项重要内容。确定性网络模型可以借助于数 学中的迭代法、递归法、数论和图论等方法来构造，使得网络的结构相对而言 比较清晰，而且网络的各种特征量都能运用数学方法得到精确解，因此，确定 性网络模型在复杂网络研究中也具有一定的实用价值1 4 6 。5 6 j 。 ( 3 ) 网络的稳定性 网络的稳定性也是复杂网络研究中的一项重要内容。稳定性( s t a b i l i t y ) 这 个词在不同领域也有不同的名称，如可靠性( r e l i a b i l i t y ) 、鲁棒性( r o b u s t n e s s ) 、 抗毁性( i n v u l n e r a b i l i t y ) 等等，但在复杂网络的研究中我们可以把它们统称为稳 定性。稳定性的反面就是脆弱性( v u l n e r a b i l i t y ) 、相继故障( c a s c a d i n gf a i l u r e ) 、 雪崩( a v a l a n c h e ) 等等，这些词在复杂网络的研究中也会经常出现。 在很多实际网络中，一个或少数几个节点或边发生故障( 故障可能是随机 发生的，也可能是由蓄意攻击而造成的) ，会通过节点之间的耦合关系引起其 它节点发生故障，这样会产生连锁反应，最后导致相当一部分节点甚至整个网 络的崩溃。例如，在i n t e r n e t 中，对少数路由器进行病毒攻击会导致路由器过载， 迫使数据包重新选择路由，从而引起其它路由器连接过载，产生雪崩效应。在 电力网中，断路器故障、输电线路故障和发电站故障常常会导致大范围停电事 故，造成严重的经济损失和社会影响。因此，复杂网络到底有多么可靠? 这无 疑是一个重要的问题。 复杂网络稳定性的研究最早始- 于2 0 0 0 年a l b e r t 等人的工俐y 7 1 ，他们所采用的 方法是考虑网络结构的变化对网络连通性的影响。他们分别把随机网络( e r 模 6 第一章绪论 型) 和无标度网络( b a 模型) 置于两种类型的攻击策略之下：随机攻击：在 这种攻击中，他们随机地删除网络中的节点( 这与网络中的随机故障相对应) ； 蓄意攻击：按照节点的度从大n d , 的顺序删除节点。结果发现：在随机攻击 下，无标度网络比随机网络有更强的稳定性。在蓄意攻击下，无标度网络比随 机网络崩溃的更早，只要少数“核心节点 被移除，整个网络就会陷入瘫痪。 这表明无标度网络面对蓄意攻击显得异常脆弱。无标度网络的这种双重特性 “稳定且脆弱( r o b u s t y e t f r a g i l e ) ”也被称为“阿基里斯的后脚跟【，7 】( a c h i l l e s h e e l ) 。a l b e r t 等人所得出的这种结论在i n t e m e t 和w w w 网上都得到了验证。 a l b e r t 等人的研究激起了大量研究人员对网络稳定性问题的兴趣。许多学者 已经对现实世界中的其它很多复杂网络的稳定性问题展开了探讨，总体研究结 果似乎都与a l b e r t 等人所得到的结论一致：多数网络对于随机的节点删除都表 现出稳定性，而面对以最大度节点为目标的蓄意攻击却相当脆弱【5 8 螂】。 目前，对复杂网络稳定性的研究主要体现在如下两个方面：设计有效的 攻击策略。虽然人们证实了攻击网络中度最大的节点是最有效的手段之一，但 在许多真实网络中，节点度的信息并不明确，也就是说，要确定网络中度最大 的节点往往是一件非常困难的事情，因此，根据我们对网络信息的了解程度， 设计出最有效的攻击策略，这无疑是一个具有重要现实意义的课题；设计更 稳定的网络。设计新的更稳定的网络或优化我们现有的网络，使之抗攻击能力 达到最强，其重要意义也是不言而喻的。然而，就目前的研究现状来看，关于 网络稳定性其它方面新的研究方法还有待于我们进一步去探讨1 6 4 舢j 。 “) 网络上的动力学行为 研究网络的结构特征和网络的演化模型并不是最终目的，最终目的还是要 研究不同的网络结构、不同的网络模型对网络上的动力学行为到底有什么样的 影响。前面所谈到的网络的稳定性问题实际上也是网络上的动力学行为之一， 只不过本文把它单独列为了一项复杂网络研究的主要内容而己。除了稳定性之 外，网络上的动力学行为还包括网络的同步性和网络上的病毒传播等问题。 网络的同步性：现实世界中的同步化行为是一种普遍存在的现象，例如， 两个挂钟挂到同一面墙上，刚开始时它们的钟摆可能是不同步的，但过了一段 时间以后它们就同步了1 6 6 】；一群萤火虫聚集在一起，刚开始时可能每只萤火虫 的闪灭时间都不同，但是一段时间以后它们就同时闪灭了【6 6 1 ；精彩的报告结束 7 第一章绪论 后，最初的几秒钟大家的掌声比较杂乱，但是很快大家的掌声就会非常整齐一 致【67 j 这样的例子在我们的现实生活中到处可见。 同步现象有好的一面，例如，在我们的心脏中，无数心脏细胞的同步震荡， 才使心瓣膜不断舒张和收缩，生命才得以延续1 6 剐；让数以万计的原子同时释放 出同样的光子，才能产生激光，从而我们才有了一项又一项造福人类的新技 术一。然而，同步现象也有不好的一面，以i n t e m e t 中的路由器为例【6 引，每个 路由器都要周期性地发布路由消息，尽管每个路由器都由自己来决定它什么时 候发布路由消息，但是研究人员发现不同路由器发布路由消息的时间，最终会 达到同步化现象，即：要么大家都不发布，要么大家同时发布，这显然会造成 网络的拥塞；还有我们所熟知的电力网、交通运输网等许多真实网络中的同步 化现象，也会给我们的生活带来诸多不便。 那么，看似巧合的同步化现象背后的机理是什么? 这个问题实际上很早以 前就已经在物理学、数学和理论生物学等领域中进行了研究 6 6 - 6 7 , 6 9 - 7 2 】，所采用的 研究方法是选择一个网络来模拟和分析产生同步的系统，只不过人们所选择的 网络大都是结构简单、容易模拟和分析的规则网络或随机网络而已。把网络中 的每个节点都看作是一个动力学系统，让有边相连的两个节点的动力学系统之 间产生某种相互耦合的作用，这样，网络就形成了一个耦合动力学系统，关于 耦合动力学系统中的同步化分析，现在已经有了一套比较成熟的方法。 人们选择具有结构简单的网络，目的是可以将研究重点放在网络节点的非 线性动力学所产生的复杂行为上，因此，网络结构对网络行为的影响就被忽略 了。然而，随着复杂网络研究的兴起，人们发现网络结构在网络同步化方面起 着非常重要的作用，网络的同步化能力在不同结