（交通运输规划与管理专业论文）一般输运网络演化模型及动力学特征的相关研究.pdf

中文摘要 中文摘要 摘要：网络的结构复杂性、演化机制及动力学行为是一般输运网络研究的基 础性科学问题，对认识大规模交通运输网络具有重要意义。本文从统计物理的观 点，运用理论解析及数值模拟等手段，对一般输运网络的演化模型及动力学特征 进行了若干探讨和研究。 首先，本文对一般输运网络的加权模型做了一系列的相关研究。根据一般输 运网络度、强度、权重分布、强度度相关性、聚类特性以及相配性等相关统计特 征，并结合考虑网络演化的某些特殊规律，提出了若干加权网络模型。这些模型 通过引入不同演化机制，不仅可以再现实际输运网络中的多种统计规律，还能够 再现小变量饱和、指数甩尾等较为细致的网络统计特征。 在复杂网络科学的研究初期，人们主要关注的是小世界效应、无标度现象、 层次性、模块性等网络拓扑结构特征。随着研究的不断深入，人们开始注意到网 络的隐含特性和框架结构。本文通过对若干实际网络和模型网络中不同重要程度 h u b 结点统计规律的研究，从节点重要度的角度研究了输运网络的主要框架。 传播动力学是网络科学中的一类重要的研究分支。本文通过考虑一般输运网 络的模块性和小世界特性，分析了模块结构对传播动力学的影响。研究表明网络 的模块结构对拥堵传播的传播速度、范围以及传播中出现的同步现象都有较为明 显的作用，这在一定程度上揭示了网络模块结构和传播之间的某些内在规律。 级联失效在大规模输运网络上时有发生，且对整个系统的破坏性巨大。如何应 对级联失效所引起的大规模故障一直是网络科学的重要课题之一。本文通过对级 联失效产生机制较为深入的分析，并结合无标度网络的拓扑特征，提出了利用导 航策略来控制级联失效的方法。研究表明，采用合适的导航策略能够有效提高网 络稳健性，避免级联失效的发生。 此外，本文通过考虑交通平衡状态下不同拓扑结构输运网络上的流量分配状 态，研究了规则网络、随机网络、小世界网络以及无标度网络上流量分布的规律 性。认识这些一般输运网络上的流量分布规律，对理解现实世界中的各种交通现 象有重要理论价值和实际意义。 关键词：输运网络；交通平衡；h u b 点；权重网络；模块；传播；导航；级联失 效。 分类号：u 4 9 1 2 a b s t r a c t a b s t r a c t a b s t r a c t ：t oc h a r a c t e r i z et h es t r u c t l l r ec o m p l e x i t y , e v o l u t i o n a r ym e c h a n i s m s a n dd y n a m i cb e h a v i o r so fn e t w o r ki st h ek e yi nr e s e a r c h i n gt r a n s p o r t a t i o nn e t w o r k i n t h i sp a p e r , b yu s i n gt h et h e o r e t i c a la n a l y s i sa n dn l l i i l e f i c a ls i m u l a t i o n s , w es t u d i e dt h e e v o l u t i o na n dd y n a m i c a lb e h a v i o r so ng e n e r a lt r a n s p o r t a t i o nn e t w o r k si nt h es t a t i s t i c a l m e c h a n i c sp o 缸o f v i e w f i r s t l y , w em a d eas e r i e sr e s e a r c h e s o nt h ew e i g h t e dm o d e l so fg e n e r a l t r a n s p o r t a t i o nn e t w o r k s b yc o n s i d e r i n gt h es t a t i s t i c a lp r o p e r t i e so ft r a n s p o r t a t i o n n e t w o r k s , s u c ha sd e g r e ed i s t r i b u t i o n , s 心e n g t hd i s t r i b u t i o n , w e i g h td i s t r i b u t i o n , c o r r e l a t i o no fs t r e n g t ha n dd e g r e e ，c l u s t e r i n gc o e f f i c i e n ta n da s s o r t a t i v i t y , a n ds oo n , w ee v o l v e d $ o m ew e i g h t e dn e t w o r k sm o d e l s t h ed i f f e r e n te v o l u t i o np r o c e s s e sc a n g i v ev a r i o u ss t a t i s t i c a lf e a t u r e so fr e a lt r a n s p o r t a t i o ns y s t e m ss u c c e s s f u l l y e s p e c i a l l y , t h em o d e l sc a nr e p r o d u c ef e a t u r e ss u c ha ss a t u r a t i o nf o rs m a l lv a r i a b l e s ，e x p o n e n t i a l d e c a y , e t c a tt h eb e g i n n i n go f t h er e s e a r c ho nt h ec o m p l e xn e t w o r ks c i e n c e ，p e o p l ef o c u so n t h es m a l lw o r l de f f e c t , s c a l ef l e ep h e n o m e n a , h i e r a r c h ya r c h i t e c t u r e ，m o d u l a r i t y $ r u g t u r e a n ds oo i lw i t l lt h ed e e p e ri n s i g h ti n t ot h i sf i e l d , p e o p l eb e g i nt or e a l i z et h e h i d d e nf e a t u r e sa n ds t r u c t u r e so fn e t w o r k s i nt h i sp a p e r , w es t u d i e dt h es t a t i s t i c a l c h a r a c t e r i s t i c so fh u bn o d e si nv a r i o u si m p o r t a n tl e v e l s ，a n dt or e v e a lt h em a i n s t r u c t u r e so f t r a n s p o r t a t i o nn e t w o r k si nt h en o d e s i m p o r t a n c ep o 缸o f v i e w e p i d e m i cd y n a m i ci so n eo f t h em o s ti m p o r t a n tp r o b l e m si nt r a n s p i r a t i o nn e t w o r k s c i e n c e b yc o n s i d e r i n gt h em e d u l a rs t r u c t u r ea n ds m a l lw o r l dp r o p e r t yo fr e a l t r a n s p o r t a t i o ns y s t e m , w es t u d yt h ee f f e c to fm o d u l a r i t yo nt h ee p i d e m i cb e h a v i o r so n n e t w o r k s i ti sf o u n dt h a tt h e m o d u l a r i t yp r e v e n tt h em t e ，e x t e n ta n dt h e s y n c h r o n i z a t i o nb e h a v i o ro f t h ep r o p a g a t i o n i tr e v e a l ss o m ei m p l i c i tr e g u l a r i t i e so f t h e r e l a t i o n s h i pb e t w e e nt h em o d i l l a r i t ya n dt h ee p i d e m i cs p r e a d i n gd y n a m i c s c a s c a d i n gf a i l u r e sc a nt a k ep l a c ei nl a r g et r a n s p o r t a t i o nn e t w o r k s ，s u c ha sp o w e r 鲥d ，i n t e m e t , e t e ，s o m e t i m e s i tm a yb r i n gc a t a s t r o p h eo ft h ew h o l es y s t e m h o wt o d e f e n dt h ec a s c a d eb r e a kd o w ni so n eo ft h em o s ti m p o r t a n tp r o b l e m si nr e s e a r c h i n g n e t w o r ks c i e n c e i nt h i sp a p e r , w ei n v e s t i g a t et h ec a s c a d i n gf a i l u r eb yc o n s i d e r i n gt h e d e g r e eb a s e dn a v i g a t i o ns t r a t e g y i ti sf o u n dt h a tb yu s i n gt h ep r o p e rn a v i g a t i o ns t r a t e g y , i tc a l lr e d u c et h er i s ko f c a s c a d i n gf a i l u r ec o n s i d e r a b l y i na d d i t i o n , w ei n v e s t i g a t et h es t a t i s t i c a lp r o p e r t i e so ft h et r a f f i cd y n a m i c si n 北京交通大学博士论文 e q u i l i b r i u ms t a t eo nt r a n s p o r t a t i o nn e t w o r k sw i t hd i f f e r e n tt o p o l o g y , i n c l u d i n gr e g u l a r , r a n d o m s m a l lw o r l da n ds c a l ef r e en e t w o r k s t ou n d e r s t a n dt h ep r o p e r t i e si n 删c e q u i l i b r i u ms t a t ei si m p o r t a n ti nr e a l i z i n gt h et r a f f i cp h e n o m e n ao fr e a lt r a n s p o r t a t i o n s y s t e m s k e y w o r o s ：t r a n s p o r t a t i o nn e t w o r k ；w e i g h t e dn e t w o r k s ；h u bn o d e ；w a f f l e e q u i l i b d u m ；m o d u l a r ；s p r e a d i n g ；n a v i g a t i o n ；c a s c a d i n g 。 c l a s s n o ：u 4 9 1 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字日期：赫年 导师签 签字日期： j 1 年i 乙月；日 乩 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名： 签字日期：厶夕 年工月扣日 致谢 本论文的工作是在我的导师高自友教授的悉心指导下完成的，从初期选题、 研究，到后期撰写、修改，以及最后定稿，高自友教授都倾注了大量心血。高自 友教授严谨的治学态度和科学的工作方法给了我极大的帮助。在此衷心感谢高自 友教授对我的关心和指导 四年半以来，高自友教授不仅在科研工作中给予我严格的教导，在日常学习 和生活上也给予我无微不至的关心和照顾。高自友教授严谨的治学态度、渊博的 学识、以及对事业执著追求的精神将使我受益终生。更为重要的是，高自友教授 正直的为人，勤勉的工作作风将深深的影响我以后的生活和工作，让我能以恩师 为楷模，戒骄戒躁，不断完善自己，在学术研究中深入探索。在此，谨向我敬爱 的导师高自友教授表示最衷心的感谢和最诚挚的敬意。 在四年半的学习和生活中，得到了系统科学研究所李克平老师、孙会君老师、 张好智博士、孔宪娟博士、吴建军博士生等对于我的热情帮助，在此表示衷心的 感谢。 感谢轨道交通控制与安全国家重点实验室的所有老师和同学，和他们的融洽 相处是愉快的。 本文中有关工作的完成得益于国家重点基础研究发展计划，9 7 3 计划( 项目编 号：2 0 0 6 c b 7 0 5 5 0 0 ) ，国家杰出青年科学基金项目( 项目编号：7 0 2 2 5 0 0 5 ) 以及国 家自然科学基金重点项目( 项目编号：7 0 6 3 1 0 0 1 ) 的资助，谨此致谢。 感谢我的父母、亲人和朋友，他们的理解和支持使我能够快乐的学习工作， 顺利的完成学业。 赵晖 2 0 0 7 年1 2 月于北京交通大学 第一章绪论 1 绪论 1 1 选题背景与意义 输运是复杂系统中的普遍现象，是物质空间和位移的变化。近年来有关非平 衡态统计物理的研究表明，复杂系统中的各种输运现象存在着一些具有普适性的 规律，例如普遍存在于大量复杂系统中的幂律关系；输运网络的分形结构等 ( b a n a v a r 等，1 9 9 9 ；p e t e r ，2 0 0 0 ) 。实际上，这些讨论已经不仅仅集中在物理、 生态等领域，现实世界中的经济系统、交通系统中的各种复杂性现象同样吸引着 学者们去研究( a x t e l l ，2 0 0 1 ；k i i l m e r t 等，2 0 0 & j i a n g 和c l a r a m u n t ，2 0 0 4 ；a m a r a l 等，2 0 0 0 ) 。而现实世界存在的许多广义输运系统，其上的抽象输运过程可以包括 货币、信息、车辆、数据、能量、甚至权利的流动，它们广泛存在于城市系统、 计算机系统、互联网、经济系统等复杂系统中。如果将交通网络抽象出来，就会 发现它与人和动物体内的血管组织、自然界中的河流网络以及植物的根、茎、叶 的输运系统非常相似，而所有这些输运系统中的演化及动力学行为也遵循着某些 类似的规律( b a n a v a r 等，1 9 9 9 ：k i i h n e r t 等，2 0 0 6 ；a m a r a l 等，2 0 0 0 ) 。 本世纪初，复杂网络理论迅速成为许多科技领域的研究热点。物理学、计算 机科学、生命科学、交通科学，甚至社会科学等领域的专家学者都在对该领域进 行着深入的研究( 祁国宁等，2 0 0 4 ；汪小帆等，2 0 0 6 ) 。同时，复杂网络理论的发 展为研究大规模输运网络提供了有力的工具，使人们可以更加深入的了解和认识 大型输运网络的拓扑结构及其上的各种动力学行为。如何融合交通运输网络的特 点，深入地研究输运网络的时空分布复杂性及其流量演化机制，揭示阻塞产生的 机理，从而进一步提出控制拥堵有效方案，将有助于解决城市交通拥堵和交通安 全等相关科学问题。 现实世界中许许多多的复杂系统都可以用网络来描述。从技术世界的i n t e r n e t 网、w w w 网、通讯网络到社会科学中的组织网络、商务关系网络、科技引文网 络、科学家合作网络，乃至生物世界的神经网络、新陈代谢网络、食物链网络， 具有网络形式的复杂系统处处可见( a l b e r t 和b a r a b h s i ，2 0 0 2 ；n e w m a n ，2 0 0 3 ； m c n d e s 等，2 0 0 3 ；p a s t o r - s a t o r r a s 和v e s p i g n a n i ，2 0 0 4 ；b o e e a i e t t i a 等，2 0 0 6 ) 。 作为日常生活中具有重要地位的输运网络，同样具有复杂的拓扑结构和动力学特 征( j i a n g 和c l a r a m u n t ，2 0 0 4 ；l a t o m 和m a r c h i o d ，2 0 0 2 ；g u i m e m 和a m a r a l ， 2 0 0 4 ；g - u i m e r h 等，2 0 0 5 ；m o n t i s 等，2 0 0 5 ；s e n 等，2 0 0 3 ；w u 和g a o ，2 0 0 4 a ) 。 北京交通大学博士论文 随着计算机处理能力的不断提高和计算机网络的普及，学科之间的相互交叉 和融合趋势不断加强，促使人们开始了解大规模网络的结构复杂性和动力学行为 复杂性。而所研究网络规模的迅速增大也迫使人们改变研究的方法。对以前所研 究的小规模网络，用实际的线和点就能相对直观的画出其网络结构图，通过观察 就可以分析或解决有关网络的特定闯题。然而，对于拥有上百万个甚至上亿个节 点的复杂网络来说，直观观察方法几乎不起任何作用。而且仅凭一人之力也不可 能准确描绘出包含上百万个节点的网络结构图。实际上，随着对复杂网络研究的 逐步深入，人们提出了许多新的概念和方法。其中，统计力学的引入为复杂网络 理论提供了一个有力工具，而复杂网络理论的研究也为统计力学带来了新的研究 内容。 研究输运网络的主要目的之一是理解拓扑结构及其对复杂系统中各种动力学 行为的影响。这不仅要认识系统中的个体或组成部分的行为，更重要的是要探索 它们共同作用下的整体行为。二元网络将所有的边都被认为是完全相同的，没有 考虑不同节点间的耦合强度，即边的权值。事实上，许多网络节点问的耦合的强 度是不同的，例如社会关系网中，边权代表两个人的熟悉程度；演员合作网中， 边权代表演员问合作的紧密程度；电力网中，高压传输站点间的边权代表其距离 的远近；i n t e r a c t 网中，路由之间的边权代表网络的带宽等等。加权网络能够更准 确的描述实际复杂系统。而最近的研究也发现了加权网络所独有的复杂特性，如 无标度强度分布、强度度非平凡相关等( b a r r a t 等，2 0 0 4 a ) 。当前对加权网络的 研究和应用尚不多见，对于加权网络的研究还处于初步探索的阶段，而其中关于 交通运输网络方面的研究就更少，因而关于加权输运网络方面的研究具有一定的 理论价值。在网络结构应用于交通科学方面，2 0 0 6 年，l e v i n s o n 和y e r r a 在 ( t r a n s p o r t a t i o ns c i e n c e ) ) 上发表的文章表明，自组织演化完全可以形成具有级次 结构的道路网络( l e v i n s o n 和y e r r a ，2 0 0 6 ) 。他们的工作成功将网络模型应用到 了实际交通科学当中。 网络h u b 点通常是那些度比较大的节点，亦即枢纽节点，它们在网络中具有 重要作用。在输运网络中，这些节点都有较多的节点与之相连，同时也具有较大 的流量负载( z h o u 和m o n d r a g o n ，2 0 0 4 ) 。例如i n t e r a c t 网中，h u b 节点通常是那 些处理能力较强的大型服务器；在交通运输网络中，h u b 节点通常是那些大型的 交通枢纽或者场站。研究网络h u b 节点的相关统计特征有助于理解输运网络的框 架结构，对认识交通运输系统有一定的积极意义。 传染病可以借助于航空网络等输运网络进行传播( c o l i z z a 等，2 0 0 6 a ) ，计算 机病毒能够借助庞大的i n t e r a c t 侵入到世界上每个角落。2 0 0 3 年，s a r s 病毒通 过航空网络进行传播，导致了全球性的感染危机。2 0 0 4 年，仅中国就有超过8 0 2 第一章绪论 的用户感染了计算机病毒，而仅“震荡波”病毒就在十几天内攻击了全球数千万台 计算机( 汪小帆等，2 0 0 6 ) 针对这一类问题，在对一般输运网络进行系统分析的 基础上，结合交通网络本身的特性，研究输运网络中的传播动力学模型，进而提 出控制传播的有效方案，对深入理解输运网络上的传播性质具有一定的理论意义。 研究预防输运网络遭到协同攻击和破坏，对防治交通阻塞、提高网络可靠性 等方面均具有重要的理论和现实意义。在输运网络中，一个或少数几个节点过载 发生故障，会通过节点之间的耦合关系引起其他节点过载，进而产生连锁效应， 最终导致网络上的大规模故障( m o t t e r 和l a i ，2 0 0 2 ) 。例如，在i n t e m e ! t 网络中， 对少数路由器进行攻击会导致大量的路由过载，发生网络大规模故障。在电力网 络中，少数几个断路器、输电线路或者电站发电单元故障都会导致大范围的停电 事故。在交通运输网络中，一个交通枢纽的拥堵，一个交通突发事件都会对整个 交通网络产生非常大的影响。研究表明，具有无标度特性的复杂网络对意外故障 具有惊人的强韧性，而如果对网络进行蓄意攻击和破坏，就会迅速导致整个网络 瘫痪( m o t t e r 和l a i ，2 0 0 2 ) 。目前国内外对输运网络可靠性具有一些研究成果， 但还没有形成完善的理论体系。实际上，对输运网络的研究不应仅局限于对其拓 扑结构的研究，更重要的应用理论研究的成果对现实网络进行有效的控制。因此， 将一般输运网络的级联失效理论应用到交通运输网络中具有重要的现实意义和应 用价值。 实际上，城市道路系统，地下交通系统，公共交通系统以及航空系统都具有 复杂的拓扑结构( j i a n g 和c l a r a m u n t ，2 0 0 4 ：l a t o r a 和m a r c h i o f i ，2 0 0 2 ：m o n t i s 等，2 0 0 5 ；b a r r a t 等，2 0 0 4 a ) 。国外已经有很多学者对网络复杂性进行了大量的 研究，并从实证的角度进行了相关分析。但是就与交通密切相关的输运网络而言， 相关研究成果还比少( 高自友等，2 0 0 6 ) 。对于一般输运网络拓扑结构以及动力学 行为的定量和定性研究是一项富有挑战性的科研课题，必将对交通运输网络的研 究产生重要的现实意义和应用价值。要运用一般输运网络来解决交通问题，必须 要深入分析输运网络上的交通动力学性质。结合交通运输网络的特殊性质，研究 输运网络上的交通流状态、分布以及演化，能够应用复杂网络的理论对现实交通 网络进行网络规划指导、设计、建设及管理( 高自友等，2 0 0 6 ) 。 近年来，我国的交通运输业保持着较高的发展速度。随着经济的发展和城市 化进程的加快，城市机动车拥有量急剧增加，交通供需矛盾日益突出，交通拥挤 越来越严重。与此同时，随着城市规模的不断扩大，人、车、路的数量不断增加， 交通运输系统也会变得越来越复杂( 高自友等，2 0 0 0 ) 。作为承载人类活动的基本 构件之一，交通运输网络是国家繁荣的主要支撑条件，直接关系着经济发展、安 全保障、环境保护等各个方面。从一般输运网络的角度，利用系统科学的原理与 北京交通大学博士论文 方法，以系统分析与集成为手段，并综合利用复杂网络理论，通过对交通运输系 统目标的分解、协调、综合和优化，实现复杂系统的建模与分析，探索交通运输 网络的演化机制和动力学行为，解释阻塞产生的根本原因，对科学规划交通系统， 缓解和预防大规模交通拥堵都具有重大的理论与实际意义。 1 2 国内外研究现状 目前，国内外从复杂网络的观点对一般输运网络的演化与动力学行为的研究 主要集中在实证研究、演化建模以及动力学行为三个方面。 1 2 1 实证研究进展 在实证结果方面，已发现大量的输运网络都具有小世界效应、无标度特性等 复杂的拓扑结构。 2 0 0 4 年，g u i m e r 矗和a m a r a i 对世界航空网络进行了统计，他们将飞机场看作网 络的节点，把飞机场之间的航线看作相连接的边。结果发现世界航空网络具有明 显的无标度特性( g u i m e r 瘌a m a r a l ，2 0 0 4 ) 。2 0 0 4 年，j i a n g 和c l a r a m u n t 对城市道 路系统的复杂特性做了实证研究( j i a n g 和c l a r a m u m ，2 0 0 4 ) 。他们将每条道路看 成一个节点，如果从一条道路和另一条道路是可达的，就在这两条道路所对应的 节点之间连一条边。研究发现，通过这种方式对应得到的城市道路网络具有明显 的小世界效应。2 0 0 4 年，l a t o r a 和m a r c h i o r i 对波士顿的地下交通网络进行了实证 研究( l a t o r a 和m a r c h i o r i ，2 0 0 4 ) 。他们将每个车站看成是节点，而把每条隧道看 作是边，这样对应而成的复杂网络也具有小世界效应。s e a t o n 等( 2 0 0 4 ) 详细计 算了波士顿和维也纳两个城市铁路线网络的小世界效应。s i e n k i e w i e z 等( 2 0 0 5 a ， 2 0 0 5 b ) 分析了波兰的2 1 个城市公共运输网络的拓扑结构性质，随后又进一步分析 了波兰城市公共交通网络的相关统计特性。s c e l l a t o 等( 2 0 0 5 ) 和c r u e i t t i 等( 2 0 0 5 ) 对城市交通网络基础设施的做了一系列的相关研究。k c d m e r t 等( 2 0 0 6 ) 从白组织 的角度出发，研究了城市供应网络的标度规律。 运用加权网络来描述输运网络的研究工作也受到了广泛的关注。l i 和( 2 0 0 4 ) 和b a r r a t 等( 2 0 0 4 a ) 对中国和美国的加权航空网络进行了研究。他们是把每个机 场看作一个节点，机场之间的航线看作网络中的边，并将有效座席看作网络的边 权。通过这种方式对应得到加权航空网络的度、权重和强度都服从幂律分布。不 仅如此，航空网络还具有较大的簇系数和明显的异配性特征，而网络的强度度相 关性也呈现出幂律特征。2 0 0 5 年，m o n t i s 等人对意大利撒丁岛城镇之间的公共交 4 第一章绪论 通系统做了实证研究( m o l i 吐s 等，2 0 0 5 ) 他们是把每个城镇看作一个节点，如果 两个城镇之间每天多于5 0 个出行单位，则在这两个城镇所代表的节点之间连上一 条边。通过这种方式对应得到网络的度服从幂律分布，并且具有较大的聚类特性 和异配性。 就国内来讲，输运网络的相关研究也受到了学者们的关注。2 0 0 4 年，w u 和 c r a o ( 2 0 0 4 a ，2 0 0 6 d ) 较早的开展了输运网络的实证研究，他们首先对北京市公共 交通网络进行了复杂性分析。如果把每个公交站看作节点，把公交线路看作边， 可以发现北京公交网络具有明显的无标度特征。f u 等( 2 0 0 6 ) 研究了基于交通频 率的高速公路客运网络的无标度性质 1 2 2 输运网络建模研究进展 自1 9 9 8 年开始，在复杂网络的建模方面就有大量的研究工作 首先，w a t t s 和s t r o g a 乜的开创性成果使人们对小世界网络的建模产生了浓厚 兴趣( w a t t s 和s t r o g a t z ，1 9 9 8 ) 1 9 9 9 年，b a r a b i s i 和a l b c n 对网络无标度特征的重 要发现( b 锄b 矗s i 和灿b e n ，1 9 9 9 ) ，使得后来的复杂网络建模分析多数集中在无 标度网络方面，大量的网络演化模型，如偏好依附概率模型、网络增长模型、局 部相互作用模型、增长制约条件模型和网络演化竞争模型被相继提出( k r a p w s k y 等，2 0 0 0 ；d o r o g o v t s e v 等，2 0 0 0 ：d o r o g o v t s e v 和m e n d e s ，2 0 0 l a ；2 0 0 l b ；b a r a b 矗s i 等，2 0 0 2 ；m b e r t 和b a r a b 瓠i ，2 0 0 0 ) 。，u 和g ( 2 0 0 5 ) 研究了具有老化现象的 随机偏好连接对网络演化的影响。进而，w 诵g - a o ( 2 0 0 6 b ) 研究了效用偏好连 接的网络演化模型。 2 0 0 4 年，b a r r a t 等( 2 0 0 4 a ) 对加权复杂网络进行了较为细致的分析。这直接 引发了加权网络研究的热潮。同年，b a r r a t 等( 2 0 0 4 c ) 提出了一个加权网络的演 化模型，简称b b v 模型。该网络模型能够再现实际网络中强度、度和权重的幂律 分布。2 0 0 5 年，w a n g 等( 2 0 0 5 b ) 等提出了基于交通驱动的加权网络演化模型， 该模型不仅能反映强度、度和权重的幂律分布，还能够模拟出强度度的非线性相 关关系，高聚类性和异配特性等。随后，w 锄g 等又进一步推广了他们自己的工作， 构建了若干推广模型( w a n g 等，2 0 0 5 a ；2 0 0 6 a ) 。w u 和g ( 2 0 0 7 b ) 研究了强 度在演化加权网络中的作用和影响。z h e n g 和g a o ( 2 0 0 7 a ) 研究了复杂网络演化 中的非对称现象。 2 0 0 6 年，l e v i n s o n 和y e r r a 在权威刊物( t r a n s p o n a f i o ns c i e n c e ) 上发表文章， 从自组织演化的角度对平面交通网络进行了建模研究( l e v i n s o n 和y e r r a ，2 0 0 6 ) 。 他们的工作成功将网络理论应用到了实际交通科学当中。 北京交通大学博士论文 1 2 3 输运网络动力学行为研究进展 一般输运网络上的动力学过程涵盖了物理学、生物学、数学、计算机科学乃 至交通科学等各个领域，主要包括传播、信息交换、随机行走、同步及交通动力 学等方面( a l b e r t 和b a r a b 矗s i ，2 0 0 2 ；n e w m a n ，2 0 0 3 ) 。 传统的传播动力学认为只有当有效传播率超过一个正的临界值时，大规模的 传播才有可能发生，而p a s t o r - s a t o r r a s 和v e s # g n a n i ( 2 0 0 1 a ，2 0 0 1 b ) 的研究表明， 当网络规模无限增大时，无标度网络的传播临界值趋近于0 。这意味着即使是很 微小的传染源也足以使得传播在庞大的网络中蔓延。2 0 0 2 年，b o g u n 矗和 p a s t o r - s a t o r r a s 又研究了关联网络的传播临界值特征( b o g u n 矗和p a s t o r - s a t o r r a s ， 2 0 0 2 ) 。v o i c h e n k o v 等人则从进化选择的机理出发，研究了无标度网络的幂指数 对传播临界值的影响( v o l e h e n k o v 等，2 0 0 2 ) 。具有模块结构的复杂网络传搔行 为也开始受到关注。y a h 等( 2 0 0 7 ) 研究了具有模块结构无标度网络上的传播同 步行为。s u n 和g a o ( 2 0 0 7 ) 对区分开模块内外部感染的传播过程做了研究。 网络上的级联失效现象与网络上的传播行为有很多相似之处。2 0 0 2 年， m o r e n o 等( 2 0 0 2 ) 人提出了一种研究无标度网络的级联失效节点动态模型。同年， m o t t 盯等人提出了另一种模型来研究网络的级联失效，对比了相近平均度条件下 均匀网络与无标度网络级联失效现象( m o t t e r 等，2 0 0 2 ) 。h o l m e 和k i m ( 2 0 0 2 a ) 研究了网络增长过程中级联失效的产生条件。2 0 0 3 年，m o r e n o 等人研究了无标 度网络中由于边的拥塞所引发的级联失效( m o r e n o 等，2 0 0 3 ) 。2 0 0 4 年，c m e i t t i 等人研究了节点与边的混合动态模型( c r u c i t t i 等，2 0 0 4 ) 。2 0 0 6 年，w u 和g ( 2 0 0 6 e ) 考虑了网络模块结构对级联失效的影响。进一步，w u 和g a o ( 2 0 0 7 a ) 研究了交通平衡状态下的级联失效现象。z h e n g 和g a o ( 2 0 0 7 b ，2 0 0 7 e ) 研究了 拥挤网络中的级联失效现象。但这些模型中对输运网络的特殊性质没有充分考虑， 仍有许多有待改进的地方，比如仅仅考虑了最短路导航方式，而没有考虑其它的 导航策略等等。 在网络交通动力学方面，c h o w e l l 等( 2 0 0 3 ) 利用大型仿真软件t r a n s i m 模 拟了交通个体在虚拟的有向网络上的交通行为，发现了一些网络上的幂律特性， 并进一步分析了度和交通量之间的线性相关性以及最大连通网络大小随时间变化 的特性。虽然这些研究仅仅是通过数据仿真实验得出结果，还不能通过实际数据 进行验证，但是仍然具有重要的理论价值，是关于交通运输系统中交通行为与拓 扑结构的相互关系中的最早研究，奠定了深入研究复杂网络上交通动力学行为的 基础。g a o 和l i ( 2 0 0 5 ，2 0 0 7 ) 和l i 和( 3 a o ( 2 0 0 6 ) 利用元胞自动机模拟道路交 通流的特性，另辟蹊径地构造了交通流演化网络，发现该网络在大多数密度下可 6 第一章绪论 得到无标度性质z h e n g 和g a o ( 2 0 0 7 d ) 等通过考虑拥挤效应，研究了在无标度 网络上的流量动态特性w u 和c r a o ( 2 0 0 6 a ) 研究了无标度网络上的拥挤动态模 型。w u 和g a o ( 2 0 0 6 e ) 又进一步研究7 不同拓扑结构上的网络拥挤动态模型。 总体上来讲，给予交通行为特征的输运网络的深入研究人存在很大的空间。 除此之外，网络上的动力学行为还包括混沌同步、搜索、随机行走、自旋、 凝聚等许多复杂问题。由于本文所关注的是与输运网络密切相关的动力学特征， 在这里对其余的动力学过程就不再详述。 1 2 4 有待研究的问题 到目前为止，有关一般输运网络的演化和动力学行为仍有许多问题值得研究。 在这其中，与交通现象密切相关的衄题也非常多，现粗略整理如下： ( 1 ) 一直以来，对输运网络的建模的工作大多集中在二元网络上面，运用加 权网络摧述输运网络的工作尚不多见。现有的一些加权网络模型虽然能描述出一 般输运网络的某些统计特征，如度分布的无标度现象、高聚类性等，却不能重现 加权输运网络的某些细致特征，如指数截尾、小变量饱和等。实际上，实际输运 网络中尚有许多统计特征有待研究。如何建立更加符合实际的输运网络模型仍是 值得研究的一个重要问题。 ( 2 ) 在输运网络中，h u b 节点在保持网络的结构和功能方面具有极其关键的 作用。认识这些h u b 节点之间的关系和其所具有的统计特征能够快速认识网络的 框架结构，对认识网络上动力学行为的内在机理有一定的理论价值。而当前对h u b 节点统计特征的研究工作尚不深入。深入认识这些h u b 节点的隐含统计规律是一 项具有挑战性的工作 ( 3 ) 在输运网络上的传播过程的研究方面，当前已经有很多工作。但是，综 合考虑输运网络的小世界特性、无标度特性、模块性等结构特征对传播过程的影 响还有待深入研究。深入分析这些拓扑特征对网络传播过程的综合作用仍然是一 个值得研究的问题。 ( 4 ) 级联失效是研究输运网络的一大类问题。国内外的研究者在这方面已经 做了许多工作。实际上，研究这中动力学行为的重要意义正是在于对现实网络的 有效控制但是根据检索到的资料，对无标度网络上这种破坏性巨大的动力学过 程的相应控制方法和策略却比较少。而现有的策略大多是通过更改网络拓扑结构 来达到控制级联失效的目的( m o t t e r ，2 0 0 4 ) 寻找其它的有效策略来避免级联失 效仍是一个重要的理论问题。 ( 5 ) 当前对输运网络上的交通动力学研究主要集中在随机行走、网络导航以 北京交通大学博士论文 及负载分布等方面。但是这些工作大多没有考虑交通运输网络的实际特点，因而 这些工作在交通科学中的应用就有很大的局限性。结合实际交通运输网络的特点， 来认识输运网络的有关流量状态、结构演化、阻塞情况等，是一个值得交通工作 者关注的问题。 1 3 论文结构 本论文共七章。第一章绪论部分对输运网络的演化模型及动力学特征的研究 意义、研究背景以及研究动态作了简单的介绍。第二章介绍了一般输运网络的基 本概念以及主要模型。从第三章至第七章总结了作者博士研究生期间在一般输运 网络演化及动力学行为领域做的一些研究工作。 第三章主要是加权网络的建模工作。在该章中，通过考虑局部作用、节点合 并、交通驱动等演化机制，构建了若干适于描述一般输运网络的模型。这些模型 不仅能再现真实网络的各种幂律分布特性，还能够重现出输运网络中一些较为细 致统计特征。文中第四章对若干实际网络和经典模型网络的h u b 节点的统计特征 进行了研究，揭示了输运网络中h u b 节点的一些隐含规律。第五章对输运网络上 的传播动力学行为进行了讨论。针对一般输运网络的模块特性，分别对具有模块 特性小世界网络上的s i s 模型和s i r 模型进行了研究。第六章对输运网络上级联 失效的防御策略进行了研究，并提出将最短路信息和网络节点度信息结合起来对 网络上的个体进行导航的策略，来防止级联失效的发生，提高具有无标度结构输 运网络的可靠性和稳健性。第七章对输运网络上的流量分布进行了研究，分析了 交通平衡态下不同拓扑结构输运网络上流量分布状态。作为结论，还对全文的主 要内容和创新点进行了总结，并对作者今后要进一步开展的工作进行了展望。 论文的结构图如下页所示： 8 第一章绪论 图1 1 ：论文主要结构图。 9 第二章基本概念与模型 2 基本概念与模型 简单而言，网络是由节点以及连接这些节点的边所构成。在数学中，以图论 为形式开展的网络研究一直是离散数学的基本组成部分之一人们对图论的研究 源于1 7 3 5 年大数学家欧拉所提出的著名的歌尼斯堡七桥问题。随着对图论研究的 不断深入，到了二十世纪，网络理论逐渐发展成为一个重要的研究领域。 上世纪5 0 年代末6 0 年代初，匈牙利数学家e r d 6 s 和r 6 n y i 在网络科学领域 取得了重要突破，他们首次在论文里提出了随机图的概念( e r d 6 s 和r 6 n y i ，1 9 5 9 ： 1 9 6 0 ；1 9 6 1 ) 。自此，复杂网络开始作为一门相对独立的学科而被广泛研究。在 2 0 世纪的后4 0 年中，随机网络理论一直是研究复杂网络的基本理论。2 0 世纪即 将结束之际，复杂网络理论的研究发生了重要转变。1 9 9 8 年，铲小世界”网络的 群体动力学行为一文发表，该文不仅进一步揭示了复杂网络的小世界特性，还 建立了一个小世界网络模型( w a t t s 和s t r o g a t z ，1 9 9 8 ：w a t t s ，1 9 9 9 ) 。1 9 9 9 年， 随机网络中标度的涌现一文发表，该文揭示了复杂网络的无标度性质，并建 立了一个无标度网络模型( b a r a b a s i 和a l b e r t ，1 9 9 9 ) 这两篇文章发表以后，复 杂网络理论的研究进入了一个新的时期。网络理论的研究不再仅仅局限于数学界，