（理论物理专业论文）复杂网络上的传播和耦合动力学过程研究.pdf

摘要 复杂网络是近年来兴起的一门新兴交叉学科，由于其研究对象的普遍性和多样性， 受到国内外众多学科研究人员的广泛关注在我们周围，网络无处不在，遍及自然界和 人类社会任何一个复杂系统都可以抽象成为由相互作用的个体组成的网络，其中个 体抽象为网络节点，个体间的相互作用抽象为网络连边其中广为人们熟知并具有代 表性的网络包括互联网、万维网、铁路网、航空网、电力网、蛋白质相互作用网、新陈 代谢网、基因调控网、神经网、人际关系网等等深入研究这些网络不仅对人们的工作 和生活具有现实意义，而且对了解自然界和社会的发展具有深远的科学和社会意义 复杂网络研究关注个体之间的微观相互作用导致的系统的宏观现象和传统还原 论方法不同，复杂网络把整个系统作为研究对象，专注于系统中个体的相互作用，预 言复杂系统丰富的整体行为，包括自组织特性，涌现等在科学高度发展的今天，以整 体的、网络的观点研究各种复杂现象已经成为科学研究的必然趋势复杂网络的研究 已经渗透到自然科学和社会科学的各个方面，突破了学科之间界限，极大地推动了数 学、物理、化学、生物学、信息工程和其它社会科学等多学科的交叉和发展因此，复 杂网络研究具有重大的理论价值 研究复杂网络的最终目标是理解网络结构如何影响发生于网络上的各种动力学过 程网络上的信息传播和网络上的耦合现象研究是其中非常重要的研究内容文献中 大量的传播动力学和网络同步的论文，包括网络上的病毒传播、信息传播、博弈过程 和同步现象等，从各自不同的角度研究复杂系统的特性根据当前国内外复杂网络的 研究动态和发展趋势，我们在网络上的信息流传播和网络的耦合同步现象的动力学过 程方面做了比较系统的工作，本文的主要工作如下： 比较系统地研究了无标度网络上的信息传播动力学，首次提出了基于局域拓扑信 息路由策略的概念随着互联网等大型通讯网络的广泛应用，网络规模变得越来越庞 大，网络结构也越来越复杂，网络拥塞变得越来越普遍，特别是网络的拓扑结构也在 不断的变化之中，这使得基于网络全局拓扑信息的传统路由策略遭受日益紧迫的存储 和计算能力的压力不同于过去的基于网络全局拓扑信息的数据包路由规则，我们提 出了基于局域拓扑信息的数据包路由规则，研究了系统中信息流从自由流态到阻塞流 态的相变特性，并以此特性为标准来刻画网络的总体通讯能力；研究了这些算法的各 种时间和空间特性。我们还发现适当地增加网络结构的拓扑信息量，比如考虑网络节 点次近邻信息，可以极大地提高通讯网络的总体通讯能力在实际设计网络路由算法 时可以在开销和性能之间取舍，以便可以获得一个最优的解决方案我们的研究对于 1 l 摘要 目前网络路由协议算法的优化以及新一代路由协议的设计有一定的指导意义相关的 研究论文发表在p h y s i c a lr e v i e we 、 e u r o p e a np h y s i c sj o u r n a lb 、p h y s i c sl e t t e r s a 等杂志上 研究了无标度网络上的同步，提出通过去耦合过程来提高网络的同步能力我们 从网络体系拓扑结构出发，对网络结构作一个微扰，研究了网络的特征参量，如平均 最短距离、网络的最大介数等参量，对网络同步能力的影响，发现网络的最大介数和 网络同步能力存在某种线性关系，因而网络的最大介数在某种情况下( 比如网络结构 相似) ，是表征网络同步能力大小的一个最适宜的参量。由于该方法简单易行，在工程 实践中可能有很大的潜在应用价值，相关的研究论文发表在p h y s i c a lr e v i e we 上 此外，我们研究了地理约束因素对小世界网络上的同步现象影响实际的网络很 多都是嵌入到一定的空间里的，即网络中的节点占据着一维、二维或者三维空间的一 个确定的位置，它们的连边是某种实际的相互作用典型的实例包括神经网络、信息 通讯网络、电力网络、交通网络( 包括河流、机场、街道、铁路和公路) 等等。我们研 究了一维和二维格子上由于地理约束所引起的耦合强度变化对网络同步能力的影响， 发现网络的同步能力不仅和空间距离而且和耦合强度都不是一个平凡的关系我们的 研究表明，空间距离的限制在网络的集体同步过程中起到非常重要的作用由于这类 网络在国民经济和人民生活中占据着十分重要的位置，对它们的研究不但是必要的而 且是必须的，相关的研究论文发表在p h y s i c a lr ，e v i e we 上 我们发现网络上的信息传播和网络的耦合同步存在内在的联系，通讯性能表现良 好的网络，其网络的同步能力也同样比较强我们分析了网络上信息传播和同步的关 系，同步的过程同时也是耦合信息传播的过程因此这两个看似无关的研究课题，本 质上是相关的过程，分别从不同的方面反映了网络拓扑结构的影响 关键词：复杂网络；新陈代谢网；信息流传播；去耦合过程；网络同步；地理约束； 耦合强度 a b s tr a c t c o m p l e xn e t w o r km o d e l i n gh a sb e e nc o n s i d e r e da sa ni m p o r t a i l ti n t e r d i s c i p l i n e 印p r o a 出f o rd e s c r i b i n ga n du n d e r s t a n d i n gc o m p l e xs y s t e m s b e c a u s eo fu n i v e r s a l i t y a n dd i v e r s i t yo fi t sr e s e a r c ho b j e c t s ，i th a sa t t r a c t e db r o a da 七乞e n t i o n so fr e s e a u f c h e r s i nm a n yf i e l d sa l la v e rt h e 、v o r l d c o m p l e xn e t w r o r k sa r eu b i q u i t o u sa r o u n do u rl i v e s ， r a n g i n gf r o mn a t u r e 七oh u m a ns o c i t y a n yc o m p l e xn e t w o r ks y s t e mc a nb ev i e w e d a sag r a p ho fi n t e r a c t e di n d i v i d u a l s ，w h e r en o d e sd e n o t ei n d i v i d u a l sa n dl i n k sd e n o t e i n t e r a c t i o n sb e t 、e nt h e m t h ew e l “( 1 1 0 w na n de x t e n s i v e l ys t u d i e dn e t 、v o r l ( si n c l u d e i n t e r n e t ，w 6 r l dw i d ew e b ，r a i l w a yn e t w o r b ，a i r p o r cn e t w o r k s ，t h ep o w e rg 蹦，p r o t e i n _ p r o t e i ni n 七e r a c t i o nn e t v v o r k s ，m e 七a b o l i cn e t w o r k s ，g e n er e g u l a t o r yn e t w o r k s ，n e u r o n n e t w d r k s h u m a nr e l a t i o n s h i pn e t w o r 王( s ，e t c e x t e n s i v er e s e a r c h e so f 七h e s en e t w o r 王( si n t h ep a s taf e wy e a r sh a ec o m p l e t e l yc h a n g e dt h et r a d i t i o n a lv i e wa b o u tt h er e a l 、 ，o r l d n e t w o r l c sa n ds p u r r e dt h er a p i dd e v e l o p m e n to ft h ei n t e r d i s c i p l i n 甜ys c i e n t i f i cf i e l d s c o m p l e xn e t w d r km o d e l i n ga p p r o a c hf o c u so nm a c r o s c o p i c a lp h e n o m e n ar e s u l t f r o mt h ei n t e r a c t i o n so fi n d i v i d u a l s a p a r tf r o mt r a d i t i o n a lr e d u c t i o n i s mu s u a l l yu s e d b yp h y s i c i s t s ，b yc o m p l e xn e t 、v o r km o d e l i n ga p p r o a c hp o i n to fv i e w ，七h ei n v e s 七i g a t i n g s y s t e mi ss e e na saw h 0 1 e ，t h ei n t e r a c t i o l l so fi n d i v i d u a l 8i 璐i d et h es y s t e ma r ef o c u s e d o na n dr i c ho v e r a l lb e h a v i o r so f 七h es y s t e ma r ep r e d i c t e di n c l u d i n gs e l f o r g a n i s e dp r o p e r t i e s ，e m e r g e n c ea n do t h e rp h e n o m e n a s of a r ，t h ei n v e s t i g a 七i o no fc o m p l e xn e 七、v o r k s h a sc o v e r e dm a n y 丘e l d s ，i n c l u d i n gm a t h m a t i c s ，p 1 1 y s i c s ，c h e m i s t r y ，b i o l o g y ，t e c h n o l o g y a n ds o c i a ls c i e n c e s t h eu l 七i m a t eg o a lo fs 乞u d y i n gc o m p l e xn e t 、v o r l 【si s 七ou n d e r s t a n dh o w 七o p o l o g i c a lp r o p e r t i e s 撕e c tt h ed y n a m i c a lp r o c e s s e st a k i n gp l a c eo nt h e m r e s e a r c h e so n i n f 6 r m a 乞i o np r o p a g a 七i o na n dc o u p l i n gp h e n o m e n ac v e rc o m p l e xn e 乞w o r k sa r eo ft h e g r e a t e s 七i m p o r 七a n c e t h e r ea r em a _ 1 1 yp a p e r sc o n c e r n i n gp r o p a g a t i o nd y n a m i c sa n d s y p ( 盘r o n i z a t i o no v e rc o m p l e xn e t w o r k si nt h el i t e r a t u r e ，i n c l u d i n ge p i d e m i cs p r e a d i n g ， i n f b r m a t i o np r o p a g a t i o n ，g a m e ，s y n c h r o n i z a t i o na n ds oo n i n s p i r e db yt h ec u r r e n 七 i 1 1 t e r n a t i o n a lr e s e a r c hi n t e r e s t s ，w ef o c u s e do nt h ei n f o r m a t i o np r o p a g a t i o nd y n a m i c s a n d 8 y n c h r o n i z a t i o np h e n o m e n a o v e rt h ec o m p l e xn e t w o r k s t h ew o r l ( s 、税d oi nt h e s e 矗e l d sa r ef o l l o w i n g ： w 色h a v es y s t e m a t i c a l l l yi n v e s t i g a t e dt h ed y n a m i c so fi n f o r m a t i o np r o p a g a t i o no v e r 1 l l l va b s t r a c t s c a l e f r e en e t w o r k s b e c a u s et h es i z e s0 fm o d e r nc o m m u n i c a t i o nn e t ，o r k sa r eb e c o m i n gb i g g e ra n db i g g e r ，e v e nw q r s e ，t h et o p o l o g yo f 七h en e t w o r k si se v e r c h a n g i n g ，t h e t r a d i t i o n a lr o u t i n gs 七r a t e g i e s ，w h i c hb a s e do nt h eg l o b a lt o p 0 1 0 9 i c a l i n f o r m a t i o n ，s u f f e r l a ( 盘o fs 七o r a g ea n dc o m p u t a 七i o n a lp o 、 r e r c o n s i d e r i n gt h i 8s i t u a t i o n ，、 虺h a ep r o p 0 8 e d s e v e r a l r o u t i n gs t r a t e g i e so f8 e n d i n gd a t ap a c k e t so n l yb a s e do n1 0 c a l i n f o r m a t i o n w 色 c a nq u a n t i f y 七h ec a p a c i t yo fan e t w o r kb yt h ep h a s et r a n s i t i o n 行o mf r e ef l o ws t a t e t oc o n g e s t i o ns t a t e ，a n d 、陀h a v ef o u n dt h eo p t i m a lp a r a m e t e rv a l u e s ，r e s u l t i n gi nt h e h i g h e s te f f i c i e n c yo fs c a l e f i e ei l e t r o i k s m o r e o v e i ，、ef 6 u i l da p p r o p r i a t e l yi n c r e a s i n g i n f o r m a t i o no fn e t w o r kt o p o l o g yc a n 擎e a t l yi n c r e a s et h ec a p a c i t yo ft h en e t 、r k ，f o r e x a m p l e ，n e x tn e a r e s t n e i g h b o rs e a r c h i n gs t r a t e g y i nt h ep r a c t i c a ld e s i g no ft h er o u t i n gs t r a t e g y ，耽r ec a nt r a d eo f fc o s ta g a i n s tc a p a b i l i t yo ft h es y s t e mi no r d e rt of i n d a no p t i m a l8 0 l u t i o n o u rr e s u l t sm a yb eu s e f u lf o rd e s i g n i n gn e x tg e n e r a t i o nr o u t i n g p r o t o c 0 1 w 色h a l v es t u d i e d 七h ec o l l e c 七i v es y n c h r o n i z a 七i o nb e h a v i o ro v e rs c a l e _ f t e en e t 、v o r k s a n dp r o p o s e dad e c o u p l i n gp r o c e s st oe n h a n c et h es y n c h r o n i z a b i l i t yo fs c a l e f r e en e t 一 、o r k s w i t hp e r t u r b a t i o no nt h en e t w o r ks 七r u c 七u r e ，w ei n v e s t i g a t e dh o wt hc h a r a c 卜 七e r i s t i cp a r a m e t e r s ，f o re x a m p l et h ea v e r a g es h o r t e s 七p a t h ，c h em 心m u mb e t w e e n n e s s a n ds oo n ，a f r e c 七t h es y n c h r o n i z a b i l i t yo ft h en e t w o r l ( s w 色f l n dt h a tt h em a x i m u mb e - t 陀e n n e s 8h a v ea1 i n e a r 一1 i k er e l a t i o nw i t hs y n c h r o n i z a b i l i t yo ft h en e 七、v o r k t h er e s u l t s i n d i c a t et h a tt h em a x i m u mb e t 、v e e n n e s si sab e s tt o k e no fn e 七w o r k8 y n c h r o n i z a b i l i t y a m o n gs i m i l a rn e t w o r ks t r u c t u r es of a r w ba l s oi m 髑t i g a t e dg e o g r a p h i c a le f j e c to ns m a l l w o r l dn e t w o r ks y n c h r o n i z a t i o n m a r l yr e a l 、o r l dn e t w o r k sa r ee h l b e d e di ns o m es p e c i f i cs p a c e ，n o d e sh a ec o o r d i n e t 8a n d l i n k sd e n o 七es o m er e a li n t e r a c t i o n s w 色h a ee x p l o r e dt h ee 珏e c t so fc o u p l i n gs t r e n g t h ， w h i c hc o m i n gf r o mg e o g r a p h i c a lr e s 七r i c t i o n ，o nn e 七w o r k8 y n c h r o n i z a b i l i t yo no n e a n d t w o _ d i m e n s i o n a ll a t t i c e 8 i ti sf o u n dt h a tn e t 、r ks y n c h r o n i z a b i l i t yi san o n t r i v i a lf u n c t i o no fd i s t a n c ea n dc o u p l i n gs t r e n g t h o u r 丘n d i n g ss h e ds o m e1 i g h to nt h ec o l l e c 七i v e d y n a m i c so fr e a lc o u p l e ds y s t e m s w ef i n di n f 6 r m a t i o np r o p a g a t i o no nac o m p l e xn e t 、w ) r kh a es o m er e l a t i o n sw i t h s y n c h r o n i z a t i o no nt h en e t 、 ，o rk n e t w o r k sw i 七hh i g hs y s t e mc a p a c i t yo f t e ns h o wh i g h n e t w o r ks y n c h r o n i z a b i l i t y a c t u a n y ，s y n c h r o n i z a t i o np r o c e s si sa l s oap r o c e s so ft r a n s _ m i s s i o no fc o u p h n gi n f o r m a t i o n t h et 、os e e m i n g l yi r r e l e v a n tr e s e a r c hs u b j e c t sh a v e v t h es a m eu n d e r l y i n gd y n a m i c a ln a t u r e ，r e f l e c t i n gd i b e r e n ta s p e c t so ft h ep r o p e r t i e so f t h es y s t e m k e y w o r d s ：c o m p l e xn e t 、阳r k ，m e t a b o l i cn e t 、o r 王( s ，i n f o r m a t i o nf l o wp r o p a g a - t i o n ，d e c o u p l i n gp r o c e s s ，n e t w o r ks y n c h r o n i z a t i o n ，g e o g r a p h i c a lr e s t r i c t i o n ，c o u p l i n g s t r e n g t h 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对 本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签名： 年月 第一章绪论 1 1 复杂网络研究的意义 复杂网络是近年来发展起来的一门新兴交叉学科，用来描述和理解复杂系统我 们都的生活在各种不同的网络中，作为不同类别的节点存在，从这个意义上说，网络无 处不在，自然界和人类社会中存在的大量复杂系统都可以通过形形色色的网络加以描 述，任何一个复杂系统都可以抽象成由相互作用的个体构成的网络，其中个体抽象为 网络节点，个体间的相互作用抽象为网络连边和传统的还原论方法不同，复杂网络从 整体的角度和系统的观点出发来研究和认识复杂系统，关注于个体间的相互作用，从 而预测系统整体所表现出来的丰富的集体行为最近几年，由于计算机数据存储和运 算能力的飞速发展，给复杂网络的研究提供了坚实的技术基础对复杂网络的研究已 经成为了统计物理学的一部分，利用统计物理的手段发掘规模巨大而又复杂无比的网 络中隐藏的秩序，成为了物理学家们的基本任务之一然而任何一种复杂系统都十分 庞大并且具有自身的特殊性，需要多学科研究人员的共同努力和学科的交叉，复杂网 络的发展得益于各个学科的齐头并进早期对网络的研究主要由数学家们从图论的角 度出发进行，最简化的模型称为随机图( r a n d o mg r 印h ) ，然而随着科学技术的进步和 研究的不断深入，人们发现真实网络既不是规则网络，也不是随机网络，而是具有与前 两者皆不同的统计特征的网络复杂网络两项开创性的工作是由w 乱t s 和s t r o g a t z 在 1 9 9 8 年提出的小世界网络【1 】和b a r a b 缸i 和a l b e r t 在1 9 9 9 年提出的无标度网络f 2 】 这两项工作揭示了形形色色的网络结构具有普遍的、非平凡的特性，彻底颠覆了人们 对真实网络的传统认识，从而掀起了一股复杂网络的研究热潮在这些发展趋势和环 境的推动下，复杂网络的研究得以迅猛的发展，提出了很多崭新的观念和研究方法。 到目前为止，复杂网络研究已经涉及了数学、物理、化学、生物学、技术和社会科 学等多个领域，取得了可喜的阶段性成果其中颇具代表性且得到广泛研究的网络有 互联网、万维网、人际关系网络、科学家合作网络、航空网、铁路网、电力网、蛋白质 相互作用网络、新陈代谢网络、基因调控网络和疾病传播网络等【3 _ 7 】随着互联网等 大型通讯网络的广泛应用，网络规模变得越来越庞大，网络结构也越来越复杂，特别 是网络的拓扑结构也在不断的变化之中，这使得基于网络全局拓扑信息的传统路由策 略遭受日益紧迫的存储和计算能力的压力研究信息网络对解决日益严重的信息拥塞 问题，设计下一代通讯网络至关重要【2 0 l ；对电力网络的研究成果指出造成巨大经济损 失的大停电现象可能源于电力网中的雪崩级联效应，并且为避免这种灾难提供了有效 l 2 第一章绪论 的解决途径【7 】；系统生物学是近年来快速兴起的一门集生物学、计算机科学、数学等 学科于一身的交叉科学，试图解决“中心法则”所不能解决的问题。一些研究工作表明 生物网络中的一些特定结构( 比如模块结构m o d u l a rs t r u c t u r e ) 和一些特定的生物学功 能存在某种联系【2 2 】，这为更加深入地了解生物系统的功能提供了崭新的途径；互联网 上的数据包传播和病毒传播同样需要研究和规范，这两个研究的目的相反，前者需要 解决信息传播的流畅问题，后者则主要考虑如何有效地抑制病毒的扩散。传染病传播 问题，比如s a r s 、a i d s 和禽流感病毒等，如何抑制其扩散一直是一个世界性的难 题研究复杂网络上的病毒传播比传统的病毒传播研究更加贴近真实和有效【2 3 i 可以 看出，对复杂网络的研究极其重要小到电路板布线，大到城市和城市间交通规戈4 ，整 个国家的能源，电力等等的决策，乃至政治体间经济军事上的对抗与合作，这些对种种 类型的真实网络进行最优化的设计抑或是最有效的破坏，无不属于网络的研究范围。 网络结构如何影响发生于其上的动力学过程是网络研究的根本问题，网络上的传 播和耦合动力学过程是其中重中之重很多动力学过程最终都可以归结为传播和耦合 过程，我们在后面的章节中将详细的介绍下面我们先结合前人的工作简单介绍复杂 网络研究的一些成果和现状 1 2复杂网络的统计特性 历史上，网络的研究主要是离散数学的分支一图论的范畴。自从1 7 3 6 年瑞士数学 家欧拉( l e o n h a r de u l e r ) 发表哥尼斯堡桥问题的解，图论已经取得了很大的进展。过 去的1 0 年，复杂网络的研究在兴趣和研究方面有了新的发展，研究重点从分析小网络 转向研究包含成千上亿个节点的网络系统，重新关注由动态个体组成的网络的属性 对社会、技术和生物网络的实证数据统计结果表明真实网络普遍存在一些共同的拓扑 特性真实网络大都具有较短的平均距离和高的聚集性，而且部分网络具有幂函数律 的节点度分布人们一时难以理解这些复杂的结构，因此称这些网络为复杂网络下 面我们介绍一些用来描述网络特征的统计量的定义和有关现象 最短距离( s h o r t e s tp a t h ) 、平均最短距离( a v e r a g es h o r t e s tp a t h ) ，介数 ( b e t w e e n n e s s ) ：节点间最短距离是指从一个节点出发到达另外一个节点所要经过最 少连边数目，其中最大值称为网络的直径；网络的平均距离定义为网络中所有两节点 间的最短距离的平均值节点( 边) 的介数是通过该点( 边) 的网络最短路径个数，因 为两节点间的最短路径可能存在多条，因此介数可能是一个非整数 小世界( s m a l lw o r l d ) ：自从1 9 9 8 年w a t t s 和s t r o g a t z 提出小世界网络模型后， 1 2 复杂网络的统计特性 3 小世界概念就深入人心，和复杂网络的概念交织在一起小世界( s m a uw o r l d ) 的概念 来源于真实网络虽然规模很大但是节点之间的平均距离却往往很小的现象真实网络 普遍具有小世界性质，比如电影演员合作网、万维网、食物链网等【3 1 小世界性质明 确的定义为：如果一个网络的平均最短距离随网络规模增加呈对数速度或小于对数增 加，那么该网络具有小世界性质【引一些设计的网络如e r d 6 s r 6 n 妒( e r ) 随机图已经 被证明也具有这样的性质【2 5 】和随机网不同的是，小世界属性在真实网络中经常伴随 着聚类现象 度分布( d e g r e ed i s t r i b u t i o n ) ：某个节点的度表示连接到该节点上的边的数目， 也就是该节点的直接邻居数一般情况下，网络中不同节点的度并不相同，因此网络 中度的分布规律也是刻划网络特点的一个重要参量随机图的节点度很接近于网络的 平均度( 七) ，度分布p ( 尼) 服从峰值在( 庇) 处的p o i s s o n 分布而大量真实网络，节点度 分布满足幂率分布【3 ，4 1 p ( 七) 一向一7 ( 1 1 ) 簇系数( c l u s t e r i n gc o e m c i e n t ) 、分层结构( h i e r a r c h i c a lo r g a n i z a t i o n ) ：节 点t 的簇系数定义为它所有相邻节点之问连边的数目占可能的最大连边数目的比例 g = 鼎。 ( 1 2 ) 其中勉是该节点的度，舷是该节点邻居间的实际连边数网络的簇系数则是所有节 点簇系数的平均值簇系数用来表征系统内的成团特性的一个统计量簇系数还用来 表征网络的分层结构，实证研究发现大量的实证网络，如互联网、w w w 网、演员合 作网、语义网，都具有分层特性( 8 】，如图1 1 所示所以，网络的分层特性也是普遍 存在的，因而也是复杂网络的一个基本特征量研究还发现真实网络的簇系数远大于 规则网络、e r 随机网络和得到广泛认可的b a 网络，这表明这些网络还不足以刻画 真实网络，创建可以描写真实系统的网络模型，依然是一个重要而艰巨的任务 相配混合性( a s s o r t a t i v em i x i n g ) ：相配混合性也称作度一度相关性( d e 铲e e _ d e g r e ec o r r e l a t i o n ) ，定义如下( 2 8 】： ( 1 3 ) 其中五和分别是边t 两端的两个节点的度i = 1 ，m ( m 网络中总边数) 用来 刻画邻居节点度之间的相关关系根据相配系数值，网络可以分为正相配网络和负相 配网络。正的相配系数表明度大的节点倾向于和度大的节点相连，度小的节点倾向于 和度小的节点相连；负的相配系数表示度大的节点倾向于和度小的节点相连有意思 一俨 p 一觑m l 十募 垫旷 m j j 二蟹 觑一+ a； 互如 型屯砑 1 2 复杂网络的统计特性 5 图1 2 所有含有三个点的有向连通子图的1 3 类小图，摘自文献【1 2 1 得多【1 4 1 在人际关系网中，通常情况下会按照不同的兴趣、财富、年龄等等划分出不 同的人群图1 3 画出了一所美国中学的学生间的朋友关系图( 1 5 j ，图中不同颜色的点 表示不同种族的学生通常情况下，不同种族的学生处于不同的群落中，并且由于学 生处于不同的学习阶段( 初、高中) 而接触较少，网络被分成四个部分，分别为：自人初 中生( 左) 、白人高中生( 下) 、黑人初中生( 上) 和黑人高中生( 右) 这四个部分就形 成了网络中的四个社团，在每个社团内部学生间的联系很密切，但在不同的社团间， 只有少部分人会成为朋友大量的实证研究表明，绝大多数的真实网络都具有社团结 构【1 4 - 16 1 但是判断一个网络是否一定含有社团结构，如何划分社团，还是一个尚未解 决的问题，这和社团的定义的模糊性有很大的关系人们已经提出很多社团划分的算 法，但是各种算法对同一个网络划分出来的社团社团一般会有较大的差别文献上也 出现了提出各种指标来比较各种算法优劣的研究，但总的来说人为的因素较大，很难 得到一个公认的结论现在已经了解的所有大型网络，包括i n t e r n e t 、w w w 网、演 员合作网、人际关系网和蛋白质相互交互网等等，都公认是具有社团结构的网络。 长期以来，人们都相信一些全局的性质，比如小世界特性、度分布特性、簇系数 等，特别是度分布特性，可以刻划复杂网络的特性最近的研究显示，上述全局特性没 有能够抓住网络结构核心问题f 1 6 | 只有当下述条件满足的情况下，这些全局特性才是 有很大意义的统计参量：( 1 ) 所研究的网络没有社团结构或者，( 2 ) 所研究的网络存 在社团结构，但是，( 2 1 ) 所有的社团都是按照同一个机制形成的，因此各社团具有相 似的性质；( 2 2 ) 除了连边的密度不同之外，社团内和社团间的统计特性相似就到目 前为止的研究成果来看，绝大多数真实网络都无法满足上述两个条件的另外，生物 网络中的模块( 社团) 被认为是和特定的生物学功能存在某种关系的基本单位因此， 网络的社团特陛的研究已经成为当前复杂网络研究中的一个十分重要的，具有极大应 1 3 复杂网络模型 7 o ” p p 隶没。 。二一。置。 ；c ? l p 、，x 、 i 一 。 、k ：、i ” 。 ， cw w w 。吨t 霸惫。 ；_孙。-t1-t 。 -t “f 、 24 81 63 2 图1 4w w w 网和演员合作网的自相似特性上图显示的是w w w 网和演员合作 网的自相似关系，下图显示的标度因子和尺度的关系摘自文献【1 8 】 ( 包括河流、机场、街道、铁路和公路) 等等，这类网络由于受到地理位置的约束，和一 般的拓扑网络的性质存在一些不同，比如电力网络的度分布就不符合幂率分布而是一 个指数分布由于这类网络在社会经济生活中所占据的的重要地位，这类网络的研究 正变得越来越不可避免 通过以上讨论，我们很容易看出真实网络所具有的一些共同的特性。一般来说，真 实网络一般具有小世界特性、无标度特性、高簇系数、社团特性、自相似特性一个好 的复杂模型需要能够重现尽可能多的真实网络所具有的拓扑特征下面我们回顾一下 一些具有代表性的复杂网络模型最著名的两个复杂网络模型是由w a t t s 和s t r o g a t z 在1 9 9 8 提出的小世界网络模型( w s ) 【1 j 和由b a r a b 缸i 和a l b e r t 在1 9 9 9 年提出的无 标度网络模型( b a ) 【2 1 ，这两个模型的出现，奠定了复杂网络研究的基础 1 3 复杂网络模型 e r 模型； 在二十世纪5 0 年代，匈牙利数学家p e r d 6 s 和a r 6 n y i 提出，用随机作图理论 来分析网络的拓扑复杂性f 2 5 】他们的这一理论后来成为分析网络的经典数学方法，被 称为“e r 理论”，其研究的网络则被称为“e r 模型”在小世界网络和标度网络提 壮 拂 挑 抄 拙 乏龟，)mjv 8 第一章绪论 r 8 喇0 # o 桊 妒= 擎净茹= f n c l t e a 售舯gr a n d o m n e s $ 黧羔。5 点墨：显示耋连概率爹麸q 戮王增加，潮络缝构的燮诧。下露；w s 小世券 网络的平均距离粕簇系数。摘塞文献【l | 。 出以前，e r 网络是研究各种笈杂问题的首选理论网络模型e r ，模型构建规劂非常 简单，即在定数量的节点之间按照莱个给定的概率p 在任意两点间添加连边该霹 络模型具有小毯界特性，度分布籍合治羧分帮。 w s 模型 l 】：l 8 年，w a t s 穰啦o g 熊晷在n & t u r e 上发表文鬻，提出了小嫠界 网络模型，揭开了现代复杂网络研究的序幕小世界阿络从一个规刘环丽出发，每条 边按照概率爹进行断遍重连，禁止宣连逸帮萋连逸。这种断边过程使褥嬲络中窿瑰长 程连接，但惩耐减少了网络中三角形的数晷豳1 5 上飕显示通过改变p ，可以观察 网络从完全规煲| j 图印= o ) 到完全随机图的转交函= 王) w s 网络的两个浆型特征是平均距离短和簇系数大，并盥都随妒可调匿王5 下圈 曼豢了特征距离z ) 勰簇系数秽) 与参数筘的函数依赖关系，数据必对z ( o ) 和g ( o ) 归一化的结果可以稽到在中闻一段区域，p 在大约o 。o o l 到o 1 的变化范围内，网络 既有短酶平均距离又有高翁簇系数这一莲域与粪实溺络一致，我稍称这个区域鹳鼹 络势夺世赛疆终 b a 摸型【2 l ；一个典型的b a 瞬络可以邋过所谓的节点增加和偏好选撵机制( p r e f _ 裂e 躐激融t 氇e 妇l e 嫩) 产生。网络从少数几个完全连通的种子节点开始演化每时闻 1 3 复杂网络模型 9 1 0 0 1o 2 ，o 、 邑1 0 。 1 矿 1 0 - b k 图1 6b a 网络的度分布，虚线的斜率为2 9 ，网络初始参数为m = m o = 5 ，分别 为1 5 0 0 0 和2 0 0 0 0 摘自文献【2 1 步加人一个新节点到已经存在的网络中这个新节点的m 条边连接到m 个不同的已 经存在的节点上老节点被新节点连接的概率正比于该老节点的连接度，即 h ( 觑) = 若( 1 4 ) l jq t 时间步后，网络包含= t + m o 个节点和m t + 0 条连边m o 和o 是初 始种子节点数目和初始边的个数基于平均场假设的理论分析可以证明，以这样的机 制生成的无标度网络，当节点数_ 时，其度分布的幂指数7 _ 3 ，平均距离 ：一抚( ) ，簇系数e 枷。7 5 ，并且如图1 6 所示，在双对数坐标下，度分布为一条 直线，斜率为2 9 权重网络模型：近年来越来越多的实证数据表明用单纯的拓扑网络来描述真实网 络是远远不够的。纯拓扑网络会丢失连接边上很重要的物理信息，即连接强度权重网 络的描述方法为研究网络拓扑结构和权重的共演化提供了便捷的途径而且近年来越 来越多的含有权重的网络实证的获得使得研究权重网络的演化成为可能通过对实证 数据的分析，人们发现了很多有趣的现象，包括连接度、点权( s t r e n 酗h ) 和边权( w e i 曲t ) 分布的无标度特性，以及度和权重的非线性关系等2 0 0 1 年以来，人们提出了很多权 重网络模型，都在不同程度上反映了真实网络的一些特征其中由b a r r a t 等人【3 1 】在 1 0第一章绪论 图1 7b b v 网络的权重分布图，摘自文献 3 2 0 0 4 年提出的演化权重网络模型( b b v ) 比较具代表性的一个模型该模型考虑了权 重和拓扑结构在演化过程中的耦合，生成的网络具有无标度特性的节点度，节点权和 边权分布，如图1 7 所示 1 4网络上的传播和耦合动力学过程 研究复杂网络的最终目标是理解各种网络的功能网络的功能