（控制理论与控制工程专业论文）复杂网络上的拥塞分析与控制问题研究.pdf

上海交通大学博士学位论文 复杂网络上的拥塞分析与控制问题研究 摘要 2 0 世纪未以来，对复杂网络系统的研究开始更多关注数量众多、连接结构复 杂的实际网络的统计特性及其上发生的动态过程。拥塞现象是发生在通信网络和 交通网络等复杂网络上的一种典型的动态行为。拥塞与搜索及路由优化策略互相 影响、密切相关。和以前的研究不同之处在于，基于复杂网络理论的拥塞、搜索 及路由策略的研究更为关注刚络的结构特性对网络的拥塞、搜索及路由优化策略 的影响，比如是否可以利用网络的局部或者全局拓扑特性来提高搜索以及路由策 略的有效性、路由策略是否会导致网络拓扑结构发生变化从而反过来影响算法的 效率、如何设计对网络拓扑结构变化具有自适应能力的路由策略以及局部优化策 略对无标度网络结构的形成有何影响等。 本文的主要研究内容正是基于各种复杂网络模型，分析不同网络结构上拥塞 产生的原因及其控制策略，并对网络结构和其上发生的动态行为之间的相互影响 关系进行初步探讨，提出了改进的路由策略来提高网络的吞吐量以及传输性能等 动态指标。本文的主要内容和研究成果总结如下： 1 基于b a r a b a s i 和a l b e r t 提出的无标度网络模型，按照节点在网络中的重 要程度将其分类，并通过定义相应的动态过程及性能指标，研究了网络 节点自身容量或者处理速度以及网络的无标度结构特性对拥塞的影响。 提出了相应的控制策略来改善网络的拥塞，发现控制策略是否有效和网 络的拓扑结构紧密相关，相同的策略在不同网络结构中的作用会有明显 不同。特别地，不需要对整个网络施加控制作用，而仅需要对一些最关 键的节点加以控制，就可以得到类似控制所有节点所产生的控制效果。 2 提出了一种结合最短路径路由和局部拥塞检测的改进路由算法，并在具 有可变聚类系数的无标度网络上进行了研究。研究结果表明可以得到一 摘要 个最优参数使得该路由算法具有最好的性能，并且随着搠塞的加剧，最 优参数值随之增加。和最短路径路由算法相比，该算法在捐j 塞加剧的情 形下性能提升更加明显，但是最优参数值几乎不随聚类系数的变化而变 化。 3 进一步研究了可以感知局部拥塞信息的路由算法在不同网络拓扑结构下 的性能，发现在各种拓扑结构下，该路由算法均可以显著的提高网络吞 吐量，并且路由算法的提高程度和网络的异质性有密切关系。 4 研究了梯度网络中的绷塞问题。基于指数可调幂律随机网络，对由其得 到的梯度网络模型的入度分布进行了研究，发现梯度网络的入度分布均 为幂律的。当基础网络的幂律指数y ，2 时，梯度网络的幂律指数和基础 网络的几乎一致，而当ys2 时，梯度网络的幂律指数小于基础网络的指 数。其次，平均度的相变值t 也与幂律指数y 相关，基础网络的幂律指 数越小，其平均度的相变值也越大。特别地，当t 为有限值时，如果平 均度( 七) c t ，那么较为异质的网络容易发生拥塞，而当平均度扯) t 之 后，结论相反，较为同质的网络结构更容易发生拥塞。当平均度( 七) 一m 时，所有网络部将趋于最大拥塞状态。 关键词：拥塞，路由，聚类系数，无标度网络，幂律随机网络，梯度网络 上海交通大学博士学位论文 a n a i j y s i sa n dc o n t r o lo fc o n g e s t i o no n c o m p l e xn e t w o r k s a b s t r a c t i nt h ee n do ft h e2 0 “c e n t u r y , m o r ea n dm o r ea t t e n t i o n si nt h ea r e ao fc o m p l e x n e t w o r kr e s e a r c hh a v eb e e nf o c u s e do nt h es t a t i s t i c s p r o p e r t i e s a n dd y n a m i c a l p r o c e s s e so faw i d ev a r i e t yo fc o m p l e xn e t w o r k sw i t hc o m p l e xs t r u c t u r e s c o n g e s t i o n p h e n o m e n o ni sat y p i c a ld y n a m i c a lp r o c e s sw h i c ht a k e sp l a c eo nc o m p l e xn e t w o r k s s u c ha sc o m m u n i c a t i o nn e t w o r ka n dt r a f f i cn e t w o r k ，e t c t h ec o n g e s t i o n ，s e a r c ha n d o p t i m a lr o u t i n gs t r a t e g yr e l a t et oe a c ho t h e rc l o s e l ya n da f f e c te a c ho t h e rd i s t i n c t l y 。 t h er e s e a r c ho fc o n g e s t i o n ，s e a r c ha n do p t i m a lr o u t i n gs t r a t e g yb a s e do nc o m p l e x n e t w o r kt h e o r yd i f f e r sf r o mt h ep r e v i o u ss t u d i e sa n de m p h a s i z e sm o r eo nt h ee f f e c t s o ft h en e t w o r kt o p o l o g y f o re x a m p l e ，c a nw ed e s i g nc e r t a i nr o u t i n gs t r a t e g i e sw h i c h u s et h el o c a lo rg l o b et o p o l o g yi n f o r m a t i o nt o u p g r a d et h ee f f i c i e n c yo fs e a r c ho r r o u t i n gp r o c e s s ? h o wt h er o u t i n gs t r a t e 画e sa f f e c tt h ef o r m a t i o no fc e r t a i nn e t w o r k s t r u c t u r ew h i l eo nt h ec o n t r a r yb ea f f e c t e db yt h eu l t i m a t en e t w o r kt o p o l o g y ? h o wt o d e s i g nr o u t i n gs t r a t e g yw h i c hc a na d a p tt ot h ec h a n g eo ft h en e t w o r ks t r u c t u r ea n d h o wt h el o c a lo p t i m a ls t r a t e g ya f f e c t st h ef o r m a t i o no ft h es c a l e - f r e en a t u r e ? t h em a i nr e s e a r c ho ft h i sd i s s e r t a t i o ni st oi n v e s t i g a t et h eo r i g i no fc o n g e s t i o no n c o m p l e xn e t w o r k sa n di t sc o n t r o lb a s e do nd i f f e r e n tk i n d so fc o m p l e xn e t w o r k m o d e l s t h ee f f e c t so fn e t w o r ks t r u c t u r eo nt h ed y n a m i c a lp r o c e s s e sh a v ea l s ob e e n s t u d i e da n da l li m p r o v e dr o u t i n gs t r a t e g yh a sb e e np r o p o s e di no r d e rt oi n c r e a s et h e n e t w o r kc a p a c i t ya n do p t i m i z et h et r a n s p o r t a t i o np e r f o r m a n c e t h em a i nc o n t e n ta n d c o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r es u m m a r i z e da sf o l l o w s ： b a s e do nt h es c a l e - f r e en e t w o r km o d e lp r o p o s e db yb a r a b a s ia n da l b e r ta n d t h ed e f i n i t i o no fd y n a m i c a lp r o c e s s e sa n dp e r f o r m a n c ei n d e x ，w ec l a s s i f y n o d e sa c c o r d i n gt ot h e i ri m p o r t a n c ea n ds t u d yt h ee f f e c t so fn o d ec a p a c i t yo r p r o c e s sr a t ea n dt h es c a l e - f r e en a t u r eo ft h en e t w o r kt o p o l o g yo nc o n g e s t i o n n 1 a b s t r a c t s i m u l a t i o nr e s u l t sv e r i f yt h ee f f e c t i v e n e s so ft h ep r o p o s e dc o n t r o ls t r a t e g y a n ds h o wt h a tc o n g e s t i o na n dd e c o n g e s t i o ni nas c a l e f r e en e t w o r ka r e s i g n i f i c a n t l yi n f l u e n c e db yb o t ht h ep r o p e r t yo ft h en o d e sa n dt h es c a l e f r e e f e a t u r eo ft h en e t w o r k e s p e c i a l l y , t h e r ei sn on e e dt oc o n t r o la l lt h en o d e si n t h en e t w o r k a l s o i ti sp o i n t e do u tt h a ts i m i l a rc o n t r o le f f e c tc a nb ea c h i e v e d b yo n l ya p p l y i n gc o n t r o ls t r a t e g yo ns o m em o s ti m p o r t a n th u b n o d e s b yi n c o r p o r a t i n gl o c a lt r a f f i ci n f o r m a t i o ni n t ot h eb a s i cs h o r t e s tp a t hr o u t i n g p o l i c y , w ep r o p o s eac o n g e s t i o na w a r e n e s sr o u t i n gs t r a t e g yw i t hat u n a b l e p a r a m e t e lw ei n v e s t i g a t et h ee f f e c t i v e n e s so ft h ep r o p o s e dr o u t i n gs t r a t e g y f o rs c a l e f r e en e t w o r k sw i t hd i f f e r e n tc l u s t e r i n gc o e f f i c i e n t sa n di nd i f f e r e n t c o n g e s t i o np h a s e s w ef i n dt h a tt h e r ee x i s t sa no p t i m a lv a l u ef o rt h et u n a b l e p a r a m e t e r i nt h ec o n g e s t i o na w a r e n e s s s t r a t e g y a n dt h eo p t i m a lv a l u e i n c r e a s e ss l o w l ya st h et r a f f i ci nt h en e t w o r kb e c o m e sh e a v i e r f u r t h e r m o r e ， t h ep e r f o r m a n c eu p g x a d eo ft h en e wr o u t i n gs t r a t e g yc o m p a r e dw i t ht h eb a s i c s h o r t e s t p a t hr o u t i n gp o l i c yb e c o m e sm o r es i g n i f i c a n t a st h en e t w o r k b e c o m e sm o r ec o n g e s t e d h o w e v e r , t h eo p t i m a lv a l u ei sa l m o s ti n d e p e n d e n t o ft h ec l u s t e r i n gp r o p e r t yo ft h es c a l e f r e en e t w o r k f u r t h e r m o r e w ei n v e s t i g a t et h ee f f e c t i v e n e s so ft h ec o n g e s t i o na w a r e n e s s r o u t i n gs t r a t e g yw i t hat u n a b l ep a r a m e t e ru n d e rd i f f e r e n tt o p o l o g i e s i t i s r e v e a l e dt h a tt h en e t w o r kc a p a c i t yi sg r e a t l ye n h a n c e dw h e nt h en e wt r a f f i c a w a r e n e s sr o u t i n gs t r a t e g yi sa d o p t e di ne a c hn e t w o r ks t r u c t u r e a l s o ，t h e p e r f o r m a n c eu p g r a d eo ft h en e ws t r a t e g yc l o s e l yd e p e n d s o nt h eu n d e r l y i n g n e t w o r ks t m c t n r e w ea l s oa n a l y z et h ec o n g e s t i o np r o b l e mo nt h eg r a d i e n tn e t w o r k i ti sf o u n d t h a tt h ei n d e g r e ed i s t r i b u t i o no ft h eg r a d i e n tn e t w o r kb a s e do nt h ep o w e r l a wr a n d o mg r a p hw i t hv a r i e de x p o n e n ti sa l s oap o w e rl a wd i s t r i b u t i o n t h e p o w e rl a we x p o n e n to ft h eg r a d i e n tn e t w o r ki sa l m o s tu n c h a n g e dc o m p a r e d w i t ht h es u b s t r a t en e t w o r kw i t he x p o n e n tr 2 h o w e v e r ，t h ep o w e rl a w e x p o n e n to ft h eg r a d i e n tn e t w o r ki sl e s st h a nt h es u b s t r a t en e t w o r kw h e n t h e e x p o n e n ty 2 i ti sa l s of o u n dt h a tt h ec r i t i c a lv a l u eo ft h ea v e r a g ed e g r e e k c i sc o r r e l a t i v ew i t h ，ti si n c r e a s e dw h e nri sd e c r e a s e d e s p e c i a l l y ， w h e n 七c i sf i n i t e ，t h em o r eh e t e r o g e n e o u sn e t w o r kt o p o l o g yt e n d st 0b e m a x i m a lc o n g e s t i o nw h e n ( k ) k c ，w h i l et h em o r eh o m o g e n e o u sn e t w o r k 上海交通大学博士学位论丈 t e n d st ob em a x i m a lc o n g e s t i o nw h e n ( k 卜t w h e n ( k ) t e n d st oi n f i n i t e ， a l ln e t w o r k sw i l lb em a x i m a lc o n g e s t i o n k e y w o r d s ：c o n g e s t i o n ，r o u t i n 岛c l u s t e r i n gc o e f f i c i e n t ，s c a l e f r e en e t w o r k ，p o w e r l a wr a n d o mg r a p h ，g r a d i e n tn e t w o r k v 上海交通大学 学位论文原创性声明 术入郊醺声l _ | j j | ：所呈交的学位沦文，魁本人在导螂i f | 勺指导卜独立进 行研究r 作所取徭的成果。除文中已经注明引用的内容外，木论文不包含 任何其他个人或集体已经发表或撰写过的作稿成果。对玮= 文f l 勺研究做i ，n 霞 凄贡献晌个人和集体，均已在文畔，以明确方式标明。本人完全意识到本声 嘲的法律结梁由本人承担。 学位论文作者签名；= 。张每0 夏苏 警簪譬臀零每瞪 上海交通大学 学位论文版权使用授权书 本静论文传者完会了解学皎商父保留、使j j 短论文的舰定，m 意 学饺倪留j ：向蝈客订关部门或机目送交论文的复日j 件，f 订l = ! l f 版，允确：沦义 被轰阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内 容编入何关数据库进行榆索，可以聚，f j 影印、缩印或 l 狲馋复制f 段像存 和汇编本学位沦文。 保密口，在一年解密后适用本援议书。 本学位沦文属于 不保密哦 ( 谤在以上力框内打“4 ”) 学位论文作者签名：体缀 指导教师签名： 日期：2 矾年1 月2 。曰 日期： 斑气自诮 上海交通大学博士学位论文 1 1 引言 第一章绪论 自2 0 世纪9 0 年代以来，人类社会飞速迈入了网络时代。从因特网到万维网、 从大型电力网络到全球交通网络、从科研合作网络到各种经济、社会关系网络等， 人们已经完全生活在一个充满着形态各异的复杂网络的世界中。二十世纪末，被 称为“网络新科学”的复杂网络理论开始逐渐渗透到数理学科以及生命学科和 工程学科等众多不同的领域，它提供了一个全新的视角来研究上述问题，也就 是用网络的观点束研究现实世界的复杂系统【1 4 】。 如果将网络看作足由节点和连接节点的边构成的系统，那么网络无处不在 【5 7 1 。比如生物科学领域的新陈代谢过程可以看作由代谢物( 节点) 和代谢物之 间的化学反应( 边) 构成的新陈代谢网络【8 】：社会科学领域的人际交往可以看 作是由作为个体的人( 节点) 和人与人之间交往形成的关联( 边) 构成的社会关 系网络【9 】。这些网络系统的复杂性主要体现在：节点数量巨大并且类型复杂， 甚至可能是具有分岔和混沌等复杂非线性行为的动力系统；网络结构错综复 杂，并且拓扑结构可能随时间发生变化，节点或边之间的连接强度和方向也可 能不同；各种复杂性因素交互影响，比如节点之间的耦合以及少量节点的状态突 变等，这些局部的扰动往往会对整个网络产生难以预测的影响。 2 0 世纪中叶以来，非线性动力学逐步成为分析复杂系统的基本工具之一，对 网络系统的动力学特性分析受到了很多的关注。绝大多数网络动态系统模型均假 设网络具有固定的规则拓扑结构，通过假设网络结构具有规则拓扑可以使人们集 中精力研究节点的复杂动力学行为对整个网络复杂性的影响 1 0 ，1 1 。统计力学作 为二十世纪物理学的三大革命性理论之一，同样也成为分析复杂系统的基本工 具。物理学家在研究相变和临界现象时，提出了普适性( u n i v e r s a l i t y ) 与标度 ( s c a l i n g ) 这两个非常重要的概念 1 2 ，1 3 1 ，并且推测不仅在物理系统中存在与表 象无关的普遍特性，许多复杂的社会系统、经济系统以及生物系统中也都存在类 似现象。最近的研究也证实许多看似不相关的复杂系统都遵循一定的普遍定律或 第一章绪论 满足一定的标度，比如不列的健康人群在理疗过程中身体指标的输出表现出的相 关性波动和会融资产的波动是一致的【1 4 1 6 】。近年来，随着计算机技术的飞速发 展和通信网络的广泛普及，使得收集和分析大量现实数据成为可能。通过对现实 复杂系统的抽象，并借助图论、统计力学方法、以及非线性动力学分折等一系列 工具，复杂网络理论逐渐形成，并且得到了长足的发展 1 7 ，1 8 1 。 复杂网络理沦使得人们可以对一些原本难以着手的复杂问题进行较为深入 的研究。例如：新陈代谢的过程、生态系统的演变以及因特网的演化是否有共同 之处? 为什么2 0 0 3 年8 月荚国俄亥俄州克利夫兰市的三条超高压输电线路过载 烧断竟然会引起整个北荚地区的大停电事故? 越来越多的研究表明，这些看上去 形态结构各异的网络，比如：万维网、因特网、社会关系网络、经济网络、电力 网络、交通网络以及神经网络等，它们之间竟然有着许多惊人的相似之处，同时 又表现出各具特色的动态特性。如何发现现实世界纷繁复杂的网络的共性，进而 研究各个网络独具的个体特性足复杂网络研究所遵循的研究方向和目的。下面首 先介绍复杂网络的基本概念。 1 2 复杂网络基本概念 复杂网络研究的新纪元始于两篇具有开创性意义的论文。一篇是1 9 9 8 年6 月在 n a t u r e ) ) 杂志上发表的题为“小世界网络的集群动力学”的文章【1 9 】；另一 篇是1 9 9 9 年1 0 月在 s c i e n c e ) 杂志上发表的题为“随机网络中标度的涌现”的文 章 2 0 1 。这两篇文章揭示了现实世界中复杂网络普遍具有的两个特性：小世界及 无标度，并建立了相应的演化模型来阐述这些特性的产生机理。 本节主要介绍复杂网络的一些基本概念，详细的介绍复杂网络的书籍请参看 【2 1 。首先对随机图理论做简单介绍，然后介绍现实世界中复杂网络的统计特性 及其产生机理，最后对复杂网络研究至今所提出的重要模型做相关描述。 1 2 1 随机图理论概要 为了研究不同复杂网络系统在结构上的共性，需要定义一种普适的方式来描 2 上海交通大学博士学位论文 述它，图论( g r a p h t h e o r y ) 足较为合适的工具，因为任何网络系统部可以抽象成 由一些节点按照一定方式连接而成的图。1 8 世纪伟大的数学家e u l e r 在解决著名 的“七桥问题”时提出了图的概念【2 2 】，并由此开创了数学的一个新的分支图 论。对图论的全面介绍可以参看文献 2 3 1 。十九世纪5 0 年代，k o c h e n 等人在研 究社会网络结构时首先提出了随机图的概念 2 4 1 。十九世纪6 0 年代，两位匈牙 利数学家e r d 6 s 和r 6 n y i 对随机图进行了较为系统地研究并得到了许多重要的结 论，由此也带动了图论的快速发展，并在各门学科中得到广泛应用1 2 5 1 。一般研 究者部公认，对复杂网络理论的开创性研究起源于在数学上对随机图理论的系统 分析，下面简要介绍和本文相关的一些随机图理论知识，全面的介绍随机图理论 的著作可以参看文献 2 6 1 。 i e r 随机图( e r d 6 s - r 6 n y ir a n d o mg r a p h ) 模型及其性质 1 9 5 9 年，e r d 6 s 和r 6 n y i 提出了如下随机图模型【2 7 】，也称为e r 随机图：该 图具有个节点，并且节点之i b j 有边相连的概率为p 。因此，具有个节点的 e r 随机图中边的总数是一个期望值为p 【( 一1 ) 2 】的随机变量。产生具有个 节点和 f 条边的e r 随机图的概率为p ”( 1 一p ) ”( “1 ) ，2 一，并且满足条件的图实际 上是一些图的集合，这个集合的大小为 1 ) l ，2 任何一个图在该集合中出现的 概率都是均等的。随机图理论研究具有个节点的图构成的概率空问的特性， 尤其值得关注的是当一m 时该图集的性质。 e r d i s 和r 6 n y i 将概率论中的描述引入到随机图理论中：如果当一0 0 时， 产生具有性质q 的e r 随机图的概率趋于1 ，那么就称该集合中所有随机图部具 有性质q 。连接概率p 不同将产生不一样的随机图集合，如果p 不断增加，最终 可以得到一个具有f 一1 ) 2 条边的完全图。随机图理论研究的一个重要课题 是：p 多大时，e r 随机图会产生一些特殊的属性? e r d 6 s 和r 6 n y i 发现e r 随机 图具有一个重要特性称为相变：即e r 随机图的许多重要性质都是突然出现的， 要么几乎集合中所有的图都具有某个性质q ( 比如连通性) ，要么几乎所有的图 都不具有该性质。换句话说，连接概率p 具有一个临界值，在l 临界值左右区间内 的图具有截然不同的特性，而相同区间内的图总是具有某种相似特性。更通俗地 3 第一章绪论 描述如下：假设地上有j v 个散落的纽扣，以相刚的概二簪p 给每对钮扣系上一根 线，如果你捡起一个钮扣，那么将会有一些钮扣也跟着被拎起。研究发现，当p 大于某个临界值p 。一( i n n ) n 时，你随机捡起地上任何一个钮扣部会拎起其它 几乎所有的钮扣。下面将推导e r 随机图的一些基本性质。 首先研究子图及其连通性。环、树和完全图是三种最简单的子图。k 阶环是 指包含k 条边并且有且只有任意两条相继的边才有公共节点的图。例如，三角形 是一个三阶的环。k 阶钳是指具有k 个节点，k 一1 条边的图，并且其任何子图部 不具有环，显然k 阶树的平均度 l2 2 k ，当k 一* 时，它的平均度趋于2 。 k 阶完全子图是包含k 个节点，k ( k 一1 ) 2 条边的图，即该图中任意两点部有边直 接相连。考虑如下问题：从个孤立节点开始，每次以概率p 连接其中任意两 个节点，那么是否存在临界值p 。( ) ，使得某个时刻所有图都会出现包含k 个节 点，条边的子图。文献【2 6 】研究发现产生t 阶树的相变值为以( ) = c n 。肚。1 ， 产生k 阶环的相变值为以( j v ) ；c ，而产生k 阶完全子图的相变值为 p c ( n 1 一c n 制“”。可以看到，最终集合中的图具有何种结构是和连接概率p 密 切相关的。当p 较小时，网络中的边比较稀疏，因此节点趋向于形成小的簇 ( c l u s t e r ) ，这些簇的大小满足指数分布并且具有有限的一阶矩。随着p 地增加， 这些簇将趋向于聚集在一起形成一个和o ( ) 同阶的最大簇( g i a n t c l u s t e r ) ，而剩 余簇的大小仍然满足指数分布并且具有有限的一阶矩。如果这个最大簇包含的节 点数等于，那么称这个图是连通的( c o n n e c t e d ) 。 下面介绍度( d e g r e e ) 这个节点属性中最简单但又十分重要的概念。节点v 所 连接的边的条数称为v 的度。网络中所有节点的度的平均值称为网络的平均度， 记为( k ) 。网络中节点度的分布用分布函数p ) 来描述，它表示随机选择的节点 i 的度恰好为k 的概率。对于具有个节点、连接概率为p 的e r 随机图来说， 节点k 。的度为七的概率满足二项分布： 尸 - k ) 一c 二一t p ( 1 一p ) ”4 - 1 ( 1 - 1 ) 由上式可以计算出度为k 的节点的期望值为： e ( x 1 ) 一。p ( t - 七) ，气一j l v c 盘一l p o - e ) ”一。1( 1 2 ) 经过简单推导可以得到p ( x l 一，) 近似于泊松分布： 4 上海交通大学博士学位论文 p ( x k = ，) 簧( 1 - 3 ) 其中 由( 1 2 ) 式决定，它不是一个常量。当，较大时，泊松分布衰减得很快，其 标准方差为压。当一m 时，式( 1 1 ) 可以近似为泊松分布： 州玎咩玎“鲁 ( 1 4 ) 还有一些研究结果表明：当p ( ) n 。4 “时，所有e r 随机图都由一些孤立 簇组成，每个孤立簇至多为七十1 阶的树，没有任何节点的度大于k 。而当 p ( n ) ； i n ( n ) + k i n i n ( n ) + c n 时，几乎所有的e r 随机图的节点的最小度部 大于k 。更进一步，对于满足p n l n ( n ) 一m 的p ，几乎所有的e r 随机图的最 大度部和平均度是同阶的。因此，e r 随机图中边的分布是比较均匀的，大多数 节点部具有几乎相同的度，这类网络称为均匀网络( h o m o g e n e o u sn e t w o r k ) 。 平均最短路径也足e r 随饥图的一个重要研究指标。最短路径( g e o d e s i c ) 是 指从起点v 到终点w 所能经过的尽可能少的边的条数，记为d ( v ，w ) 。图中所有节 点对之间的最短路径的最大值称为直径( d i a m e t e r ) 。可以进一步定义网络的平均 路径长度：l 。2 d ，v ) ( + 1 ) ，它反应了图中任意两个节点之间的距离 的平均值，其中表示网络规模。一般来说，e r 随机图具有较小的直径。对于 某个给定的节点，与该节点距离为f 的节点的个数不会少于t k ) - 的概率较大， 对于整个图求平均可以得到直径的粗略估计是它和i n ( n ) i n ( k ，1 同阶，也就是 说图的直径和网络规模成对数函数关系，因此它增长比较缓慢。凡是具有相 同节点数和相同连接概率p 的e r 随机图，其直径都相差无几，它们的值都集中 在i n ( n ) i n ( k ) ) 附近【2 8 】。对于平均最短路径长度，可以推测它也应该满足如 下关系： ，i n ( n ) i n ( k 1 ( i - 5 ) 通过对现实网络的平均最短路径长度进行计算，文献【2 9 l 发现许多实际网络和与 之相同大小的e r 随机图都具有几乎相同的平均最短路径长度，并且它们的值和 式( 1 5 ) 的估计非常符合。 最后介绍聚类系数的概念。在社会网络中，很容易观察到如下现象：即你的 两个朋友很可能彼此也是朋友。这种“物以类聚，人以群分”的特性可以用网络的 5 第一章绪论 聚类系数朱描述。假设节点i 有k ，条边将它和其它节点相连，这七；个铮点称为声 点i 的邻居。定义这k ，个邻居之间实际存在的边数。和最多可能存在的边数 k 。( k ，一1 ) 2 之比为节点i 的聚炎系数：c i 一2 e ，i ( k 。 ；一1 ) ) 。整个图的聚类系数c 就是所有节点i 的聚类系数c 。的平均值，即c ：yc n 。显然，0 s c 墨1 ，c ：0 一 当且仅当网络中不存在任何三角形结构的连接；c = 1 当且仅当该图是完全图。 对于含有个节点的e r 随机图，可以计算出c 。一p 一 | | ，n ，当j 很大时， c ，。= o ( n - 1 ) 。实际的统计数据表明，许多大规模的现实网络都具有明显的聚 类特性，其聚类系数尽管远小于i 但却比o ( n 1 ) 要大的多。比如在社会关系网 络中，你朋友的朋友同时也是你的朋友的概率会随着网络规模的增加而趋于某个 非零常数，即当一* 时，c = d ( 1 ) 。因此实际的复杂网络并非完全随机的，而 是在某种程度上具有类似于社会关系网络中的聚集特性1 1 9 1 。 i i 基本渗流理论 什么是渗流( p e r c o l a t i o n ) 可以如下通俗地解释：一块铁和一块海绵同时放 到水中，海绵的中心很快就被浸湿，而铁块稍微靠近表面的部分也不会有水，显 然这是由两种物体的致密程度决定的。如果将组成它们的元素看作点，点之间的 缝隙看作边的话，那么致密程度就相当于这些边出现的概率p 的大小不同。渗流 理论研究得就是何种概率p 使得物体被浸湿成为可能? 更严格的说就是寻找临 界概率如。的值，一旦p 超过此临界值，渗流将不可避免。在随机图理论的研究 中，人们发现在形成最大连通子图的过程中连接概率p 会有一个相变值，这一过 程和渗流现象有许多相似之处。虽然渗流理论是数学和统计力学较为关注的一个 研究课题 3 0 - 3 2 ，然而它对于解释一些现实网络中的现象依然十分重要，并且这 些现象有时是随机图理论无法解释的。 渗流理论关心的一些指标，比如节点属于某个无限维簇的概率、平均簇大小 t s ，以及节点在大小为s 的簇中具有固定位置的概率等，也是随机图理论所关心 的。由于渗流理论是定义在规则的d 维网格上的，而对于随机图来说，无法将其 嵌入到任何一个有限维的规则网格之内，因此，随机图理论和渗流理论只有在维 6 上海交通大学博士学位论丈 数d m 时才可以精确匹配。事实上，许多研究表明渗流理论的大部分结论部可 以推广到无限维的情形。在随机图理论的研究中，研究对象足具有j l 、r 个节点并 且它们之问的边以概率p 出现的图的集合，这至多足一个维的渗流问题。研 究j v 一* 时随机图所具有的性质也就类似于研究无限维渗流问题。对于一个d 维规则对象，其外围节点数( s u r f a c e ) s 和整个空间上的节点数( v o l u m e ) v 满 足一个粗略的关系：s a v “膳，当维数d 一。时，s ，y 满足近似的线性关系。在 对凯菜讨的研究中发现它的叶子节点个数和节点总数具有线性关系1 3 0 1 ，因此可 以近似的将其看作一个无限维对象的例子。相应的，对于凯莱树的研究结果可以 看作是渗流理论在无限维情形下的结果。由文献 3 0 1 中的结论可以知道凯莱抖产 生渗流的相变值= l l ( z 1 ) ，其中z 是凯莱树的配位数( c o o r d i n a t i o nn u m b e r ) 大小。对于具有个节点的e r 随机图来说，其配位数大小为1 ，因此可以 得到e r 随机图发生渗流的相变值为p 。= 1 n ，这一结论和e r d 6 s 与r 6 n y i 得到 的e r 随机图产生最大簇时的连接概率p 的表达式是一致的。可以说，随机图中 发生的相变是渗流的一种表现形式，文献 3 3 1 中也证实了随机图中发生相变的临 界指数和无限维渗流的相变临界指数是相等的，这种等价性对于复杂网络的研究 是非常重要的。 i i i 两种解析方法 生成函数法( g e n e r a t i o nf u n c t i o n s ) 和主函数法( m a s t e r e q u a t i o n s ) 是研究随 机图理论用得较多的两种解析方法。生成函数法作为联系离散数学和连续分析特 别是复变量理论的一座桥梁，可以巧妙地解决离散数学中的许多问题。2 0 0 1 年， n e w m a n 等人首先将生成函数法引入到随机图理论的研究中1 3 4 。下面简单介绍 生成函数法在随机图理论中的主要结果。给定e r 随机图的度分布p ) ，生成函 数如下定义： g o o ) 。荟p 矿( 1 - 6 ) 其中j 【一1 l 】。对( 1 - 6 ) 式两边求k 阶导数可以得到p ( k ) 的表达式，因此岛o ) 几 乎包含了所有p ( k ) 的信息。同样的，可以推出平均度z 的生成函数表示为： 7 第一章绪论 z = - 罗概一g o ( 1 ) ( 1 7 ) o 。一 随机选取一个节点，可以用如下7 t 成函数束表示该节点的邻居审点的分布： g l o ) ；k p ( k ) x 一；k p ( k ) k = g ：o ) c t ，0 - 8 ) 如果定义生成函数啊o ) 为从任意随饥选择的边所达到的簇的大小的分布，那么 可以得到如下递归表达式： h i o ) = 切( t ) n ( 工) r ，；印 ) ，x g 。n ( 工) 】( 1 - 9 ) 如果考虑从一个随机选取的节点出发所能达到的簇大小，它可以如下表示： h o ( x ) ；z p ) 叭工) ；x g 。附工) 】( 1 - 1 0 ) 当e r 随机图中不存在最大簇的时候，可以求得平均簇的大小为： ( s ) = ( 1 ) = 1 + g o ( 1 ) ( 1 - g l ( 1 ) ) ( 1 ，1 1 ) 如果g i ( 0 1 ，则表明e r 随机图中将会出现最大簇。将式( 1 1 0 ) 代入上式，可以 得到e r 随机图中出现最大簇的判据为： y 七( 七一2 ) p ( k ) = 0 ( 1 - 1 2 ) 一 这和m o l l o y 等人得到的判据是致的【3 5 】。 主函数法的思想是将一些图指标的变化过程和图的演化过程相联系，通过求 解主函数方程得到相应结论。在计算诸如度分布、相关度等指标时，这是一种非 常有效的方法。考虑如下演化模型：初始有个孤立节点，每步加入一个节点y 并在新加入的节点和原来存在的节点之间以一定的概率p 加入m 条边，概率p 如 下选取： p 。厕k v + 1 ( 1 1 3 ) 假设七2 研，并且度为七的节点个数为。当在图中加入一条边时，如果原来度 为t 一1 的节点被连接，那么i 将增加，如果度为k 的节点被连接，那么m 将减 少【3 6 ，3 7 1 。利用式( 1 1 3 ) ，可以得到如下表达式： 姚。一嚣器一坠攀掣 m 为了得到稳态解，假设对所有的七，t ，p ( 七) 一p “1 他) 。经过简单计算可得： 8 上海交通大学博士学位论文 a n k p ) 结合式( 1 - 1 4 ) 、( 1 - t 5 ) 百i 得： m k p 伙- 1 ) 一( 3 m + l + m k ) p 似) 通过将上式近似为连续情形可以得到： x p 一一f 3 + l m ) p 求解上式可以得到：p ( x 1 一a 一”“，其中c 是萨则化常数。 化过程得到的图的度分布为具有指数为一3 1 m 的幂率分布。 1 2 2 经典复杂网络模型 ( 1 1 5 ) ( 1 1 6 ) ( 1 1 7 ) 这个结果表明该演 i w s 小世界网络模型( w a t t s - s t r o g t zs m a l lw o r l dn e t w o r k ) 小世界网络模型反映了现实生活中的一种现象：一个人的朋友大部是他的邻 居或单位的同事，然而也有些是相距较远的人。w a t t s 和s t r o g t z 于1 9 9 8 年提出 了小世界网络模型，称为w s 小世界模型，该模型可以看作是从规则网络向随机 网络的过渡过程 1 9 1 ，其构造算法如下： a 1 仞始网络是一个