（模式识别与智能系统专业论文）复杂网络及网络上的演化博弈动力学研究.pdf

摘要 摘要 复杂网络是研究复杂系统的一门新兴学科，近几年受到研究学者的广泛关注。 自然界中的任何复杂系统都可以抽象成为由相互作用的个体组成的网络，如互联 网、万维网、航空网、电力网、蛋白质相互作用网以及各种合作网络等。研究这 些网络不仅对于人们的工作和生活至关重要，而且对于揭示自然界特别是生物系 统的奥秘也至关重要。根据国内外复杂网络的研究动态和发展趋势，研究了混合 演化和内部演化网络的结构特点，并且在常用的囚徒困境博弈以及雪堆博弈的基 础上研究了网络拓扑结构对合作行为演化的影响，同时探讨了一些可能的支持合 作涌现和稳定维持的动力学机制。本文的主要研究工作及贡献如下： 1 、提出了一种混合演化网络模型。在该模型中，新节点在加入网络中时，以特定 的概率进行全局或局部择优连接。理论分析和数值模拟表明，通过调节模型参 数，网络的度分布可以在幂律分布和指数分布之间进行变换。根据该模型生成 的网络在保持对随机故障鲁棒性的同时改善了对蓄意攻击的脆弱性。 2 、提出了一种内部演化网络模型。基于扩展的速率方程方法，解析分析了网络的 度分布和联合度分布，并做了相应的数值模拟。理论分析和数值模拟结果符合 得相当好。研究表明，当择优连接为线性时，度分布仍然服从幂律。对于亚线 性择优连接，度分布呈拉伸的指数分布形式。对于超线性择优连接，边的两端 都择优连接时会出现几乎与网络中所有其他节点都相连的“凝胶 节点。网络 增长过程中节点之间建立了非平凡的相关性和联合度分布。 3 、研究了两种正相关随机网络上的囚徒困境博弈。采用有限种群近似的复制动力 学方程作为个体策略更新规则。研究表明，网络的相关性可以促进也可以抑制 合作行为的产生。此外，还研究了网络中拥有不同连接度的个体的合作概率， 发现大度数节点总体上比小度数节点更加倾向于合作，小度数节点在博弈过程 中更倾向于改变他们的策略，这种频繁的策略切换被证明是不利于合作行为产 生的。 4 、研究了n e w m a n 高聚类社团网络上的囚徒困境博弈。该网络具有可调的聚类系 数和社团大小。个体策略更新采用有限种群近似的复制动力学方程。发现在节 点度比较均匀的网络上，网络的聚类系数对合作者的涌现是不利的。另外，对 社团结构的研究表明大的社团结构不仅会导致较低的合作水平而且使得合作 者在较小的背叛诱惑处灭亡。 5 、研究了n e w m a l l w a t t s 小世界网络上基于局部贡献和自我反省机制的囚徒困境 博弈和雪堆博弈。在博弈过程中，个体不仅考虑自己的利益，还考虑自己对邻 居的贡献。个体还具有自我反省能力，其策略更新是通过比较采用合作和背叛 i i 复杂网络及网络上的演化博弈动力学研究 策略所获得的收益来实现的，即每一轮博弈中，除了实际采用的策略外，还采 用相反的策略进行一轮虚拟博弈，然后在下一轮博弈中采用两者中能够带来较 高收益的策略。研究表明，在模型中合作行为很容易在群体中涌现出来。 6 、研究了社团网络上基于活跃连接的囚徒困境博弈和雪堆博弈。在博弈过程中， 个体可以以一定的概率断开与邻居的连接或者建立新的连接。假定同一社团内 部的个体之间建立连接的概率要大于隶属不同社团的个体之间建立连接的概 率，我们对模型做了理论分析和数值模拟，两者符合得比较好。研究表明，基 于活跃连接机制的演化博弈动力学发生在社团网络上比发生在没有社团结构 的网络上更加能够促进合作行为的产生。该结果对初始合作者的个数以及连接 动力学与策略更新动力学的时间尺度比是鲁棒的。 7 、为了理解演化博弈动力学中的记忆效应，提出并研究了一种基于记忆的囚徒困 境博弈模型。假设个体根据过去一段时间的累积收益进行策略更新。当进行策 略更新时，个体学习邻居的行为模式，即以同样的概率进行合作或者背叛。研 究表明，基于这种类型的记忆的博弈能够有效地促进合作的提高。这种促进合 作的机制对策略的更新方式以及选择邻居的方式是鲁棒的。 8 、研究了收益累积效应对囚徒困境博弈中合作行为演化的影响。在该模型中，参 与比较的有效的收益是从演化初始阶段到当前时间步的累积收益，但学习的策 略是当前时间步的策略。研究表明，当个体采用累积收益作为收益评价函数时 合作行为能够有效地涌现出来。这是一种能够普遍地促进合作产生的机制，不 因为策略更新方式的改变或者底层交互网络结构的改变而改变。 9 、研究了二维方格上基于平均收益的囚徒困境博弈。个体的策略更新方式不是通 过学习某一个邻居的策略而是通过参考自己邻域内所有个体的策略来进行的。 在每一轮博弈之后，个体根掘采用的策略将邻居内的个体分成两类，合作的个 体和背叛的个体，然后优先采用平均收益较高的那类个体采用的策略。研究表 明，这种策略更新方式能够有效地促进合作行为的产生。究其原因，主要是因 为该模型有利于合作者在较广的范围内互相帮助。 关键词：复杂网络网络模型囚徒困境雪堆博弈演化博弈合作 a b s t r a c t i i i a b s t r a c t c o m p l e xn 舐) l r o r ki san e wb r a j l c ho fs c i e n c et h a ts t l l d i e sc o m p l e xs y s t e m s ，w h i c h h a sa t t r a c t e dm u c ha t t e n t i o nf 如ms c i e n t i f i cr e s e a r c h e r s a n yc o m p l e xs y s t e m si nn a t u r e a r ec o m p o s e do f m a l l yi n t e r e a c t i n gu n i t s ，s u c ha st h e1 1 1 t 锄e t ，w o r l dw i d ew - e b ，a i 印o r c n e m o r k s ，p o w c r 鲥d s ，p r o t e i n p r o t e i ni n t e r a c t i o nn e t w o r k sa n dc o l l a b o r a t i o nn e 觚o r k s ， e t c t h e s en 鲍v o r k sa r eo fl l i 曲t e c h n o l o 西c a la n di n t e l l e c t u 2 l li m p o r t a n c ea i l dt l l ed e s i r e t 0 珊d e r s t a n ds u c hc o m p l e xs y s t e i i l sh a se 1 1 c o u n t e r e ds i 盟i 6 c a l l tc h 觚l l 锄g e sa sw e l l i n s p i r e db ym ec l 】【玎e 1 1 t i n t e n l a t i o n a lr e s e a r c hi n t e r e s t s ，w ei n v e s t i g a t em es t m c t u r a l p r o p e r t i e so fm eh y b r i de v o l v i n ga n di i l i l e re v 0 1 v i n gn e t w o r k s ，a d d r e s sh o wm e c v o l u t i o no f c o o p e f a t i o ni sa 日e c t e db yt 1 1 en e t 、r kt o p 0 1 0 既a n de x p l o r es o m ep o s s i b l e m e c h a i l i s m ss u p p o r t i n gt h ee m e 玛e n c ea n dm a i n t 锄c eo fc o o p e r a t i o nb a s e do nt h e c o m m o n l y - u s e dg 锄em o d e l s t h em a i nw o f k 觚dc o n t r i b u t i o n sa r ea sf o u o w s ： 1 、ah y b d de v o l v i n gn e 魄o r km o d e li sp r o p o s e d w h e nan o d ee 1 1 t e r si n t ot h en e t w o r k ， t l l e 哲o c a lo rl o c a lp r e f e r e n t i a la t t a c h m e n ti sc a m e do u tw i mac e r t a i np r o b a b i l i t y b o t l lt h e o r e t i c a l a 1 1 a l y s i s a n dn u m 嘶c a ls i m u l a t i o n ss h o wt h a tm ed e 伊e e d i s t r i b u t i o n so ft l l eg e n e r a t e dn e m o r k sc a i lv a 巧矗d mp o w e r - l a wd i s t r i b u t i o nt 0 e x p o n e n t i a ld i s t r i b u t i o nb ya d j u s t i n gm em o d e lp a r 锄e t e r f un _ h e 咖o r e ，m em o d e l r e d u c e st l l e 劬百1 i t ya g a i n s ti n t e i l t i o n a la t t a c k sw h i l ep r e s e i n gm er o b u s t n e s s a g a i n s tr a n d o mf a i l u r e s 2 、a ni 1 1 1 1 e re v 0 1 v i n gn e 魄o r km o d e li sp r o p o s e d b a s e do nt h ee x t e n d e dr a t ee q u a t i o n 印p r o a c h ，w ea n a l y z em e o r e t i c a l l yt h ed e 铲e ed i s 埘b u t i o na n dj o i n td e 黟e e d i s t r i b u t i o na 1 1 dp e r f i o mc o r r e s p o n d i n gn u l n e r i c a ls i m u l a t i o n s ni sf o u n dt h a tt h e t h e o r e t i c a la i l a l y s i si si ng o o da 黟e e m e n tw i mt h en u m 甜c a lr e s u l t s w h e l lt h e p r e f e r e n t i a la t t a c h m e n ti sl i n e a r ，t h ed e g r e ed i s t r i b u t i o n sf o l l o wt h ep o w e r - l a wf o r n l f o rt h es u b l i n e a rp r e f e r e l l t i a ls e l e c i t i o n ，t h ed e 伊e ed i s t r i b u t i o n sf o l l o wt h ef o mo f s t r e t c h e de x p o n e n t i a l f o rm es u p l i n e a r p r e f e r e n t i a la t t a c h m e n t ， t h ed o u b l e e n d p o i n tp r e f e i e n t i a la t t a c h m e n tc a n1 e a d t oa ne x t r 锄e l yi o wn u m b e fo f “g e l n o d e st h a tc o i u l e c tt 0n e 砌ye v e 叫o t h e rn o d ei nm en e t 、) l ，o r k t h en o n t r i v i a ld e 乒e e c o n e l a t i o na n dj o i n td e 伊e ed i s t m u t i o na r ee s t a b l i s h e dd u r i n gm e g r o w i n gp r o c e s s 3 、w ee x p l o r et h ep r i s o n e r sd i l e m m ag 釉eo nt w ot y p e so fp o s i t i v e l yc o r r e l a t e d n e t w o r k s e v o l u t i o ni sc a 币e do u tb yi m p l e n l e i l t i n gt h ef i n i t ep o p u l a t i o na j l a l o g u e o fr 印l i c a t o rd y n 啪i c s i ti sf o u n dt h a tt h en e 觚o r k sw i t hp o s i t i v ed e 伊e ec o 玎e l a t i o n c a ne i t h e rp r o m o t eo ri m l i b i tm ee m e 唱e i l c eo fc o o p e r a t i o n f u n h e 姗o r e ，w e i n v e s t i g a t et h ep r o b a b i l i 哆t 0c 0 0 p e r a t ea saf u n c t i o no ft h en o d ec o n n e c t i v i t y ，a n d f i i l dt h a tl l i 曲d e 掣e ei n d i v i d u a l so v e r a l lh a v eah i g h e rp r o b a b i l i t yt oc o o p e r a t e i ti s a l s of o u n dm a ts m a l l d e g r e ei n d i v i d u a l su s u a l l yc h a n g et h e i rs t r a t e 酉e s 1 1 1 0 r e 丘e q u e n t l y ，a n ds u c hc h a i l g ei ss h o w n t ob e 衄f a v o r a b l et oc o o p e r a t l o n 4 、w ei i l v e s t i g a t el ep r i s o n e r sd i l 锄m ag a m eo nn e w m a nh i 曲l y c l u s t e r e d c o m m u n i t ! i rn e 时o r k sw i t ht i m a b l ec l u s t 嘶n gc o e 伍c i e i l t s a i l dc o i l l m u n 埘s i z e s e v 0 1 u t i o ni sc a m e do u tb yi m p l 锄e n t i n gm e f i i l i t ep o p u l a t i o na i l a l o g u eo fr e p l i c a t o r d i a m i c s i ti sf o u n dm a t 虹l ec l u s t 耐n g e m e i e n ti ns u c had e 铲e e - h o m o g e n e o u s n e t w o r ki n h i b i t st h ee m e r g e n c eo fc o o p e r a t i o nf o rt h ee n t i r er 锄g eo ft h ep a y o f f p a r a m e t e r ni sa l s of 0 吼d 也a tc o 舢m u n i t ys i z ec a n a l s oh a v eam a r k e di n f l u e n c eo n m ee 、，o l u t i o no fc o o p e r a t i o n ，w i lal a 唱e rc o m m u n i t ys i z e1 e a d i n gt on o to n l ym e 1 0 w e rc o o p e r a t i o nl e v e lb u ta l s ot h es m a l l e rt h r e s h 0 1 do fm ep a ) 7 0 f rp a r 枷e t e r a b o v e 、h i c hc o o p e r a t o r sb e c o m ee x t i n c t 5 、w ei n v 础g 刮t em ee v o h l t i o n a r y 埘s o n e r sd i l 瞰匝ag a m ea n d t h es n o w 越rg a m e o nn e 砌锄w 缸t ss m a l l w o 订dn e 俩o r k sw i t h1 0 c a lc o n t f i b u t i o na n di n t i - o s p e c t i o n 1 1 1m eg 锄e s ，i n d i v i d u a l sn o to i l l yc o n c e n t r a t eo nm e i ro w ni n c o m e sb u ta l s o c o n s i d e rm el o c a lc o n 埘b u t i o n st ot h e i rn e i g o r s f u r t h e m l o r e ，i n d i v i d u a l sh a v e t h ea b i l i t yo fs e l f q u e s t i o n i n ga n dt h es t r a t e g yu p d a t i n gi s d e t e m i n e db yt h e c o m p a r i s o nb e t w e e i lt h ep a y o 舔o b t a i n e dw i mc o o p e r a t i o n 锄dd e f e c t i o n ，i e ，m c r e a c hr e a lr o u n do fg 锄e s ，e a c hp l a y e rp l a y sav i n u a lr 0 1 m do fg 锄e sa n dt h e i l a d o p t sm es 缸瞰e g y1 e a d i n gt o ah i 曲c rp a y o 值s t l l d i e ss h o wt h a tc o o p 训i o n e m e r g e se a s i l yi nm ep o p u l a t i o ni nt h i sm o d e l 6 、w ei n v e s t i g a t et h ep r i s o n e r sd i l 咖ag 帅e 觚ds n o w d r i 俞g a m eo nc o m m u n l t y n e 附o r k sw i t ha c t i v el i l l k i n gd ”a m i c s i nt h eg 锄e ，i n d i v i d u a l sc a nb r e a ko l dl i n l ( s a n de s t a b l i s hn e wl i n l ( sw i t h 乏h e i rn e i 曲b o r s w ea s s u m et h a ti n d i v i d u a l si n 也es a m e c o m m u n i t yh a v eah i 曲e rp r o b a b i l i t yt oe s t a b l i s hl i n k st h a ni n d i v i d u a l sb e l o n 百n g t o d i 行e r e n tc o m m u n i t i e s w bc a n y o u tb o t ht h e o r e t i c a la n a l y s i sa 1 1 dn u m e n c a l s i m u l a t i o n s ，f i n d i n gg o o da 伊e e n l e n tw i t he a c ho t h 瓯s t u d i e ss h o wt h a tc o i l l 】m u n l t y s t n l c t u r ei sm o r ef a v o r a b l et oc o o p e r a t i o n t h er e s u l t sa r er o b u s tw i mr e s p e c tt o b o t hm ei n i t i a ln 啪b e ro fc o o p e r a t o r sa n dt h et i m e s c a l er a t i oo f1 i n k i n gd y n 锄i c s t os t r a t e g yu p d a t i n gd y n a m i c s 7 、i no r d e rt o 蛐d e r s t a n dt h em 锄。巧e 丑b c t si nt h ee v o l u t i o n a r yg a m ed y n a m l c s ，a m 锄o r v - b a s e d 研s o n e r sd i l e m m a 铲m em o d e l i sp r o p o s e da i l da n a l y z e d ni s a s s 啪e dt h a ti n d i v i d u a l su p d a t et h e i rs t r a t e 百e sa c c o r d i n gt o m ea c c u m u i a t l v e a b s l l t a c t v p a y o 侬i nt l l ep a s ts e v e r a lt i m es t e p s w h e nu p d a t i n gs 仃a t e 西e s ，i n d i v i d u a l si m i t a t e t h eb e h a 访o r a lp a t t e m so ft h e i rn e i g h b o r s ，i e ，t h e yc o o p e m t eo rd e f e c tw i t l lt l e s a m ep r o b a b i l i 够a sm e i rn e i g h b o r s s t u d i e ss h o wt l l a tc o o p e m t i o nc a l lb e 黟e a t l y e r l l l a i l c e d w eh a v ec h e c k e dt h a tt h e c u r r e n tm e c h a n i s mw h i c hp r o m o t e s c o o p e r a t i o ni sr o b u s tw i t hr e s p e c tt ob o t ht h ew a y so fs 们a t e g yu p d a t i n ga n d n e i 曲b o rs e l e c t i o n 8 、w bs t i l d yt h ep a y o 僻a c c 啪u l a t i v ee 髓c to nt h ee v o l u t i o no fc o o p e r a t i o ni nm e p r i s o n e r sd i l 铷：吼ag 锄e i i lo u rm o d e l ，t h ep a y o f fi ne 虢c ti st h ea c c u m u l a t i v e p a y o f r 舶m t t l ev e 巧b e 西i l i l i n go f 廿1 ee v o l u t i o n a 叫p r o c e s s ，b u tm e s t r a t e g yi m i t a t e d b yi n d i v i d u a l si s t h es 仃a t e g yi i lt h ec u r r e i l tt i m es t 印i ti sf o u n dt h a tw h 吼 i i l d i v i d u a l sf o c u so nt h ea c c u m u l a t i v ep a y o 正c o o p e r a t o r sa r ef a v o r a b l eb ys e l e c t i o n i ti sau n i v e r s a lm l e 吐1 a tc a l lp r o m o t ec o 叩e m t i o n ，w h i c hi sf o b u s tw i t l lr e s p e c tt o m ew a yo fs 仃a t e g yu p d a t i n ga n dm e l h l d e d y i n gi n t e r a c t i o nn e 觚o r k 9 、w e i n v e s t i g a t et 1 1 ep d s o n e r sd i l e m m ag 锄eo ns q u a r el a t t i c e sb a s e do nt h ea v e r a g e p a y o 伍i i lt h em o d e l ，e a c hi n d i v i d u a lu p d a t e si t ss t r a t e g ) ，b yl e a n l i n ga l ln e i g h b o r s i nt l l en e i g h b o r h o o di n s t e a do f b yl e a r m n g 行o mas i n 百en e i g h b o r a r e re a c hr o u n d o fg 锄e ，e a c hi 1 1 d i v i d u a ls e p a r a t e sa l lt h e i rn e i g h b o r si n t ot v m g r o u p s ：c o o p e r a t i v e g r 0 1 l pa i l dd e f e “n gg r o u p ，a 1 1 dt h e i la d o p t st h es t r a t e g yo ft h ei n d i v i d u a l si nt h e g r o u pw i n la 拭曲e ra v e r a g ep a y o 正s t u d i e ss h o wt h a tc o o p e r a t i o nc a nb ee 虢c t i v e l y p r o 】【1 1 0 t e db ys u c ha i lu p d a t i n gm l e ，w h i c hi sc a u s e db ym ef a c tt 1 1 a tc o o p e r a t o r s ，c a n ， h e l pe a c ho m e ri naw i d e rr 锄g e k e y w o r d s ：c o m p l e xn e t w o r kn e t w o r km o d e l p r i s o n e r sd i l e i l l m a s n o w 嘶f tg 锄e e v 0 1 u t i o n a 巧g a m ec o 叩e r a t i o n 独创性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：立。葑务 日期油j 9 专，7 r 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留 送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容， 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。( 保密的论文 在解密后遵守此规定) 本人签名：立立鲁盘 靳繇丝 日期塑! ! ：垒：! z 日期尘趔- 7 第一幸绪论 第一章绪论 2 0 世纪8 0 年代以来，以互联网为代表的计算机和信息工程技术的迅猛发展使 人类社会大步迈入了一个网络时代。从互联网到万维网、从电力网到交通网、从 生物体中的大脑神经网到新陈代谢网、从科研合作网到各种政治、经济、社会关 系网等人们事实上已经生活在一个充满着各种各样的复杂网络的世界之中。人 类社会的日益网络化要求人类对各种人工和自然的复杂网络的结构、性质和功能 有更清楚的认识。长期以来，通信网络、电力网络、生物网络和社会网络等分别 是通信科学、电力科学、生命科学和社会科学互不相交的研究对象，而今天被称 为复杂网络( c o m p l “n e t w o r k ) 【“的理论分支所包揽。复杂网络已经成为描述和 理解现宴复杂系统的一种重要的方法。自然界中大量的复杂系统都可以通过形形 色色的网络加以描述 】，其中颇具代表性并得到广泛研究的网络有互联网【叫”、 电力网、科学家合作网络旧瑚、蛋白质相互作用网络。”、食物链网络( 见 图l1 ) 等。当用复杂网络来刻画这些复杂系统的结构时，网络中的节点代表真实 图l1 一个涣水湖中的食物链阿络( 摘自文献【7 ) 。 系统中不同的个体，而个体之间的关系则抽象为嘲络中的边或连接，往往是两个 个体之间有某种特定关系则连条边，否则不相连。例如因特网描述了计算机 之间的网络连接，科学家合作网络表示了科学家之间的合作关系( 见图l2 ) ，蛋 白质相互作用网刻画了蛋白质相互作用关系而社会网络则描述了人与人之问的 社会关系等。大体上说，复杂网络要研究的是各种看上去瓦不相干但其实密切关 联的形形色色网络之间的共同属性和处理它们的普适性方法。 从2 0 世纪9 0 年代开始，复杂网络的研究逐步形成了一个自我完备的学科，甚 至被称为“网络的新科学”f2 0 】。复杂网络作为一个新的研究领域，它的基本理论 正渗透到从数理科学到生命科学、工程科学甚至社会科学等众多不同的领域中去。 事实上，复杂网络的研究已经成为近1 0 年来全世界在不同学科领域( 包括力学、 复杂嘲络及网络i 的演化博奔动力学研究 物理、生物、系统控制、通信技术、社会、经济和军事等) 中的科学家们的研究 热点( 见图13 和i4 ) ，复杂网络研究蓬勃发展。今天，对复杂网络的定性与定量 特征的认识和理解已成为网络时代科学研究中一个共同而又极其重要的挑战性课 题。 ， + ， 谴、+ 兰 劳弋 囝l2 圣塔菲研究所科学家合作网络的最大组元( 墩自文献【l 卅) 4 呻0 3 5 0 0 鬈2 5 0 0 2 i l0 0 0 5 0 0 d m i 1 7 图13 以复杂网络为关键诃的s c i 论文发表情况统计( 摘白文献f 2 1 1 ) 。 复杂网络研究的蓬勃发展主要得益于以下几个方面的因素：第一，数据采集 的计算机化使人们能够获得各种真实网络的拓扑结构的大型数据库：第二，计算 能力的提升使得人们能够处理各种大规模的网络；第三，复杂阿络的研究打破了 异学科之叫的界限，这为揭不水同复杂刚络共同的结构特性提供了十分有利的条 件。复杂网络两项开创性的研究是1 9 9 8 年w 帕和s t r o g m z 提出的小世界网络模 型川和1 9 9 9 年b a r a b 矗s i 和a 1 b 哪提出的无标度网络模型n 这两项工作揭示了现 实世界形形色色的复杂网络具有普遍的、非平凡的结构特性彻底颠覆了人们对 实勘i 删络的传统认识，掀起了一股复杂网络研究热潮。 到日前为jj 。，网络的应用领域涉及到军事、经济、通信、r 程技术、社会、 政治、经济和管理等众多领域。研究这世网络有助于解决人类呵临的一些重要问 第一章绪论 题【2 2 矧： 首先，网络科学的研究具有现实的和长远的军事国防意义。2 i 世纪将是互联 网和信息时代，互联网的麓展带动计算机、微电子、通信和软件等信息产业的发 展，成为2 1 世纪全球军事和经济的主要推动力，这些需求反过来又推动因特网向 宽带、高速发展。正在探索中的f 一代的互联网，包括光互联网和未来的量子互 联网，这些都极富挑战性。网络科学的深入研究必将对全球经济发展有长远的战 略意义，并且粕有巨大的应用潜力。 扩“_ 明； 4 复杂网络及网络上的演化博弈动力学研究 到目前为止，复杂网络研究总体上主要集中在两个方面：复杂网络结构的演 化动力学机制以及网络上的动力学过程特性。前者主要是对所观察到的复杂系统 的拓扑结构做出理论上的解释，后者主要是研究网络结构如何影响网络上的动力 学过程。 1 1 网络结构的统计特性 大量的实证研究表明，现实世界的网络具有许多共同的结构特性，如节点度 分布服从幂函数律、具有高的聚类系数和小的平均路径长度等。下面结合网络的 基本概念来介绍这些特性。 度和度分布( d e g r e ed i s t r i b u t i o n ) ：度也称为节点度或连接度，是单独的节点 属性中简单而又重要的概念。一个节点的度定义为与该节点相连接的边的条数( 或 者节点的个数) 。对于有向网络而言，一个节点的度可分为出度和入度。节点的出 度定义为从该节点出发连向其他节点的边的条数；节点的入度定义为从其他节点 连入该节点的边的数目。度在不同的实际网络系统中所代表的含义不尽相同。例 如，在城市航空网中，度表示一个城市航线的多少及其重要程度。度越大，其重 要性就越大；在社会网络中，度可以表示个体的作用力和影响程度，一个节点的 度越大，表示在整个网络系统中的作用和影响就越大，反之亦然。网络中所有节 点的度的平均值称为整个网络的平均度，记为( 后) 。网络中节点度的分布状况可以 用分布函数尸( 七) 来描述。p ( 妁表示的是随机选定一个节点，其度值恰好为七的概 率。相应的，对于有向网络，有p ( 尼加) 和p ( 尼哪) ，分别对应节点的入度分布和出度 分布。研究表明，很多真实的大规模网络如万维网、互联网、蛋白质相互作用网 等f 5 ，。7 】的度分布显示出幂律的分布特性，即p ( 惫) 后一，具有幂律度分布的网络称为 无标度( s c a l e 舶e ) 网络【2 4 】。 另外一种刻画网络节点度分布状况的物理量是度分布的矩，p ( 七) 的嚣阶矩定 义如下 ( j j ”) = ：尼”尸( 七) ( 1 - 1 ) 下 其中一阶矩对应网络的平均度( 后) ，二阶矩( 七2 ) 刻画了节点连接度分布的波动大 小。研究表明，二阶矩的发散与否将会根本性地影响网络上的动力学过程。 平均路径长度( a v e r a g ep a t hl e n g t h ) ：对于无向、无权的网络，网络中的两个 节点i 和，之间的距离d 。定义为这两个节点最短路径上边的条数。网络中所有节点 对之间的最大距离称为网络的直径，记为d ，即 d 3 嘴x ( 叱) ( 1 - 2 ) 第一章绪论 网络的平均路径长度定义为网络中所有节点对之间距离的平均值，即 扛南舌吒 ( 1 - 3 ) 网络的平均路径长度也称为网络的特征路径长度。网络的平均路径长度和直径衡 量的是网络的传输性能和效率。研究发现，尽管许多实际的复杂网络的规模很大， 但网络的平均路径长度却小的惊人，即真实网络普遍具有小世界性质。 小世界性质有着清晰的数学表达：如果距离中心节点距离为，范围内的节点的 数目随着，的增加呈指数增长，那么网络的平均距离就会随着网络规模的增加呈对 数规律增加。最近小世界性质有着更加明确的定义：如果网络的平均路径长度随 着网络规模的增加呈对数速度或者小于对数速度增加，那么称网络具有小世界性 质【2 5 1 。 聚类系数( c i u s t e r i n gc o e f f i c i e n t ) ：聚类系数用来衡量一个网络的聚集程度，该 概念有着深刻的社会根源。在社会网络中，你朋友的朋友很可能也是你的朋友， 这种属性称为网络的聚类特性，它刻画了网络成团化的程度。假定网络中某一节 点i 有岛个邻居。显然，在没有重边的情况下，这个邻居之间最大可能的边数为 岛( 红一1 ) 2 。同时，用e 表示这些邻居节点之间实际存在的边数，则点f 的聚类系 数e 定义为 c ： 垒：兰墨 f t ( 南一1 ) 2t ( 墨一1 ) 、7 该定义便于用计算机计算。聚类系数还有另外一个定义，即 与点f 相连的三角形的数量 ，。、 - 2 写丽莉萄硅蠢酉藤 卜) j 其中，与节点f 相连的三元组是指包括节点f 的三个节点，并且至少存在从节点f 到 其他两个节点的两条边【_ 7 1 。该定义便于理论分析。对网络中所有节点的聚类系数取 平算术均值即可得到整个网络的聚类系数c 。 度相关性( d e g r e ec o r r e l a t i o n ) ：现实网络除了上述三个最基本的特性之外，另 外一个重要的特征量是度度相关性，也称为匹配模式，它刻画了不同节点之间的 连接关系。如果网络中度大的节点倾向于和度大的节点相连，则称网络是正相关 的或者正匹配的；反之，如果度大的节点倾向于和度小的节点相连则称网络是负 相关或负匹配的。p 2 l s t o r - s a t o r r a s 【2 6 】等人给出了度度相关性的一个简洁直观刻画， 即计算度为尼的节点的邻居的平均度，其值为尼的函数。对于正、负相关的网络， 函数图形分别是是的递增和递减曲线；对于不相关的网络，该函数值为常数。 n e w m a n 定义了度度关联函数为【2 7 2 8 】 一 一m 业( 一g ，吼) ( 1 6 ) 6 复杂网络及网络上的演化博弈动力学研究 这里， 表示对所有边的平均，p 珞为归一化两个节点两端随机连接的剩余度 的联合概率，鲰：登去粤k 是剩余度归一化分布，鼽为度分布。n e 仰a 1 1 进一步 l 渺3 简化了计算方法【2 8 】，只需计算p e a r s o n 关联系数广( 一l ，1 ) 即可描述网络的度 度相关性。这时，简化为 m 。1 ，讹一瞰1 ，寺( j l + 树 m 。，寺( 彳+ 砰) 一【m 一，寺( z + 岛) 】2 其中，无和颤是网络中第f 条边两端的节点的度数，m 是网络中总的边数( 后文中 将用到这两种方法刻画网络的度一度相关性) 。此方法给出的是一个唯一数，如果 厂 0 ，则网络是正相关的，如果， 。由此可知， 随机图具有小世界特征；另一方面，由于e r 图中，不论两点是否拥有共同的邻居， 其连接的概率总是为p ，根据聚类系数的定义可知，e r 随机图的聚类系数 = p = ( 七 1 ，这意味随机图没有聚类特征。 固定e r 随机图的平均度 不变，那么对于一个拥有个节点的e r 随机图， 其度分布可以表示为 p ( 七) = c 嘉一p ( 1 一p ) - 1 。 ( 1 一1 2 ) 当专o 。时，式( 1 1 2 ) 可以化为 雕) = 磷# 印刊川一= 耥以1 刊川“ 等p 印刊州= 学( 1 刊专呻m 。 燮p 一：盟e 嘶 ( 1 - 1 3 ) 庀!七! 近似为一个泊松( p o i s s o n ) 分布。因此，e r 随机图也称为p o i s s o n 随机图。尽管e r 随机图作为实际复杂网络的模型存在明显的缺陷，在2 0 世纪的后4 0 年中，e r 随 1 0复杂网络及网络上的演化博弈动力学研究 机图理论一直都是研究复杂网络拓扑的基本理论，其中的一些思想对于目前的复 杂网络研究仍然很重要。 e r 随机图模型提出以后因简单而被大多数人所接受。从2 0 世纪5 0 年代末到 9 0 年代中期，大多数大规模网络的拓扑结构都采用该模型来描述。然而，由于实 际网络的特性并不完全像e r 随机图那样，例如在社会网络