（理论物理专业论文）复杂网络的演化动力学及网络上的动力学过程研究.pdf

摘要 复杂网络是研究复杂系统的一门新兴学科，近几年受到国内外研究学者的广泛关注 任何复杂系统都可以抽象成为由相互作用的个体组成的网络，因而网络无处不在，遍及 自然界和人类社会其中颇具代表性且受到广泛研究的网络有互联网、万维网，铁路网、 航空网、电力网、蛋白质相互作用网，新陈代谢网，基因调控网和各种合作性的网络等 研究这些网络不仅对人们的工作和生活至关重要，而且对了解自然界特别是生物系统的 奥秘有深远的科学意义 另一方面，复杂网络研究关注个体之间的微观相互作用导致的系统的宏观现象。这 种将系统行为作为一个整体的研究方式不受传统还原论方法的限制，从而能够预言复杂 系统丰富的整体行为，包括自组织特性，涌现等这使得以网络的方式研究复杂系统成 为了必然趋势同时，复杂网络的研究热潮促进了学科之间界限的打破，推动了统计物 理，非线性动力学，应用数学、信息工程社会学和生物学等多学科的交叉和发展因 此，复杂网络研究具有重大的理论价值 研究复杂网络的最终目标是理解网络上的各种动力学过程如何受到网络结构的影 响，而网络的形成和演化机制决定网络的结构因此研究网络结构的演化动力学成为了 复杂网络研究的前提和热点之一根据当前国内外复杂网络的研究动态和发展趋势，我 们在网络结构的演化动力学机制和网络上的动力学过程方面做了比较系统的工作，涉及 权重网络的演化、网络上的信息流、博弈过程，病毒传播和同步现象以及布尔动力学等 本文的主要工作如下 提出了交通流驱动机制、双向选择机制和双向吸引机制，建立了一系列权重网络演 化模型，重现了实际权重网络中所观察到的节点权重，边权重和连接度的幂率特性，以 及小世界特性，节点度和权重的非线性相关性等基于这三种机制的模型分别得到了负 的相配混合性，分层特性和正负可调的相配混合性，从而能够很好地刻画技术网络，社 会网络和生物网络这三大类真实网络，并且回答了复杂网络研究十大问题之一的相配混 合性问题。 系统地研究了无标度网络上的交通动力学我们提出了基于局域拓扑和动态信息的 数据包路有规则。研究了系统中信息流从自由流到阻塞流的相变特性，并利用这一特性 刻画网络的通讯能力我们还发现无标度网络上交通动力学存在着迟滞回线和亚稳态的 行为我们的研究对于目前路由协议的优化以及新一代路由协议的设计有一定的指导意 义 研究了无标度网络上的同步，提出通过去耦合过程来提高网络的同步能力此外， 摘要 研究了具有群落结构的无标度网络上的病毒传播，发现病毒传播中存在同步现象，并且 同步现象随着群落结构强度的改变存在相变我们运用有限尺度分析方法计算了相变指 数并指出相变的普适类 探讨了丽络上的演化博弈。提出基于个体历史记忆的演化机制、偏好学习机制和博 弈与网络结构的共演化，能够很好地解释实际中普遍存在的和合作现象而且我们发现 了合作频率的分段和非单调行为、斑图相变无标度网络的涌现、随机共振现象和双稳 态行为等 提出运用动力学粗粒化的方法来研究无标度布尔网络在混沌区域的动力学特性，发 现系统状态空间网络具有五种幂律分布特性进一步将布尔动力学应用到真实的细胞及 雹子基因调控网络，发现了动力学核心模块和控制细胞与雹子之间相互转化的两条关键 通路，并运用动力学的方法对不同条件下表达的基因调控网络进行分类，得到很好的结 果。通过研究不同条件下基因调控网络的d e r r i d a 曲线，我们发现正常细胞更加接近于 混沌的边缘，这验证了k a u f f m a n 提出的混沌边缘假说 关键词t 复杂网络；演化权重网络；网络上的信息流；网络上的博弈；布尔动力学； 基因调控网络 a b s t r 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 n ta p p r o a c hf 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 ac o m p l e xs y s t e mi sc o m p o s e do fm a n y i n t e r a c t e di n d i v i d u a l s 。w h i c hc a nb en a t u r a l l yr e p r e s e n t e db yag r a p hw i t hi n d i v i d u a l s d e n o t e db yn o d e sa n di n t e r a c t i o n sb yl i n k s f r o mt h i sp o i n to fv i e w ，c o m p l e xn e t w o r k s a r eu b i q u i t o u s ，r a n g i n gf r o mn a t u r et os o c i e t y i nt h ep a s tf e wy e a r s ，w eh a v ew i t n e s s e d ag r e a td e v o t i o no fs c i e n t i s t s t ou n d e r s t a n d i n gt h eu n d e r l y i n gm e c h a n i s m so fc o m p l e x n e t w o r k st o g e t h e rw i t ht 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 t h ea d v a n c e s o fc o m p l e xn e t w o r k sa r ep r o p e l l e db ys e v e r a lp a r a l l e ld e v e l o p m e n t s ，i n c l u d i n gt h ec o i n - p u t e r i z a t i o no fd a t aa c q u i s i t i o n ，i n c r e a s eo fc o m p u t i n gp o w e r ，b r e a k d o w no fb o u n d a r i e s b e t w e e nd i s c i p l i n e sa n di n c r e a s i n gn e e d sf o ru n d e r s t a n d i n gt h eb e h a v i o ro fa ni n t e g r a t e d c o m p l e xs y s t e ma saw h o l e s i n c et h eg r o u n d w o r kl a i db yb a r a b a s i ，a l b e r t ，w a t t sa n d s t r o g a t z ，m o r ea n dm o r ea t t e n t i o nh a sb e e ng i v e nt ot h i se m e r g i n gf i e l d t h ew i d e l y o b s e r v e d s m a l l - w o r l d ”a n d “s c a l e - f r e e p r o p e r t i e ss h a r e db ym a n yr e a ln e t w o r k sh a v e n o wc 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 n d 嗍nk n o w l e d g eo fm a n y p e o p l eo nt h e r e a l - w o r l dn e t w o r k 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 a r ys c i e n t i f i c 丘e l d s of a r ，t h ei n v e s t i g a t i o no fc o m p l e xn e t w o r k sh a sc o v e r e dm a n yf i e l d s ，i n c l u d i n g p h y s i c s ，c h e m i s t r y , t e c h n o l o g ya n db i o l o g y , w h e r ei n t e n s i v e l ys t u d i e dn e t w o r k sc o v e ra sd i - v e r s e8 8t h ei n t e r n e t ，w o r l dw i d ew e b ，p o i n t - t o - p o i n tn e t w o r k s ，c o l l a b o r a t i o nn e t w o r k s ， a i r p o r tn e t w o r k s ，p o w e rg r i ( i 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 s ，g e n e t i cr e g u l a t o r y n e t w o r k sa n de p i d e m i cs p r e a d i n gn e t w o r k s ，e t c t h e s en e t w o r k sa r eo fh i g ht e e h n o l o g - i c a la n di n t e l l e c t u a li m p o r t a n c ea n dt h ed e s i r et ou n d e r s t a n ds u c hi n t e r w o v e nc o m p l e x s y s t e m sh a se n c o u n t e r e ds i g n i f i c a n tc h a l l e n g e sa sw e l l t h eu l t i m a t eg o a lo fs t u d y i n g c o m p l e xn e t w o r k si st ou n d e r s t a n dh o wt o p o l o g i c a lp r o p e r t i e sa f f e c tt h ed y n a m i c a lp r o - c e 联瞄t a k i n gp l a c eo nt h e m h o w e v e r w h a ts h o u l db ef i r s td o n ei st od e e p l yu n d e r s t a n d h o wc o m p l e xn e t w o r k sp o s s e s st h o s ec o m m o nt o p o l o g i c a lf e a t u r e si na s a l f - o r g a n i z e dw a y i n s p i r e db yt h ec u r r e n ti n 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 ee v o l u t i o n a r y d y n a m i c so ft h en e t w o r ks t r u c t u r e sa n dt h ed y n a m i c a lp r o c e s s e so c c u r r i n go v e rc o m p l e x n e t w o r k s o u rw o r kc o n t a i n st h ee v o l u t i o no fw e i g h t e dn e t w o r k s ，i n f o r m a t i o nt r a f f i c s o ns c a l e - f l e en e t w o r k s ，s y n c h r o n i z a t i o no nn e t w o r k s ，e v o l u t i o n a r yg a m e so nn e t w o r k s ， m a b s t r a c t b o o l e a nd y n a m i c sa n dg e n e t i cr e g u l a t o r yn e t w o r k s w eh a v ep r o p o s e ds e v e r a le v o l u t i o n a r ym o d e l sf o rw e i g h t e dn e t w o r k s ，i n c l u d i n gt h e t r a f f i cd r i v e nm o d e l ，t h em u t u a ls e l e c t i o nm o d e la n dt h em u t u a la t t r a c t i o nm o d e l t h e w e i g h t e dn e t w o r k sg e n e r a t e db ys u c hm o d e l sp o s s e s sp o w e r - l a wd i s t r i b u t i o n so f s t r e n g t h s ， w e i g h t sa n dd e g r e e sw i t ht h ee x p o n e n t st u n e db ym o d e lp a r a m e t e r sb e t w e e n2 3 ，w h i c h a r ew e l lc o n s i s t e n tw i t ht h ee m p i r i c a le v i d e n c e i np a r t i c u l a r ，t h ew e i g h t e dn e t w o r kg e n - e r a t e db yt h et r a f f i cd r i v e nm o d e lh a sad i s a s s o r t a t i v em i x i n gp r o p e r t ya n dan o n l i n e a r c o r r e l a t i o nb e t w e e ns t r e n g t ha n dd e g r e e ，w h i c ha r ei ng o o da g r e e m e n tw i t hr e a lw e i g h t e d t e c h n o l o g i c a ln e t w o r k s f o rt h em u t u a ls e l e c t i o nm o d e l ，t h eo b t a i n e ds t a t i s t i c a lh i e r a r - c h i c a lp r o p e r t yb yt h em o d e lc a nw e l lr e p r o d u c et h er e a lo b s e r v a t i o n sa b o u tw e i g h t e d s o c i a ln e t w o r k s t h em u t u a la t t r a c t i o nm o d e lc a ng e n e r a t en e t w o r k sw i t hb o t ha s s o r t a - t i r ea n dd i s a s s o r t a t i v em i x i n gp r o p e r t i e s ，i n d i c a t i n gt h a tt h em o d e lc a nw e l lm i m i cs o c i a l n e t w o r k s ，t e c h n o l o g i c a ln e t w o r k sa n db i o l o g i c a ln e t w o r k s e s p e c i a l l y , o u rw o r kh a sp r o - v i d e dag o o da n s w e rt oo n eo ft h et e nl e a d i n gq u e s t i o n si nt h es t u d yo fc o m p l e xn e t w o r k s ： w h ya l ls o c i a ln e t w o r k sa r ea s s o r t a t i v e ，w h i l et e c h n o l o g i c a la n db i o l o g i c a ln e t w o r k sa r e d i s a s s o r t a t i v e ? w eh a v es y s t e m a t i c a 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 nt r a f f i c so v e rs c a l e - f r e en e t w o r k s s e v e r a lr o u t i n gs t r a t e g i e so fm a n a g i n gd a t ap a c k e t sh a v eb e e np r o p o s e d ， i n c l u d i n gt h el o c a lr o u t i n gs t r a t e g ya n dt h em i x e dr o u t i n gs t r a t e g yb a s e do nl o c a ls t a t i c a n dd y n a m i ci n f o r m a t i o n w ec a nq u a n t i f yt 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 nf r o mf r e ef l o ws t a t et oc o n g e s t i o ns t a t e ，a n dw eh a v ef o u n dt h eo p t i m a lp a r a m e t e r v a l u e so fe a c hm o d e l ，r e s u l t i n gi nt h eh i g h e s te f f i c i e n c yo fs c a l e - f r e en e t w o r k e dt r a f f i cs y s - t e r n s ，m o r e o v e r w eh a v ef o u n dh y s t e r e s i sl o o pi nn e t w o r k e dt r a f f i cs y s t e m sw i t haf i n i t e p a c k e t - d e l i v e r i n ga b i l i t y s u c hh y s t e r e s i sl o o pi n d i c a t e st h ee x i s t e n c eo fb i s t a b l es t a t e si n t h et r a f f i cd y n a m i c so v e rs c a l e - f r e en e t w o r k s w eh a v es t u d i e dt h ec o l l e c t i v es y n c h r o n i z a t i o nb e h a v i o ro v e rs c a l e - f r e en e t w o r k sa n d p 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 e h r o n i z a b i l i t yo fs c a l e - f r e en e t w o r k s b e c a u s eo ft h el o wc o s ti np e r f o r m i n gt h i st a s k ，t h ed e e o u p l i n gp r o c e s sm e t h o dm a yh a v e v e r yg o o dp o t e n t i a la p p l i c a t i o n s f u r t h e r m o r e ，w eh a v ei n v e s t i g a t e dt h ee p i d e m i cs p r e a d - i n go v e rs c a l e - f r e en e t w o r k sw i t hc o m m u n i t ys t r u c t u r e sa n df o u n dt h e i rs y n c h r o n i z a t i o n b e h a v i o r i n t e r e s t i n g l y , t h e r ee x i s tp h a s et r a n s i t i o n so ft h es y n e h r o n i z a b i l i t yd e p e n d i n g o i lt h es t r e n g t h so ft h ec o m m u n i t ys t r u c t u r e si nt h en e t w o r k s o nt h eb a s i so ft h e 丘n 蚍 v s i z es c a l i n g ，w eh a v eo b t a i n e dt h ev a l u e so fp h a s et r a n s i t i o ne x p o n e n t s ，i n d i c a t i n gt h a t t h ep h a s et r a n s i t i o n sb e l o n gt ot h em e a n - f i e l dt y p e w eh a v es y s t e m a t i c a l l ys t u d i e dt h ee v o l u t i o n a r yg a m e so nn e t w o r k s am e m o r y - b a s e ds n o w d r i f tg a m eh a sb e e np r o p o s e d w ef o u n dt h a ti nr e g u l a rl a t t i c e s ，t h ec o o p e r a - t i o nl e v e lv e r s n 8p a y o f fp a r a m e t e rs h o w sas t e ps t r u c t u r ew i t he a c hs t e pc o r r e s p o n d i n gt o at y p i c a ls p a t i a lp a t t e r n t h e r ei sas h a r pp a t t e r nt r a n s i t i o nb e t w e e na n yt w od i f f e r e n t p a t t e r n s t h i si n t e r e s t i n gp h e n o m e n o nh a sn o tb e e nr e p o r t e dp r e v i o u s l y f o rs c a l e - f r e e n e t w o r k s ，t h ec o o p e r a t i o nl e v e lv e r s u sp a y o f fp a r a m e t e ri nt h em e m o r y - b a s e ds n o w d r i f t g a m ed i s p l a y sn o n - m o n o t o n o u sb e h a v i o rw i t hc o o p e r a t i o nl e v e lp e a k i n ga ts o m es p e c i f i c p a r a m e t e rv a l u e s w h i c hs u g g e s t st h a ts u i t a b l ee n c o u r a g e m e n to fs e l f i s hb e h a v i o rc a nl e a d t ot h eo p t i m a lc o o p e r a t i o nl e v e l w h e r e a f t e r ，w ep r o p o s e da ne v o l u t i o n a r ym o d e lb yc o u p l i n gt h ee v o l u t i o no fg a m e s a n dt h en e t w o r k i ti sf o u n dt h a tt h ec o o p e r a t i v eb e h a v i o rc a nb ec o n s i d e r a b l yp r o m o t e d a n dt h es c a l e - f r e ea sw e l la sn s s o r t a t i v em i x i n gt o p o l o g i c a lp r o p e r t i e sc a ne m e r g ef r o m t h ec o e v o l u t i o n f u r t h e r m o r e ，w eh a v ep r e s e n t e dap r e f e r e n t i a ll e a r n i n gm e c h a n i s ma n d i n v e s t i g a t e dt h ee v o l u t i o n a r yg a m e so nw e i g h t e da d a p t i v en e t w o r k sf o rb e t t e rm i m i c k i n g t h ew i d e l yo b s e r v e dc o o p e r a t i o nb e h a v i o r b e s i d e s ，b ya d o p t i n gt h eh o m o g e n o u ss m a l l - w o r l dn e t w o r k s ，w eh a v ee x p l o r e dt h ee f f e c t o fr a n d o m n e s si ne v o l u t i o n a r yg a m e sa n d f o u n dc o h e r e n c er e s o n a n c ep h e n o m e n at h e r e i n i no r d e rt ou n d e r s t a n dt h ed y n a m i c a lp r o p e r t i e si nt h ec h a o t i cr a n g eo fs c a l e - f r e e b o o l e a nn e t w o r k s ，w ep r o p o s e dad y n a m i c a lc o a r s eg r a i n i n gm e t h o dp e r f o r m e di nt h e s t a t es p a c e i ti sf o u n dt h a tt h ew e i g h t e da n dd i r e c t e ds t a t eg r a p hp o s s e s s e sf i v ep o w e r - l a wd i s t r i b u t i o n s ，i n d e p e n d e n to ft h es t r e n g t ho ft h ec o a r s eg r a i n i n g f u r t h e r m o r e ，w e h a v ee x p l o r e dt h ed y n a m i c so fr e a lg e n e t i cr e 9 1 1 1 a t o r yn e t w o r k so fc e l l sb yu s i n gt h e b o o l e a nn e t w o r km o d e l i n t e r e s t i n g l y , au n i v e r s a lc o r em o d u l a ri sf o u n d s u b s e q u e n t l y , w ec a nc l a s s i f yt h ec e l l u l a rr e g u l a t o r yn e t w o r k su n d e rd i f f e r e n tc o n d i t i o n si nt e r m so ft h e d y n a m i c a lp r o p e r t i e so ft h ec o r em o d u l a r t h r o u g ht h es t u d yo ft h ed e r r i d a c u r v eu n d e r d i f f e r e n tc o n d i t i o n s ，w ef o u n dt h a tt h en o r m a lc e l li sc l o s e rt ot h ee d g eo fc h a o s ，w h i c h s u p p o r t st h eh y p o t h e s i so fk a u f f m a n k e y w o r d s ：c o m p l e xn e t w o r k ；w e i g h t e dn e t w o r k ；i n f o r m a t i o nt r a f f i c ；e v o l u t i o n - a r yg a m e ；b o o l e a nd y n a m i c s ；g e n e t i cr e g u l a t o r yn e t w o r k 第一章绪论 复杂网络是描述和理解复杂系统的一种很重要的方法复杂网络研究不局限于经典 统计物理的研究框架，从整体的角度来认识和研究复杂系统由于任何复杂系统都可以 从实际背景出发，抽象成由相互作用的个体构成的网络，因此，网络无处不在，并且为 复杂系统研究提供了一个崭新的相对简单的研究平台然而任何一种复杂系统都很庞 大并且具有自身的特殊性，这增加了研究的难度，需要多学科研究人员的共同努力和学 科的交叉，同时也使得复杂网络的研究变得丰富多彩复杂网络的发展得益于各个学科 的齐头并进首先，随着数据采集的计算机化，出现了各种真实网络的拓扑结构的大型 数据库；第二，计算能力的大幅度提高使我们可以研究包含几百万到几十亿个节点的网 络，研究以前计算机能力所不及的问题；第三，学科界限的打破为揭示不同的复杂网络 的共同特性提供了有利的条件；第四，从整体的角度研究系统行为的呼声越来越高，这就 要求对网络结构如何影响其上的动力学过程有一个深入系统的理解在这些发展趋势和 环境的推动下，复杂网络的研究得以迅猛的发展，提出了很多崭新的观念和研究方法 复杂网络两项开创性的工作是由w a t t s 和s t r o g a t z 在1 9 9 8 年提出的小世界网络【l 和 b a r a b 缸i 和a l b e r t 在1 9 9 9 年提出的无标度网络【2 】这两项工作揭示了形形色色的网络 结构具有普遍的、非平凡的特性，彻底颠覆了人们对实际网络的传统认识，从而掀起了 一股复杂网络的研究热潮 到目前为止，复杂网络研究已经涉及了物理，化学、技术和生物等多个领域，取得了 可喜的阶段性成果其中颇具代表性且得到广泛研究的网络有互联网，万维网点对点 网络，合作网络，航空网、铁路网电力网、蛋白质相互作用网络新陈代谢网络，基因 调控网络和疾病传播网络等【州研究互联网等信息网络对解决日益严重的信息拥塞问 题，设计下一代通讯网络至关重要f 8 】；对电力网络的研究成果指出造成巨大经济损失的 大停电现象可能源于电力网中的雪崩级联效应，并且为避免这种灾难提供了有效的解决 途径【7 】；研究生物网络可以超越传统还原论的方法，不受局部研究的限制，从而能够探 究生物系统的整体行为，特别是“涌现”( e m e r g e n c e ) 等独特的现象一些工作已经证明 生物网络中的一些特定结构( 譬如集群结构c o m m u n i t ys t r u c t u r e ) 对应特定的生物学功 能f 9 】。这为更加深入地了解生物系统的功能提供了崭新的途径；目前人类正面l f 缶越来越 多致命病毒的威胁，如a i d s ，s a r s ，h 5 n 1 等在研制出这些病毒疫苗之前，控制病毒 的传播是关键。互联网上的病毒传播同样会造成及其严重的后果，给国家，公司和个人带 来严重的经济损失研究病毒传播的最终目标是找出有效抑制病毒的传播的途径研究 网络上的病毒传播比传统的病毒传播研究更加贴近实际和有效 1 0 1 复杂网络的研究成 1 2 第一章绪论 - - “捌k 拉k _ 4 9 w h - h ra m q b t 山口 m h m * h ，- d it l i j m - 一b - h * ” t i n t i 尼7 4 n - r q m 1 h f i ” 2 s p 一t 口d - ， ，* p k - 弹l n - 埘 2 l 囝1 1 ：复杂网络实证统计，摘自文献【4 1 ， 果不胜枚举，在国内外科研期刊上呈逐年增长的趋势，在国际著名综述性刊物r e v i e w o fm o d e r np h y s i c s 和s i a mr e v i e w 等上也相继刊登了数篇复杂网络综述文章 结构和功能是复杂网络理论研究的两个核心问题结构和功能并非相互独立，而是 存在本质的相互联系通常复杂网络结构决定功能，但是功能反过来也可能影响网络结 构的演化网络结构可以通过统计特性来刻画，功能通常可以由网络上的动力学过程来 反映下面就这两个方面结合前人工作进行简要介绍 1 1网络结构的统计特性；实证研究和建模 遍及社会技术和生物网络的实证数据统计结果表明真实网络普遍存在一些共同的 拓扑特性，如图表1 1 所示真实网络大都具有较短的平均距离和高的聚集性，而且部 分网络具有幂函数律的节点度分布下面结合网络统计拓扑量的定义介绍这些现象及其 分类 小世界：小世界( s m a l lw o r l d ) 的概念来源于真实网络虽然规模很大但是节点之间的 拓扑距离却往往很短的现象距离被定义为节点之间最短路径经过的连接边的数日关 于小世界现象最著名的实验是社会学家s t a n l e ym i l g r a m “l 在1 9 6 7 年发现的吹度分离 ( s i xd e g r e e so fs e p a r a t i o n ) ”现象该实验表明在美国每个人平均可以通过六个认识的人 1 1 网络结构的统计特性：实证研究和建模 3 找到任何个想找的人真实网络普遍具有小世界性质，比如电影演员合作网、万维网、 食物链网等【3 1 另一方面，小世界性质有清晰的数学表达如果距离中心节点距离为r 范围内的节 点数目随着r 的增加呈指数增长。那么网络平均距离就会随着规模的增加呈对数规律增 加很多真实网络和随机网络都具有这样的性质最近小世界性质有更加精确的定义； 如果一个网络的平均距离随网络规模增加呈对数速度或小于对数增加，那么该网络具有 小世界性质1 5 1 e r d s s - r 缸y i ( e r ) 随机图已经被证明具有这样的性质1 1 2 1 簇系数( c l u s t e r i n gc o e f f i c i e n t ) ，社会网络中存在一些“圈子”，这些圈子里的人 往往都互柱认识这种成豳的内在倾向性可以用簇系数来量化m 考虑个节点度为 的节点t 连接了恕个其它的节点如果这个点和它的所有直接邻居构成一个连接极其紧 密的圈子，那么它们之间将会存在( 一1 ) 2 条边那么它们之间实际边的数目与最大 可能的边的数目的比值就是i 点的簇系数 q = 蒜 ( 1 z ) 整个网络的簇系数是对所有节点平均的结果研究发现真实网络的簇系数远大于规则网 络和e r 随机网络，这表明随机网络不足以刻画真实网络 节点度分布( d e g r e ed i s t r i b u t i o n ) ，网络中的节点不一定都有相同数目的邻居。 节点度的弥散性可以反映在节点度的概率分布函数p ( k ) 中在随机网路中。大多数的节 点具有相同的节点度，很接近于网络的平均度( 膏) 随机图的度分布服从p o i s s o n 分布， 峰值在p ( ) ) 处很多真实网络的度分布明显偏离p o i s s o n 分布，这是很有趣的现象 一些特别大规模的网络。如万维网、互联网、蛋白质相互作用网络等【3 一，度分布的尾 部显示出幂律分布特性 p ( k ) 一k 一 ( 1 2 ) 这种具有幂律度分布的网络被称为无标度( s c a l ef r e e 】网络虽然一些网络的度分布不是 标准的幂函数律，但也显著偏离随杌网络的p o i s s o n 分布 相配混合性( a s s o r t a t i v em i x i n g ) 。相配混合性也称作度度相关性( d e g r e e - d e g r e e c o r r e l a t i o n ) ，刻画邻居节点度之间的相关性那么到底是度大的点倾向于互相连接还是 相反? 实际上这两种情况都存在由于节点度是网络重要的拓扑量，相配混合性自然引 起了研究人员相当大的兴趣 前人提出了几种衡量网络扭配性的指标。m a s i o v 等人f 1 3 l 提出了画每一条边两蜷 节点度二维图的方法他们用这种方法研究过蛋白质相互作用网络和互联网的相配性 p a s t o r - s a t o r r a s 等人【1 4 l 提出了一种更为简洁的量化方法，即通过互联网中每个节点的 4 第一章绪论 邻居平均度和原节点度的函数关系来刻画互联网相配性如果得到一个随着节点度的增 加上升的一维曲线，那么网络是正相配混合的用这种方法发现互联网具有负的相配混 合性( d i s a s s o r t a t i v e ) n e w m a a 1 5 】提出了个更加简化的方法，只通过一个系数来刻画 网络的相配混合性如果这个系数为正，网络正相配；为负，网络则为负相配个很有 趣的发现是几乎所有的社会网络都是正相配的，而技术和生物网络都为负相配的1 4 1 到 目前为止还不清楚造成这种差异的原因，也许根本没有个简单的原因 通过以上讨论，我们不难得出真实网络所具有的共性，即小世界特性、无标度特性、 高簇系数和正负相配混合性那么复杂网络建模的目标也自然清楚了一个好的模型需 要能够重现真实网络所具有的拓扑特征复杂网络建模的最终目标是揭示导致真实网络 具有共性的内在机制，而且模型越简单越能够反映背后的本质机理但是由于复杂网络具 有的极高的复杂性，提出非常简单的模型模拟所有的真实网络可能超出我们的想象，因此 需要一个循序渐进的建模过程来更好地理解真实复杂网络的演化机制最著名的两个复 杂网络模型是由w a t t s 和s t r o g a t z 在1 9 9 8 提出的小世界网络模型( w s ) t 1 j 和由b a r a b f i s i 和a l b e r t 在1 9 9 9 年提出的无标度网络模型( b a ) 【2 1 下面简单介绍这两个开创性的工 作 b a 模_ 型1 2 1t 一个典型的b a 网络可以通过所谓的偏好选择机制( p r e f e r e n t i a la t w t a c h m e n t ) 产生网络从少数种子节点开始演化。每一时间步加入一个新节点到已经存在 的网络中这个新节点