（运筹学与控制论专业论文）复杂网络及其交通动力学行为研究.pdf

中文摘要 摘要： 随着计算机的飞速发展，关于复杂网络的研究已经成为当前国内外学术界的一 个研究热点问题。复杂网络的基本理论和研究方法可能为研究现实中各种系统或 者网络的复杂性问题提供一个有利的工具，对人们的工作和生活具有重大意义。 本文结合复杂网络以及交通运输网络的主要特点，运用统计物理、数学以及计算 机模拟等方法，从网络建模、流量分布特性和级联失效三个方面对复杂网络的相 关问题进行了分析和研究。 在建立新模型方面，文中分别给出了一个无向网络的组合模型和一个有向加权 网络的非对称模型。组合模型在网络演化过程中，综合考虑了节点度的吸引，距 离的约束以及老化，模拟结果表明，组合模型能够演化出随机网络和无标度网络； 非对称加权网络模型，通过理论分析和数值模拟研究了网络的一些拓扑特性，能 够重现很多现实网络中的度分布、强度分布和权重分布的幂律特征。 复杂网络上的交通动力学行为很多，本论文侧重流量分布特性和级联失效行 为。基于四种典型的拓扑结构( 即规则网络、随机网络、小世界网络和无标度网 络) ，探讨了用户平衡、系统均衡和系统最优三种不同的交通流分配方式对系统总 阻抗的影响。研究表明，对于交通流量的增加，无标度网络和随机网络结构具有 更好的表现，可以减缓系统总阻抗的增加。另外，模拟结果表明，在系统均衡和 系统最优分配方式下，在无标度网络中的流量分布与用户平衡分配方式下相似， 都具有幂律特性，并且其幂律指数值更大，从一定程度上减少了流量的异质特性。 最后，在四种不同网络结构下，研究了三种不同流量分配策略下的级联失效行为， 为交通运输网络安全的有效控制提供理论基础。 关键词：复杂网络；交通流分配；用户平衡；系统均衡；系统最优；级联失效 分类号：n 9 4 0 ，0 1 5 7 6 a bs t r a c t a b s i r a c t ： a st h er a p i dd e v e l o p m e n to fc o m p u t e r s ，s t u d i e so nc o m p l e xn e t w o r k sb e c o m em o r e a n dm o r ep o p u l a ri na c a d e m i ai nn a t i o na n da b r o a d b a s i ct h e o r i e sa n dr e s e a r c h m e t h o d so f c o m p l e xn e t w o r k sm a yp r o v i d eau s e f u lw a y t os t u d yv a r i o u sr e a ls y s t e m s o rt h ec o m p l e x i t yo ft h en e t w o r k s ，a n db eo fg r e a ts i g n i f i c a n c ei np e o p l e sw o r ka n dl i f e i nt h i s p a p e r , c o m b i n e dc o m p l e xn e t w o r k sw i t hm a i nc h a r a c t e r i s t i c s o ft r a n s p o r t n e t w o r k s ，b yu s i n gs t a t i s t i c a lp h y s i c s ，m a t h e m a t i c sa n dc o m p u t e rs i m u l a t i o nm e t h o d s ， w ei n v e s t i g a t en e t w o r km o d e l i n g ，l o a dd i s t r i b u t i o na n dc a s c a d i n gf a i l u r e sa st h et h r e e a s p e c t sr e l a t e dt on e t w o r ka n a l y s i sa n d r e s e a r c h o nn e t w o r km o d e l i n g ，w ei n t r o d u c eac o m b i n e dm o d e lf o rn o n d i r e c t e dn e t w o r k s a n da na s y m m e t r i c a lm o d e lo fd i r e c t e da n dw e i g h t e dn e t w o r k s t h ec o m b i n e dm o d e l c o n s i d e r st h ea t t r a c t i o no ft h ed e g r e e ，d i s t a n c ec o n s t r a i n t sa n da g i n gt h r o u g ht h e e v o l u t i o no ft h en e t w o r k s s i m u l a t i o nr e s u l t sd e m o n s t r a t et h a tt h ec o m b i n e dm o d e lc a n e v o l v ei n t or a n d o mn e t w o r k sa n ds c a l e f r e en e t w o r k s t h ea s y m m e t r i c a lm o d e ls t u d i e s s o m et o p o l o g yp r o p e r t i e sb yt h e o r e t i c a la n a l y s i sa n dn u m e r i c a ls i m u l a t i o n s ，w h i c h r e c o v e rt h ep o w e rl a wb e h a v i o ro ft h ed i s t r i b u t i o n so ft h ed e g r e e ，s t r e n g t ha n dw e i g h t d i s c o v e r e di nm a n yr e a ln e t w o r k s t h e r ea r ep l e n t yo ft r a f f i cd y n a m i c a lb e h a v i o r so nc o m p l e xn e t w o r k s i nt h i sp a p e r w ef o c u so nt h el o a dd i s t r i b u t i o na n dc a s c a d i n gf a i l u r e s b a s e do nf o u rt y p i c a ln e t w o r k s t r u c t u r e s ( i e ，r e g u l a rn e t w o r k s ， r a n d o mn e t w o r k s ，s m a l l - w o r l dn e t w o r k sa n d s c a l e f r e en e t w o r k s ) ，w ei n v e s t i g a t et h ee f f e c to ft h r e et r a f f i ca s s i g n m e n t s ，i e ，u s e r e q u i l i b r i u m ，s y s t e me q u i l i b r i u ma n ds y s t e mo p t i m i z a t i o n ，o nt h es y s t e mt o t a lc o s t i t i n d i c a t e st h a t ，w i t ht h ei n c r e a s eo ft h et r a f f i cv o l u m e ，s c a l e f r e en e t w o r k sa n dr a n d o m n e t w o r k sh a v eab e t t e rp e r f o r m a n c et or e l i e v et h ei n c r e a s eo ft h es y s t e mt o t a lc o s t i n a d d i t i o n ，s i m u l a t i o nr e s u l t sa l s os h o wt h a t ，u n d e rt h et r a f f i ca s s i g n m e n t so fs y s t e m e q u i l i b r i u ma n ds y s t e mo p t i m i z a t i o n ，l o a dd i s t r i b u t i o n se x h i b i tap o w e r - l a wb e h a v i o ri n s c a l e - f r e en e t w o r k s ，w h i c hi ss i m i l a rt ot h a tu n d e rt h et r a f f i ca s s i g n m e n to fu s e r e q u i l i b r i u m b u tt h ee x p o n e n t sa r em u c hl a r g e rt h a nt h a tu n d e rt h et r a f f i ca s s i g n m e n to f u s e re q u i l i b r i u m ；a sar e s u l t ，t h eh e t e r o g e n e i t yo ft h el o a dd i s t r i b u t i o nc a nb ed e c r e a s e d u n d e rt h et r a f f i ca s s i g n m e n t so fs y s t e me q u i l i b r i u ma n ds y s t e mo p t i m i z a t i o n f i n a l l y , b y c o n s i d e r i n gt h r e ed i f f e r e n tt r a f f i ca s s i g n m e n t s ，w es t u d yc a s c a d i n gf a i l u r e sw i t h i nf o u r v a r i o u sn e t w o r ks t r u c t u r e s ，w h i c hc a nt h e o r e t i c a l l ys u p p o r tt h ee f f e c t i v es t r a t e g i e st o c o n t r o lt h es a f eo ft h et r a f f i ca n d t r a n s p o r t a t i o nn e t w o r k s k e y w o r d s ：c o m p l e xn e t w o r k ；t r a f f i ca s s i g n m e n t ；u s e re q u i l i b r i u m ；s y s t e m e q u i l i b r i u m ；s y s t e mo p t i m i z a t i o n ；c a s c a d i n gf a i l u r e c l a s s n 0 ：n 9 4 0 ，o l5 7 6 v 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：乏莶，凡 导师签名 签字同期：工洳圹年月土日 签字日期：年月 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：乏多，慨签字同期：加夕年厂月日 5 5 致谢 三年来，导师高自友教授在我的科研和论文写作中都给予了精心的指导。高 自友教授渊博的学问和独特创新思路为我打开了科学的大门，我在学习、科研中 取得的进步和成果都离不开导师的悉心指导。同时，导师治学严谨、对事业执著 追求的精神以及在基础理论方面的精深研究和造诣使我受益终生，无论现在还是 未来，导师都是我追求的典范、学习的榜样。在此，谨向敬爱的导师高自友教授 表示最衷心的感谢! 高自友老师、赵小梅老师、孙会君老师、徐猛老师等对于我 的科研工作都提出了许多的宝贵意见，在此表示衷心的感谢。 感谢郑建风博士、赵晖博士、吴建军博士、张好智博士对我硕士期间科研工 作的大力支持和帮助，正是他们热情、无私的帮助才使我的论文工作得以充实和 完善，最终能够顺利完成。 感谢8 6 11 和思源实验室的其他师兄弟姐妹们，和大家在一起的生活给我留下 了美好的回忆。 最后，感谢我的父母，亲人和朋友，他们是我永远的依靠和支持! 1 绪论 本章主要分为四部分。首先介绍与社会生活息息相关的交通现象和交通网络。 复杂网络作为研究交通网络的方法和工具，可以用来对城市交通展开深入的理论 和应用研究，于是我们对复杂网络的概念和基本特征量作以介绍。随后，简要阐 述国内外研究现状。由此，确定了本文的总体框架和主要内容。 1 1 交通运输网络 1 1 1 交通运输系统 交通运输系统是社会经济发展的基础。现实世界存在的许多广义运输系统， 其上的抽象运输过程可以包括货币、信息、车辆、数据、能量、甚至权利的流动， 它们广泛存在于城市系统、计算机系统、互联网、经济系统等复杂系统中。如果 将交通网络抽象出来，就会发现它与人和动物体内的血管组织、自然界中的河流 网络以及植物的根、茎、叶的运输系统非常相似，而所有这些运输系统中的演化。 及动力学行为也遵循着某些类似的规律【l 】。 本世纪初，复杂网络理论迅速成为许多科技领域的研究热点。物理学、计算 机科学、生命科学、交通科学，甚至社会科学等领域的专家学者都在对该领域进 行着深入的研究【2 】。同时，复杂网络理论的发展为研究大规模运输网络提供了有力 的工具，使人们可以更加深入的了解和认识大型运输网络的拓扑结构及其上的各 种动力学行为。如何融合交通运输网络的特点，深入地研究运输网络的时空分布 复杂性及其流量演化机制，揭示阻塞产生的机理，从而进一步提出控制拥堵有效 方案，将有助于解决城市交通拥堵和交通安全等相关科学问题。 随着计算机处理能力的不断提高和计算机网络的普及，学科之间的相互交叉 和融合趋势不断加强，促使人们开始了解大规模网络的结构复杂性和动力学行为 复杂性【2 3 巧】。而所研究网络规模的迅速增大也迫使人们改变研究的方法。对以前 所研究的小规模网络，用实际的线和点就能相对直观的画出其网络结构图，通过 观察就可以分析或解决有关网络的特定问题。然而，对于拥有上百万个甚至上亿 个节点的复杂网络来说，直观观察方法几乎不起任何作用。而且仅凭一人之力也 不可能准确描绘出包含上百万个节点的网络结构图。实际上，随着对复杂网络研 究的逐步深入，人们提出了许多新的概念和方法。其中，统计力学的引入为复杂 网络理论提供了一个有力工具，而复杂网络理论的研究也为统计力学带来了新的 研究内容。 研究运输网络的主要目的之一是理解拓扑结构及其对复杂系统中各种动力学 行为的影响。这不仅要认识系统中的个体或组成部分的行为，更重要的是要探索 它们共同作用下的整体行为。二元网络将所有的边都被认为是完全相同的，没有 考虑不同节点间的耦合强度，即边的权值。事实上，许多网络节点间的耦合的强 度是不同的，例如社会关系网【6 】中，边权代表两个人的熟悉程度；演员合作网中， 边权代表演员间合作的紧密程度；电力网中，高压传输站点间的边权代表其距离 的远近；i n t e r n e t 网 j 中，路由之间的边权代表网络的带宽等等。加权网络能够更 准确的描述实际复杂系统。而最近的研究也发现了加权网络所独有的复杂特性， 如无标度强度分布、强度度的非平凡相关等。当前对加权网络的研究和应用尚不 多见，对于加权网络的研究还处于初步探索的阶段，而其中关于交通运输网络方 面的研究就更少，因而关于加权运输网络方面的研究具有一定的理论价值。 研究预防运输网络遭到协同攻击和破坏，对防治交通阻塞、提高网络可靠性 等方面均具有重要的理论和现实意义。在运输网络中，一个或少数几个节点过载 发生故障，会通过节点之间的耦合关系引起其他节点过载，进而产生连锁效应， 最终导致网络上的大规模故障。例如，在i n t e n - n e t 网络【_ 7 】中，对少数路由器进行攻 击会导致大量的路由过载，发生网络大规模故障。在电力网络中，少数几个断路 器、输电线路或者电站发电单元故障都会导致大范围的停电事故。在交通运输网 络中，一个交通枢纽的拥堵，一个交通突发事件都会对整个交通网络产生非常大 的影响。研究表明，具有无标度特性的复杂网络对意外故障具有惊人的强韧性， 而如果对网络进行蓄意攻击和破坏，就会迅速导致整个网络瘫痪。目前国内外对 运输网络可靠性具有一些研究成果，但还没有形成完善的理论体系。实际上，对 运输网络的研究不应仅局限于对其拓扑结构的研究，更重要的应用理论研究的成 果对现实网络进行有效的控制。因此，将一般运输网络的级联失效理论应用到交 通运输网络中具有重要的现实意义和应用价值。 2 国外已经有很多学者对网络复杂性进行了大量的研究，并从实证的角度进行 了相关分析。但是就与交通密切相关的运输网络而言，相关研究成果还比少。对 于一般运输网络拓扑结构以及动力学行为的定量和定性研究是一项富有挑战性的 科研课题，必将对交通运输网络的研究产生重要的现实意义和应用价值。要运用 一般运输网络来解决交通问题，必须要深入分析运输网络上的交通动力学性质。 结合交通运输网络的特殊性质，研究运输网络上的交通流状态、分布以及演化， 能够应用复杂网络的理论对现实交通网络进行网络规划指导、设计、建设及管理。 近年来，我国的交通运输业保持着较高的发展速度。随着经济的发展和城市 化进程的加快，城市机动车拥有量急剧增加，交通供需矛盾同益突出，交通拥挤 越来越严重。与此同时，随着城市规模的不断扩大，人、车、路的数量不断增加， 交通运输系统也会变得越来越复杂。作为承载人类活动的基本构件之一，交通运 输网络是国家繁荣的主要支撑条件，直接关系着经济发展、安全保障、环境保护 等各个方面。从一般运输网络的角度，利用系统科学的原理与方法，以系统分析 与集成为手段，并综合利用复杂网络理论，通过对交通运输系统目标的分解、协 调、综合和优化，实现复杂系统的建模与分析，探索交通运输网络的演化机制和 动力学行为，解释阻塞产生的根本原因，对科学规划交通系统，缓解和预防大规 模交通拥堵都具有重大的理论与实际意义。 1 1 2 城市交通网络的描述 作为交通系统的一个特例，城市交通系统与人们的日常生活密切相关，因而 具有非常重要的作用。城市交通系统本身是由道路系统、流量系统和管理系统组 成的一个典型的、开放的、复杂巨系统。城市交通网络由交叉路口和连接他们的 街道组成，车辆在网络中行驶。其中，交叉路口或小区对应于节点( n o d e s ) ，街道 或道路对应于边( 1 i n k s ) ，车辆在边上行驶遇到的阻抗( c o s t ) 对应于边上的权重， 其值通常可以用所花费的行驶时间来描述。这样，城市交通网络就可以抽象成为 一个复杂网络( c o m p l e xn e t w o r k s ) 【8 】。 目前，将城市交通网络抽象成为复杂网络，并进一步利用网络理论深入研究 城市交通的各种特性，已经得到广泛关注。当然，如何将城市交通网络映射为复 杂网络的方法不是单一的，如将道路映射为网络中的节点，将道路间的交叉口映 3 射为节点间的连边，被称为d u a la p p r o a c h 9 1 。本文的抽象方法如上节所述，将交叉 路1 ：1 映射为网络中的节点，将道路映射为节点间的连边，此被称为p r i m a l a p p r o a c h 1 0 1 。 1 2 复杂网络 1 2 1 源起 要研究网络结构复杂性及其与网络行为之间的关系，首先需要有一种描述网 络的统一工具。这种工具在数学上称之为图( g r a p h ) 。任何一个网络都可以看作是 由一些节点按某种方式连接在一起而构成的一个系统。具体网络的抽象图表示， 就是用抽象的点表示具体网络中的节点，并用节点之间的连线来表示具体网络中 节点之间的关系。实际网络的图表示可以追溯到1 8 世纪伟大的数学家欧拉( e f i l e r ) 于1 7 3 5 年对著名“k o n i g s b e r g 七桥问题”的研究。欧拉对七桥问题的抽象和论证 思想，开创了数学中的一个分支图论( g r a p ht h e o r y ) 的研究。今天人们关于 复杂网络的研究与欧拉当年关于七桥问题的研究在某种程度上是一脉相承的，即 网络结构与网络性质密切相关。 2 0 世纪6 0 年代，有两位匈牙利数学家e r d 6 s 和r 6 n y i 建立的随机图理论 ( r a n d o mg r a p ht h e o r y ) 【2 0 】被公认为是在数学上开创了复杂网络理论的系统性研 究。在此之后的四十年中，随机图理论一直是研究复杂网络的基本理论，然而绝 大多数实际网络结构并不是完全随机的。例如，两个人是否是朋友，i n t e m e t 中两 个路由器之间是否有光纤连接，w w w 上两个页面之间是否有超文本链接等都不会 是完全随机决定的。在2 0 世纪木，复杂网络研究不再局限于数学领域。人们开始 考虑节点数量众多、连接结构复杂的实际网络的整体特性。有两篇文章可以被认 为是复杂网络研究新纪元开始的标志：一篇是w a t t s 和s t r o g a t z 于1 9 9 8 年6 月发 表在n a t u r e 上的“小世界网络的集体动力学【2 u ；另一篇是b a r a b a s i 和a l b e r t 于1 9 9 9 年1 0 月发表在s c i e n c e 上的随机网络中标度的涌现1 3 】。这两篇文章分 别揭示了复杂网络的小世界效应和无标度特性，并建立了相应的模型以阐述这些 特性的产生机理。 随着计算机的飞速发展，关于复杂网络的研究成为了当前国内外学术界的一 4 个研究热点问题。复杂网络的研究基于统计物理、应用数学、混沌以及控制等多 门基础学科，具有很强的交叉性。复杂网络的基本理论和研究方法可能为研究现 实中各种系统或者网络的复杂性问题提供一个有利的工具。同时，在科学层面上 研究复杂网络，对人们的工作和生活具有重大意义。如何避免通讯网络上的信息 拥塞，如何有效避免和控制人群中的疾病传播，如何准确高效地在互联网上搜索 到需要的信息，如何抑制大范围内的金融危机，以及如何缓解与控制城市交通网 络上的交通拥挤等等，所有这些问题都与复杂网络科学息息相关【3 ，4 1 1 。3 1 。 1 2 2 基本概念和统计特征量 简单而言，网络是由节点以及连接这些节点的边所构成，以图论为形式开展 的网络研究一直是离散数学的基本组成部分之一。人们对图论的研究源于1 7 3 5 年 大数学家欧拉( e f i l e r ) 所提出的著名的歌尼斯堡( k o n i g s b e r g ) 七桥问题，随着对 图论研究的不断深入，到了二十世纪，网络理论逐渐发展成为一个重要的研究领 域。复杂网络( c o m p l e xn e t w o r k s ) 即是用网络模型的方法描述复杂系统，从而进 行分析和研究。 为了本文的完整性和可读性，这里给出一些相关的基本概念： ( 1 ) 节点：网络的基本单元，也称为顶点。 ( 2 ) 边：连接两个节点的线或者关系。 ( 3 ) 有向( 无向) ：如果网络中的一条边仅有一个方向可通行，则称为有向边， 如果一条边的两个方向都可通行，则称为无向边。有向边也称为弧。如果一个网 络中所有的边均为有向边，则称这个网络为有向网络，否则称为无向网络。无向 网络也可视为有向网络，只要把图中相关联的所有边都看作有向网络中两条方向 相反的边即可。 ( 4 ) 度：与一个节点相关联的边的条数。在没有重边的网络中，它等同于与 此节点相邻接节点的个数。在有向网络中，每个节点都有一个出度和一个入度， 它们分别指与这个节点相连的出边和入边的条数。 ( 5 ) 平均度：平均度是指网络所有节点度的平均。由于增加一条边，整个网 络的度就增加，那么网络的平均度： 5 ( 七) = 专；砖= 等 ) 其中m 和分别表示网络的边数和点数。 ( 6 ) 连通：从一个节点出发沿着网络中的边所达到全部节点的集合，称为这 个网络的一个连通区域。对一个网络而言，如果从一个节点出发沿网络中的边能 够到达网络中的任何节点，则称这个网络为连通的。 ( 7 ) 最短路：对于二元网络，从一个节点到另一个节点的最短路是指这两个 节点之间所经过边数最少的路径。而对于加权网络，最短路则是指从一个节点到 另一个节点所经过边的权重之和最小的路径。两个节点之间的最短路通常不止一 条。 ( 8 ) 直径：网络的直径是指任意两个节点之间最短路径的最长长度( 在二元 网络中，长度指所包含边的条数) 同样给出一些相关的统计特征量： ( 1 ) ( 节点) 度分布：网络中节点的度分布一般用度分布函数p ( k ) 来衡量， 它指对一个随机选定的节点，它的度恰好为k 的概率。有向网络的度分布又可分为 出度分布和入度分布。另一种描述度统计特性的方法是采用累计度分布函数，即 统计节点度大于或等于k 的概率， 最= p ( 后i ) ( 1 2 ) 如果网络的度分布呈现出幂律特征p ( k ) k ，其中见为幂指数，则称此网络 为无标度网络。 ( 2 ) 平均最短距离( 特征距离) ：对一个无向网络，定义平均最短距离，是网 络中节点对之间最短距离的算术平均： ，：士主力 ( 1 3 ) 去以( ，l + 1 ) 企7 其中，如是从节点f 到节点，的最短距离。此平均数中包含了从每个节点到其自身 的距离( 为0 ) 。 另一个可供选择的定义方式是所有节点对之间最短距离的调和平均： 6 厂1 = 产靠1 ( 1 4 ) 去，l ( 以+ 1 ) 经7 如果网络平均节点度固定，珀勺值随网络大小以对数的速度或慢于对数的速度 增长，那么称此网络具有小世界效应。 ( 3 ) 簇系数：簇系数是用来衡量网络聚类特性的统计量。假设网络中的某个 节点f 有勺个节点和它相连，这磅个节点就称为节点i 的邻居。显然，在这岛个节 点之间最多可能有岛( 岛- 1 ) 2 条边。这砖个节点之间实际存在的边数量和总的可能 边数向( 勺- 1 ) 2 之比定义为节点i 的簇系数q ，即g = 2 e j ( 毛( 砖- 1 ) ) 。 从集合特征上看，上式的定义等价为： 包含结点韵三角形的个数， 1 = 一 i1j 、 以顶点f 为中心的三点组的个数 “。7 对于度为0 或1 的节点，由于分子和分母均为0 ，则认为e = 0 。整个网络的 簇系数就是所有节点确垂系数e 的平均值： 仁 - z 二c , n ( 1 6 ) f 显然，0 c 1 。c = 1 当且仅当网络是一个全局耦合网络，也即全连通网络。 ( 4 ) 相配性系数：相配性描述的是节点度的相关性，它可以通过邻居节点平 均度来衡量，即 k ，= 薛1 ，乃 ( 1 7 ) 考察所有给定度k 的邻居节点平均度能够度量整个网络的相配性， k ( 七) = 上n p ( k ) ，荟。k n n , t 善后p ( 川后) 。 1 剐 如果邻居节点度不相关，p ( k ik ) 仅为k 的函数，则k ( 后) 退化为一常数。 网络可就其相配性特征分为两大类。一类是同配网络，即k ( 后) 随度k 的增加 而增加；另一类是异配网络，即k ( 尼) 随度k 的增加而减小。几乎所有的社会网络 是同配网络，而几乎所有技术网络、通讯网络、生物网络都是异配的。虽然为什 么会出现这种明显的分类还是未知的，相配性却给人们提供了一个区分社会网络 和技术网络、生物网络的区分方法。 7 ，： 竺：圣! 苎竺二! 竺：圣! 圭! 乏：竺! ! ： ( 。9 ) m 叫一1 ，2 + 砰) 一【m 一，寺( z + 岛) 】2 其中五，毛为第i 条边两端节点的度，i = l ，m ( 其中m 为网络总的边数) 。简单 如) _ ，毛，警s t ( 1 1 0 ) j f s v一 其中为从节点s 到f 之间路径的条数，( 1 ，) 是从节点j 至l j t 2 _ f n f f h 径中通过节点 咖) _ ，三，警s t ( 1 5 f j v一 其中为从节点s 到f 之间路径的条数，似) 是从节点j 到f 之间路径中通过边u 1 3 国内外研究现状 现实世界中许许多多的复杂系统都可以用网络来描述。从技术世界的i n t e r n e t 网、w w w 网、通讯网络到社会科学中的组织网络、商务关系网络、科技引文网 络、科学家合作网络，乃至生物世界的神经网络、新陈代谢网络、食物链网络、 交通运输网络，具有网络形式的复杂系统处处可见【3 。13 1 。复杂网络的分析方法也已 经广泛应用于各个领域，用来描述系统中个体之间的关系以及系统的集体行为。 上世纪5 0 年代末6 0 年代初，匈牙利数学家e r d 6 s 和r 6 i l 弧在网络科学领域取 得了重要的突破，他们在论文里提出了一个典型的随机图模型【2 0 1 。在2 0 世纪的后 4 0 年中，随机网络理论一直是研究复杂网络的基本理论。2 0 世纪即将结束之际， 复杂网络理论的研究发生了重要的转变。这个时期，网络理论的研究不再仅仅局 限于数学界，大量来自物理界、工程学界乃至生物学界、社会学界的优秀学者投 入到了网络科学的研究中来。 近年来，随着计算机的快速发展，计算能力迅速增强，人们开始考虑具有上 万个，乃至上百万个节点的超大型网络。在自然科学的各个领域，计算机化的数 据采集产生了各种能够显示复杂网络拓扑结构的大型数据库。同时，迅速增强的 计算能力也为研究大型复杂网络提供了相应的技术支持。而科学界限的突破也使 研究人员更加便利地使用各种数据库，这使得他们能够作为一个整体去尝试了解 复杂网络的一般特性。 所研究网络规模的迅速增大迫使人们必须改变研究方法。对以前所研究的小 规模网络，用实际的线和点就能相对直观的画出其网络结构图，通过观察就可以 分析或解决有关网络的特定问题。然而，对于拥有上百万个甚至上亿个节点的复 杂网络来说，直观观察方法几乎不起任何作用。而且仅凭一人之力也不可能准确 描绘出包含上百万个节点的网络结构图。事实上，随着对复杂网络研究的逐步深 入，人们提出了许多新的概念和方法。其中，统计物理的引入为复杂网络理论提 供了一个有力工具，而复杂网络理论的研究也为统计物理学带来了新的研究内容。 1 3 1 复杂网络建模 自从w s 小世界网络模型和b a 无标度网络模型【3 】提出以来，复杂网络的建 模工作开始被国内外学者所关注。a l b e r t 和b a r a b f i s i t 。7 】通过引入局域事件，提出 a b 模型，发现从无标度网络到随机网络的相变区域。b i a n c o n i 和b a r a b 缸i 【l5 j 提出 了适应度模型，解释了一种所谓的“赢者通吃( w i n n e rt a k e sa 1 1 ) 的现象，类似于 市场中的寡头垄断。其他很多学者也都对无权网络的建模进行了研究【3 7 枷】。 2 0 0 0 年，k r a p i v s k y 等人【1 4 】就非线性偏好依附机制对网络动态特性和拓扑结构 的影响做了研究。解析和模拟结果都表明了非线性偏好依附直接破坏了网络的无 标度特性，而当偏好依附的选择概率与节点度的关系是近似线性时，网络会自组 织的演化成为无标度网络，且其幂律指数可在2 到0 0 之间任意可调。同年， d o r o g o v t s e v 等人【l5 1 考虑了节点初始吸引度对网络无标度特性的影响，并给出了这 一类网络增长模型度分布的精确解。研究表明节点的初始吸引度只会对幂指数的 9 大小有所影响，而并不改变网络度分布的幂律特征。2 0 0 1 年，d o r o g o v t s e v 和 m e n d e s 【1 6 】研究了网络加速增长对度分布的影响；并提出的一个等价模型，能够重 现度分布的分段幂律特征。另外，在实际系统的演化过程中，许许多多局部作用， 如加边、重连、删点、删边等，都会对整个网络产生影响。2 0 0 0 年，a l b e r t 和b a r a b f i s i 【l 7 】 对局部事件对网络演化的影响进行了研究。 在无权网络中，邻接矩阵( a d j a c e n c ym a t r i x ) a 的矩阵元素非0 即1 ，仅表示 节点之间的边存在或不存在两种情况。显然，无权网络给出了节点之间的相互作 用存在与否的定性描述，这种定性描述反映了相互作用最主要的信息。 在一些情况下，节点之间的相互作用或关系的强度差异起着至关重要的作用。 例如，食物链网络中捕食关系及其强度的多样性【1 8 1 ；新陈代谢反应速率之间的差 别是维持生态系统和新陈代谢网络稳定的重要因素【l9 】；在社会系统中，相互作用 强度对网络上的疾病传播等过程会产生重要影响【6 】；i n t e m e t 网络上的带宽【7 】，科学 家合作网络中的合作次数【2 2 】等都是影响系统性质的重要因素。此时，引入边的权 重( 1 i n kw e i g h t ) 来刻画相互作用强度的差异性，能够更准确地反映实际网络的细 致结构及其功能，从而形成加权网络。 近几年来加权网络的研究工作发展迅速。2 0 0 6 年，b o c c a l e t t i 等在p h y s i c s r e p o r t s 上发表了最新的关于复杂网络研究的综述文章，在该文的引言中曾经提到， 对加权网络研究的进展是他们编写新的综述文章的动因之一【2 3 】。目前对加权网络 的研究工作进展主要集中在网络静态统计性质、网络物理模型和网络演化模型等 几个方面。关于加权网络静态统计性质的研究，主要关注引入权重以后网络几何 量的定义和实证分析等方面的工作。已有研究结果表明，在许多实际加权网络中， 除了幂律度分布、平均最短距离小、聚类系数高等这些无权网络所具有的基本特 点外，点权( 或称点的强度) 和边权也遵循幂律分布；关于加权网络物理模型方 面，把某些物理模型放到加权网络中，如疾病传播、非线性振子和混沌的同步与 共振等，可以探讨相关物理过程在加权网络上的行为；关于加权网络演化模型方 面，则是利用简单和自然的演化规则，产生与实证分析中得到的典型统计性质相 符的加权网络。加权网络研究的核心问题是：理解网络拓扑、物理过程和权重分 布三者之间的匹配关系对网络功能的影响。先是网络的结构与功能往往是通过网 络的拓扑结构、物理过程和权重的相互作用而涌现出来的，通过研究加权网络可 1 0 以加深对实际网络的理解，同时对优化网络的功能具有一定的指导意义。 2 0 0 4 年，b a h a t 等人【2 4 j 对科学家合作网络和世界航空网络做了加权描述，并 进行了较为细致的分析。同年，b a r r a t ，b a r t h 6 1 e m y 和v e s p i g n a n i 提出了一个加权 网络的演化模型，简称b b v 模型【2 5 1 。该网络模型能够再现实际网络中强度、度和 权重的幂律分布。2 0 0 5 年，w a n g 等人【2 6 】提出了一个考虑网络上的交通动力学特性 的加权网络演化模型。该模型不仅能反映强度、度和权重的幂律分布，还能够模 拟出强度度的非线性相关关系，高聚类性和异配特性等。随后，w a n g 等又进一步 推广了他们自己的工作，构建了若干更加符合实际的加权网络模型【27 1 。由于很多 实际网络，例如，i n t e r n e t 上网页之间的链接具有方向性【4 u ；食物链网络中捕食关 系【1 8 1 等等。研究有向加权网络也具有一定的实际意义，也得到学者们越来越多的 关注 2 5 - 2 9 1 。 1 3 2 网络交通流 网络交通流从道路交通流发展而来，围绕交通流分配展开的研究，几十年来 一直是网络交通流研究的基本模式。所谓交通流分配就是将已经预测出来的o d ( o r i g i n d e s t i n a t i o n ) 需求按照人们选择路径的规则分配到网络中的各条道路上， 并求出各条道路的交通流量。由于实际路网的复杂性，通常有很多o d 对，且每 个o d 对之间的可行路径数较大、路径之间存在重叠路段等，以及一些人为判断 路径成本的能力、标准不一致，导致交通流分配( t r a f f i ca s s i g n m e n t ) 一直是一项 难度很大的工作。从1 9 5 2 年w a r d r o p 提出道路网平衡配流的概念和定义【3 0 】之后， 如何求解w a r d r o p 均衡配流便成为了重要课题。1 9 5 6 年，b e c k m a n n 等人【3 l 】提出了 静态均衡交通配流的一种数学规划模型；2 0 年之后，l e b l a n c 等人【3 2 】将非线性规 划中的f r a n k w o l f e 算法成功应用于求解b e c k m a n n 模型，从而形成了现在的实用 解法。以上三点突破是交通配流问题研究领域的重大进步，也是当前交通配流问 题研究的基础。 静态交通配流的文献还可以参考s h e f f i 的( ( u n b a nt r a n s p o r t a t i o nn e t w o r k s ： e q u i l i b r i u ma n a l y s i sw i t hm a t h e m a t i c a lp r o g r a m m i n gm e t h o d s ) ) ( 19 8 5 ) 3 3 】、黄海军的 城市交通网络平衡分析理论与实践( 1 9 9 4 ) 3 4 】，以及高自友等人的城市交通 连续平衡网络设计理论与方法( 2 0 0 0 ) 3 5 】。 静态交通配流模型大多是以这样的假定为前提条件，即o d 间的交通需求量 都是稳定不变的，交通流分布形态固定，路段上分配的交通量也是不变的，这种 模型主要针对长期稳态的交通系统，一般只能用于远期交通计划。实际交通网络 中的交通需求恰恰具有随时间变化的性质，动态交通配流模型则考虑时变的o d 需求、时变的交通条件下的交通行为。j o k s i m o v i c 和b l i e m e r 提出了动态交通配流 的经典框架【3 6 1 。 动态交通配流考虑了交通需求随时间变化的特性，适合自由流、拥挤流两个 方面，在给定交通网络、路段阻抗函数以及随时问变化的o d 需求基础上，获取 路网上随时间变化的交通流形态以及走行时间、费用，因而可以更广泛、更确切 地再现包括交通拥挤在内的广泛的交通现象。因此，静态交通配流是以交通网规 划为目标开发出来的需求预测法，而动态交通配流模型是以道路网交通流为对象， 以交通控制管理为目标开发出来的需求预测法。 1 3 。3 级联失效 在很多实际网络中，一个或少数几个节点或边发生故障，无论是随机发生的 还是由蓄意攻击造成的，这种故障会通过节点之间的耦合关系引起其他节点发生 故障，于是就产生了连锁效应，最终导致相当一部分节点甚至整个网络的崩溃。 这种现象称为级联失效( c a s c a d i n gf a i l u r e s ) p j 。 级联失效概念对于通讯网络或交通网络并不陌生，这种现象在现实社会中广 泛存在【3 1 。例如在i n t e m e t 中，对少数路由器进行病毒攻击会导致路由器过载，迫 使数据包重新路由，从而引起其他路由器相继过载，产生级联失效。在电力网络 中，输电线路故障和电站发电单元故障常常导致大范围停电事故。在社会与经济 网络中也有类似级联失效现象，2 0 世纪9 0 年代木爆发的亚洲金融危机就是一个典 型的例子。类似地，在城市交通网络也会发生级联失效的现象。借助于病毒传播 的s i r 传播模型，w u 等人提出了一种交通拥挤的演化模型。z h a o 等人【5 0 】还研 究了在复杂网络中阻塞产生的相变行为，找到了在规则网络和c a y l e y 树上交通拥 挤产生的临界值。由于交通运输网络中节点或边的容量限制等等，处于网络中的 流体会产生拥挤现象。在此之前，有学者研究了二元网络中由于网络结点或者边 的容量限制而导致的网络崩溃的级联失效模型【5 1 , 5 2 1 。 1 2 1 4 论文主要内容 本文结合复杂网络以及交通运输网络的主要特点，运用统计物理、数学以及 计算机模拟等方法，对复杂网络及其上的交通动力学进行了若干研究。研究不同 的网络拓扑结构和不同的网络配流模型对流量分布特性的影响、分析不同流量分 配策略下的级联失效的发生机理和演化过程，确定提高网络运输能力及安全可靠 性的方法与策略，为网络交通流的有效控制提供理论基础。 特别地，无标度网络具有真实网络中最常见的两个特征：增长性和偏好依附 性。而在实际网络中，还会有许