（系统分析与集成专业论文）基于复杂网络理论的区域公路交通网络可靠性研究.pdf

摘要 目前对复杂网络的研究已经成为离散系统中一个新兴的研究热点。公路交通网络是一个 典型的复杂网络，利用复杂网络理论分析公路交通网络的拓扑结构，能够准确的定位网络中 的关键核心节点，对网络中重要基础设施进行有目的的强化管理，优化交通网络的整体协调 与指挥，增强公路交通有机的、协同的管理，提高公路交通运输的服务质量等都具有重要的 现实意义。 区域公路网络的结构对于区域交通网络的连通可靠性具有重要的影响，因此本文在收集 了江苏公路信息的基础上，将江苏省公路网络抽象为两个不同的复杂网络模型：构造了邻接 城镇网络模型( a 模型) 和公路线路网络模型( b 模型) 并对其进行复杂性分析，计算网络的度分 布、平均路径长度、集聚系数等静态统计特征值。得出了邻接城镇网络模型( a 模型) 为随机 网络模型，公路线路网络模型( b 模型) 为一个典型的无标度复杂网络。 最后从复杂网络通常所面临的两种攻击一随机性攻击和选择性攻击角度评价整个区域交 通网络的连通可靠性，利用网络的整体效能降低比例与全局效率作为江苏公路网络的连通可 靠性评价指标。通过实证研究分析了江苏公路网络在不同攻击模式下可靠性的变化情况，得 出邻接城镇网络模型( a 模型) 对随机性攻击表现出了较强的抗毁性，公路线路网络模型( b 模 型) 对随机性攻击显示了较强的鲁棒性，而在选择性攻击时，网络的抗攻击能力表现极差。最 后，对公路线路网络模型( b 模型) 进行了基于介数优先和基于度优先的去点攻击，结果表明 对江苏公路网实施基于介数优先的去点攻击网络全局效率下降速度比基于度优先的去点攻击 网络全局效率下降的速度更快，从而得出b 网络模型对基于介数优先去点攻击比基于度优先 去点攻击的抗毁性更弱。 关键词：复杂网络，公路网络，模拟仿真，可靠性 a b s t r a c t a tp r e s e n t , t h es t u d yo fc o m p l e xn e t w o r k sh a sb e c o m ea l le m e r g i n gr e s e a r c hf o c u so n d i s c r e t e - t i m es y s t e m s h i g h w a yt r a 佑cn e t w o r ki sat y p i c a lc o m p l e xn e t w o r k , s oi ti sv e r y e s s e n t i a lt os t u d yh i g h w a yt r a 伍cn e t w o r kb yc o m p l e xn e t w o r kt h e o r y i th a st h e o r e t i c a la n d p r a c t i c a ls i g n i f i c a n c et oe v a l u a t er e l i a b i l i t yo fh i g h w a yt r a f f i c ；n e t w o r kw h i c hb a s e d0 1 1t h et h e o r y o fc o m p l e xn e t w o r k i t 锄i d e n t i f yt h ek e yh u bo fh i g h w a yt r a f f i cn e t w o r k , w h i c ha l s oc a n a r o u s ea t t e n t i o nt ot h ef a u l to fh i g h w a yt r a f f i cn e t w o r k i tc a np r e v e n ti n t r u s i o na n dd a m a g et o h i g h w a yt r a 伍cn e t w o r k i th a s a ni m p o r ti m p a c to ne x p l o r i n gt h ep o t e n t i a la n do ni m p m v m gt h e r e l i a b i l i t y , s e r v i c e ，a t t r a c t i v eo fh i g h w a yt r a f f i cn e t w o r k t h es t r u c t u r eo ft h er e g i o n a lh i g h w a yn e t w o r kf o rt h er e g i o n a lt r a n s p o r t a t i o nn e t w o r k c o n n e c t i n gr e l i a b i l i t yh a si m p o r t a n ti n f l u e n c e ，t h i sp a p e ra f t e rc o l l e c t i n gt h ej i a n g s uh i g h w a y i n f o r m a t i o no nt h eb a s eo fh i g h w a yn e t w o r ka b s t r a c t i o ni nj i a n g s up r o v i n c ef o rt w od i f f e r e n t c o m p l e xn e t w o r km o d e l ：c o n s a x t o e du r b a nn e t w o r km o d e la d j a c e n t ( am o d e l ) a n dt h eh i g h w a y r o u t en e t w o r km o d e l ( bm o d e l ) a n dt h ec o m p l e x i t ya n a l y s i sm e t h o d , t h ed e g r e ed i s t r i b u t i o n n e t w o r k , a v e r a g ep a t hl e n g t h , g a t h e r i n gt h ec o e f f i c i e n to fs t a t i s t i c a lc h a r a c t e r i s t i cv a l u eo fs t a t i c a d j a c e n tt o w nn e t w o r km o d e li so b t a i n e df o rr a n d o m ( am o d e l ) n e t w o r km o d e lf o rh i g h w a y r o u t en e t w o r km o d e l ( b ) f o ra t y p i c a lm o d e lo f s c a l e - f r e ec o m p l e xn e t w o r k f i n a l l y 劬mt h ec o m p l e xn e t w o r ku s u a l l yf a c e st w oa t t a c k - r a n d o m n 豁sa t t a c ka n d s e l e c t i v ea t t a c ka n g l e se v a l u a t et h ew h o l ea r e ao ft r a i 陋cn e t w o r kr e l i a b i l i t y , u s i n gt h ei n t e r n e t c o n n e c t i v i t yt h eo v e r a l le f f e c t i v e n e s sr e d u c e dp r o p o r t i o na n dg l o b a le f f i c i e n c ya sj i a n g s u h i g h w a yn e t w o r kc o n n e c t i n gr e l i a b i l i t ye v a l u a t i o ni n d e x j i a n g s uh i g h w a yn e t w o r kt h r o u g h e x a m p l e si nd i f f e r e n ta t t a c km o d e ，i ti sc o n c l u d e dt h a tt h er e l i a b i l i t yo ft h ec h a n g i n gs i t u a t i o n a d j a c e n tt o w nn e t w o r km o d e l ( am o d e lo fr a n d o ma t t a c k ) s h o w e das t r o n ga n t i d e s t r o y i n g a b i l i t y , h i g h w a yr o u t en e t w o r km o d e l ( bm o d e lo fr a n d o ma t t a c ks h o w s ) ，s t r o n gr o b u s t n e s s ，a n d f o rs e l e c t i v ea t t a c k , n e t w o r ka b i l i t ya g a i n s tt h ea t t a c kp e r f o r m a n c ei sp 0 0 lf i n a l l y , 0 nt h e h i g h w a yr o u t en e t w o r km o d e l ( b ) m o d e lb a s e do nb c t w e e n n e s s - f i r s ta n dp r e f e r r e dt op o i n t s b a s e do nt h ed e g r e eo fj i a n g s up r o v i n c e ，t h er e s u l t ss h o w e dt h a tt h ea t t a c kn e t w o r kb a s e do n b e t w e e n n e s s f i r s ti m p l e m e n t a t i o no fn e t w o r ka t t a c km a d et oo r d e rt h eo v e r a l le f f i c i e n c yo ft h e r e d u c t i o ne f f e c t s ，b e t t e rt h a nt h ep r e f e r r e dt op o i n t sb a s e do nd e g r e e sa t t a c k k e y w o r d s ：c o m p l e xn e t w o r k , h i g h w a yn e t w o r k , s m u l a t i o n , r e l i a b i l i t y 目录 1 1 - 3 2 组织结构3 1 4 论文创新点4 第二章公路交通网络可靠性综述5 2 1 系统可靠性研究的发展历史5 2 2 交通网络可靠性研究分析5 2 - 3 基于复杂网络的交通网络可靠性研究现状一7 2 3 1 国外研究成果7 2 3 2 国内研究成果8 第三章复杂网络基础理论1 0 3 1 图论基础与复杂网络基本概念。1 0 3 2 复杂网络的静态统计特征1 2 3 2 1 度和度分布。1 2 3 2 2 平均路径长度l3 3 2 - 3 集聚系数c 1 5 3 2 4 介数1 1 ； 3 - 3 复杂网络模型介绍1 6 3 3 1 规则网络模型1 6 3 3 2 随机网络模型1 6 3 3 3 小世界网络模型1 7 3 3 4 无标度网络模型。2 0 3 4 本章小结2 3 第四章区域公路网络模型的构建与可靠性分析2 4 4 1 区域公路网络的模型构建2 4 4 1 1 基础数据处理2 4 4 1 2 区域公路网络建模方式2 5 4 2 区域公路网络可靠性的定义 4 3 区域公路网络可靠性指标的确立2 7 4 3 1 最大连通子图的相对大小2 7 4 3 2 网络的效率2 8 4 4 区域公路网络可靠性测度指标2 9 n i l 2 3 3 4 5 本章小结3 0 第五章 江苏公路网络实证研究一。3 2 5 1 引言3 2 5 2 江苏路网模型构建3 2 5 2 1 数据抽象3 2 5 2 2 建模方式3 3 5 3 江苏路网网络模型静态参数计算与分析3 5 5 3 1 数据处理3 5 5 3 2a b 模型的静态参数分析3 5 5 4 江苏省公路网可靠性分析3 9 5 5 本章小结4 7 篦六章譬蔑与鼹遗妻。w 4 9 6 1 结论2 1 9 6 2 展望。5 0 致谢5 i 看参习争文献。5 2 攻读硕士期间发表的学术论文 l l i t 录。一_ 5 7 i v 第一章绪论 1 1 研究背景 第一章绪论弟一早珀了匕 随着社会经济的发展和人们生活水平的提高，传统的衣食消费比例在逐渐下降，而包 括交通在内的其他消费比例却在逐年上升。因此，对交通出行工具的投资增加成为了人们 生活水平提高的一个象征。在这种情况下，私人小汽车进入家庭已经成为了一种必然的趋 势。在国家产业规划明确大力发展汽车工业借以推动国民经济发展的背景下，国产汽车价 格大幅下降，国外汽车大量涌入国门，人们较以往有了更大的选择余地。同时，随着社会 经济的发展，出行距离的拉长无形中提升了人们对出行工具的依赖性，而小汽车以其简便、 快捷、舒适的特点备受人们的青睐。目前，正处在小汽车进入家庭的爆发期，机动车保有 量正在迅猛增长，导致了交通拥堵现象的日益严重，发生交通拥堵的次数逐渐增多，持续 时间逐渐增长。交通拥堵问题造成时间资源浪费、消耗大量的能源和其它不可再生资源， 产生严重的空气污染、噪声污染：交通事故造成了大量的人员伤亡和高额的直接和间接经济 损失，这些都阻碍了城市社会经济与环境的健康发展。为此，我们必须采取相应的对策。 近年来，随着复杂网络研究的兴起，使得人们开始广泛关注网络结构复杂性及其与网络 行为之间的关系。国内外已有很多学者对复杂网络进行了大量理论研究，有的还从实证角 度进行了相关分析。就交通网络而言，目前相关研究成果还比较少，已有的研究工作也主 要集中在地铁、街道、公共交通等网络的实证分析上，研究网络的基本拓扑结构，如度分 布、平均最短距离、聚类系数等。a m a r a l 等学者( 2 0 0 0 ) 【1 】研究了航空网络的拓扑结构；l a t o m 和m a r c l l i 耐( 2 0 0 2 ) 【2 】对波士顿地铁的网络特性进行了初步的研究；s e n 等( 2 0 0 2 ) 研究了印度 铁路网络的s m a l l - w o r l d 特性【3 ；s c a t o n 等( 2 0 0 4 ) 详细计算了波士顿和维也纳两城市铁路线网 络小世界效应 4 ；s i e n k i c w i c z 等( 2 0 0 5 ) 分析了波兰的2 1 个城市的公交运输网络的拓扑结构特 性p j ，随后，又进一步分析了波兰城市公共交通网络的聚类系数、匹配性和介数等特性。 复杂加权网络方面的研究近年来也受到了广泛关注。l i 等( 2 0 0 3 ) 、b a g l e r 等( 2 0 0 4 ) 、b a r r a t 等( 2 0 0 4 ) 和g u l m e r a 等( 2 0 0 5 ) 分别对中国、印度和全球机场加权网络特性进行了研究删。 其中，b a r r a t 等以实际数据较为深入地探讨了加权网络中权值与拓扑结构间的相关性，并 引入了加权网络中某些特性的定义。就国内来讲，城市交通网络方面的复杂性研究才刚刚 开始。w h 和g a o 等( 2 0 0 4 ，2 0 0 5 ) 较早地开展了复杂网络的理论与实证研究i g l ，分析了北京 公交网络的无标度特性。这些研究均表明，城市交通网络表现出了复杂网络的结构特性。 南京信息r t 程大学硕士学位论文 1 2 研究意义 2 0 0 3 年8 月1 4 日由美国俄亥俄州一条超高压输电线路相继过载烧断引起的 积停电事故，使得数千万人一时陷入黑暗，经济损失高达数百万亿美元。这是一 局部故障，电压崩溃，最后造成电网瓦解，引起大面积停电的严重恶性事故。经 美电网是一个典型的无标度复杂网络 严峻的现实告诉我们，一个复杂网络局部小的毁伤，往往会出人意料的产生危及全局 的后果。由此不由的思考和应对这样的问题：我们的网络到底有多可靠? 一些微不足道的 事故隐患是否会导致整个网络系统的级联崩溃? 在面对敌对势力蓄意破坏的情况下，网络 是否还能正常发挥作用? 在不久以前，准确回答这样的问题仍是十分困难的。但随着复杂 网络理论的发展，人们在逐渐理解。复杂系统之所以复杂”这一至关重要的基础问题，并 开始了解结构复杂性对网络行为复杂性的影响。复杂网络理论研究的深入，为能够定量评 估现实网络抗毁性问题提供了理论依据和良好数学工具，因此从复杂网络角度考虑公路交 通网络的可靠性具有极其重要的意义，具体如下： ( 1 ) 利用复杂网络理论分析公路交通网络的拓扑结构，对网络中重要基础设施进行有 目的的强化管理，优化路网的整体协调与指挥，增强公路交通有机的、协同的管理，提高 公路交通运输的服务质量等都具有重要的现实意义。山东师范大学李明通过对济南公交网 络进行定性定量分析，准确的定位出了大观园，泉城广场等为济南公交网络中的关键核心 节点，通过对所建模型进行一系列研究后，对济南的公交网络规划和公交站点布局，优化 调整公交线网等问题提出了建设性的意见。 ( 2 ) 许多现实网络中，一个或少数几个节点故障的发生( 这种故障可能是随机发生的， 也可能是蓄意攻击造成的) 会通过节点间的耦合关系引起其它节点发生故障，最终导致部 分节点或整个网络的崩溃，这是复杂网络中的相继故障原理。例如2 0 0 8 年湖南郴州一架输 电塔倒塌事故导致配电所跳闸断电，从而引起一系列的连锁反应，使多个省份电网的电力 设施遭到不同程度的破坏，造成了大面积的停电与交通瘫痪，使一些县城，乡镇成了孤岛， 供水停止，燃料告急，食物紧张。利用这个原理对于引起人们对公路交通网络故障的重视， 防备公路网络遭到协同攻击和破坏，控制灾后次生灾害的发生、损失的进一步扩大具有重 要的现实意义。 ( 3 ) 利用复杂网络理论对公路网络进行可靠性分析，例如金雷通过对我国西部某地域 公路网络的研究，从尽可能全面的角度分析了该地域公路交通网的抗毁性，得出了研究地 域的公路交通网毁伤阈值和最优毁伤策略。并且设定了一种简单运输任务背景下的仿真实 验模型，从一个侧面考查了地域公路交通网上两条运输线路的抗毁性。对于该地域公路网 2 第章绪论 制订应急交通管理策略，有效发掘公路网络潜力，提高公路 引力等都具有极其重要的理论和现实意义。 织结构 ( i ) 根据复杂网络的相关理论构建区域公路网络的两个基本模型：以所研究地区的8 6 7 个城镇为节点，以他们之间的连接公路为边，构建了邻接城镇网络模型( a 模型) ，以所研 究地区的2 8 4 条公路为节点，将他们相互交叉关系设置为边，构建了公路线路网络模型( b 模型) ，重点分析了两个模型的静态统计特征值，并给出在交通网络中的实际意义。 ( 2 ) 从复杂网络通常面临的两种攻击模式一随机性攻击和选择性攻击的角度重新定义 区域交通网路的可靠性，将最大连通子图相对大小和网络的全局效率作为区域公路网络可 靠性的评价指标。 ( 3 ) 实例分析研究了构建的两种网络模型的复杂网络特征，并仿真随机性攻击与选择 性攻击，得出了a 网络模型对随机性攻击表现出了较弱的抗毁性：b 网络模型对随机性攻 击显示了较强的鲁棒性，而对选择性攻击时，网络的抗攻击能力表现极差的研究结论。 1 3 2 组织结构 第一章绪论 该章主要介绍论文的研究背景及其意义，然后提出本文的研究内容、组织结构以及创 新点。 第二章公路交通网络可靠性综述 该章首先综述可靠性研究的发展历史，然后进行了交通网络可靠性研究分析，最后介 绍了复杂交通网络可靠性国内外的研究成果。 第三章复杂网络基础理论 该章重点介绍复杂网络基本理论知识。首先介绍了图论的基本理论以及复杂网络的基 本概念和理论知识，并且重点分析复杂网络的内在静态统计特征，接着阐述四种典型的复 杂网络模型的演化原理以及它们的静态统计特征值。 第四章区域公路网络模型的构建与可靠性分析 该章主要介绍了区域公路网络的模型构建，区域公路网络可靠性的定义，并确定了两 3 南京信息工程大学硕士学位论文 种区域公路网络可靠性测度指标。 第五章江苏公路网络实证研究 该章是进行案例实证分析。利用前几章的理论知识对江苏省公路网络建模后进行两种 模式攻击，分析江苏省公路网络在不同攻击模式下的可靠性变化情况。 第六章结论与展望 该章对研究的内容进行总结，并对进一步的研究工作进行了展望。 1 4 论文创新点 本论文的创新点主要有以下二点： ( 1 ) 针对区域公路网络的复杂性问题，利用复杂网络的实证研究方法，结合江苏公 路网络实际数据，将江苏省公路网构造为两个不同的复杂网络模型：邻接城镇网络模型( a 模型) 和公路线路网络模型( b 模型) 。在这两个模型的基础上研究了江苏省公路网络的复 杂性，并且分析了两种网络模型的度分布，平均路径长度，集聚系数等几何参数的意义。 从而得出了邻接城镇网络模型( a 模型) 为随机网络，公路线路网络模型( b 模型) 为典型的 无标度网络的结论。 ( 2 ) 利用最大连通子图的相对大小和网络的全局效率作为可靠性测度指标实证分析 了江苏公路两种网络模型的可靠性，同时生成两种攻击模式下的评价指标曲线，通过分析 这些曲线的变化情况得出邻接城镇网络模型( a 模型) 对随机性攻击表现出了较强的抗毁 性，公路线路网络模型( b 模型) 对随机性攻击显示了较强的稳定性，而在选择性攻击，网 络的抗攻击能力表现极差。最后，对公路线路网络模型( b 模型) 进行了基于介数优先和基 于度优先的去点攻击比较，结果表明对江苏公路网实施基于介数优先的去点攻击2 0 个点 后，网络就瓦解了，基于度优先的去点攻击2 5 个节点后网络才崩溃，对江苏公路网实施 基于介数优先的去点攻击网络全局效率下降速度比基于度优先的去点攻击网络全局效率 下降的速度更快，从而得出b 网络模型对基于介数优先去点攻击比基于度优先去点攻击 的抗毁性更弱。这些结论对于江苏省公路交通网络的建设与优化设计和发展规划工作可提 供一定的决策支持。 4 第二章公路交通网络可靠性综述 第二章公路交通网络可靠性综述 2 1 系统可靠性研究的发展历史 随着科学技术的发展，现代化的机器、技术装备、交通工具和探索工具越来越复杂。这 些机器和设备等的可靠性受到了人们的广泛重视，把这种可靠性称为系统可靠性。系统愈 复杂，若可靠性达不到较高的指标要求，则系统出故障的可能性愈大、造成的损失也愈大。 这些损失可能是经济上的、信誉上的，甚至是造成生命安全或更严重的灾难性后果。譬如 导航系统的不可靠或工作失误可导致飞机坠毁；飞机在着陆时，其控制系统如不能将飞机 的滑翔轮子可靠地弹出，后果将是不可想象的。 可靠性作为专题研究是从第二次世界大战开始的，当时出现了飞机、导弹等比较复杂的 工具，而这些兵器的主要部分一电子设备屡出故障，丧失了应有的作战能力，这就促使早 期的电子可靠性研究。1 9 5 0 年，美国国防部成立了电子装置的可靠性委员会a d h o e g r o 即 ( 1 9 5 2 年更名为a g r e e ( a d v i s o r yg r o u po nr e l i a b i l i t yo fe l e c t r o n i ce q u i p m e n t ) ) ，开 始了系统可靠性的研究，虽然对电子管的可靠性提高不大，但取得了可喜的成绩。到2 0 世纪4 0 一5 0 年代，产品的可靠性仍然低劣( 1 9 5 0 年美国海军电子设备能正常工作的仅占 1 3 ) ，而且设备维修的费用很高。为了降低维修费用，从2 0 世纪6 0 年代末开始，可靠性 的研究已经从上述的狭义的可靠性扩展到可靠性、维修性、保障性和可用性的广义的概念。 我国可靠性工程起步于2 0 世纪6 0 年代，主要在航空、航天、电子、机械等领域内展开。 2 0 世纪8 0 年代后，可靠性得到了迅速的发展，特别是在武装装备的可靠性管理和研究方 面得到了很大的进步，交通网络可靠性应用也是在近二十多年来才受到广大交通学者的重 视。到目前为止，我国已经颁布了一系列可靠性方面的国家标准( 如故障树分析程序， g b t 7 8 2 9 1 9 8 7 ) 和军事标准( 如维修性分配和预计手册，g j - b z 5 7 9 4 ) ，并在许多大型 工程项目中得到了广泛的应用。 2 2 交通网络可靠性研究分析 路网可靠性研究是最近十多年才兴起的，它是可靠性概念在道路交通系统中的应用， 它不仅结合了一般网络可靠性的研究方法和内容，而且还同时考虑了路网用户的行为特征， 为分析评价人们的出行效率和交通设施的利用情况提供了有价值的理论依据。自上世纪9 0 年代以来，路网可靠性作为世界交通领域的一项分析指标，得到世界范围内交通工作者和 5 南京信息工程大学硕士学位论文 决策者的高度重视，在日本、欧洲和美国等国家快速发展起来。近年来，随着小世界特征 和无标度性质的揭示，复杂网络理论及其应用蓬勃发展。复杂网络理论由最初的数学领域 到物理领域，而后将这种网络研究拓扑结构的方法应用于众多领域，如交通、电信、互联 网等。交通网络是关乎居民日常生活，经济发展的重要网络，它是一个结合了区域规划、 交通道路的复杂系统。 l a t o r a 和m a r c h i o r i ( 2 0 0 2 ) 对波士顿地铁网络( m b t a ) 的网络特性进行了初步研列1 0 1 ， 他们把波士顿地铁抽象为一个无向加权图：地铁站点是图中的顶点，如果至少有一辆列车 能够中途不停顿的从一个站点到达另一个站点，那么这两个站点对应的节点之间就有弧段 相连，弧段的权值表示两个站点之间的距离。经过计算发现网络整体“效率”很高，而局 部“效率”和。成本一很低，这表明此网络付出了很少的成本建立了一个运输效率很高的 网络，付出的代价是容错能力的降低，但是由于地铁网络并不是封闭的一个系统，容错能 力并不是其考虑的重要因素，所以这样的一个网络是经济的、合理的。最后研究表明波士 顿地铁是一个小世界网络。 s 饥( 2 0 0 2 ) 等在文献1 1 1 1 【1 刁中研究了印度铁路网络( 的小世界特性，在印度铁路网络 “取n ) 中，站点被定义为节点，一趟列车如果在任意两个站点停车，那么这两个站点之间 有连边，则网络的距离衡量了网络可达性的好坏。研究表明印度铁路网络( i r n ) 的平均距离 与那些集聚系数大的结点的数量呈对数关系，这说明了印度铁路网络( i r n ) 具有小世界网络 的特性。 j i a n g 和c l 猢u 似2 0 0 4 ) 对城市街道网络进行了研列1 3 1 【1 4 】，把实际的城市街道网络抽 象成以指定的街道为节点、以街道交叉路口为边的网络在此抽象网络上计算了网络的连 通性、平均路径长度和聚类系数，证实了城市街道网络具有小世界特性，但是不具有无标 度特征。 g u i m e r ar o g e r 等学者研究了航空网络的拓扑结构，g u i m e r ar o g e r 和m o s s a 在研究全 球航空网络( g a 时1 6 1 1 1 7 l 【，将每个机场所在的城市看成是网络中的节点( 一个城市的多个 机场看作是一个节点) ，如果两个城市之间有直通的航班，那么这两个城市对应的结点之间 有边相连( 假设航班都是双向飞行的) 。通过计算，得出平均换乘航班数和网络节点数的对 数成正比，集聚系数也比同等完全随机网络的集聚系数高很多，所以航空网络也是小世界 网络。 6 第二章公路交通网络可靠性综述 2 3 基于复杂网络的交通网络可靠性研究现状 2 3 1 国外研究成果 由于计算机技术的迅猛发展，人们开始有能力收集和处理各种不同类型网络的实际数 据。特别是在关于小世界网络和无标度网络的奠基性工作之后，人们对来自不同领域的各 类复杂网络进行了广泛深入的实证研究。不断涌现出来的实证结果成为促进复杂网络研究 迅速发展的“动力源泉”。沿用n e w m a n 的方法【1 9 i ，可以将现实世界中的复杂网络分为四 大类： ( 1 ) 社会网络 社会网络是人或人的群体的集合，这些人之间具有某一接触或相互作用模式，例如个体 之间友谊网络，公司之间商业关系网络，家族之间联姻网络，性接触网络。一个丰富且相 对可靠的社会网络数据源是合作网络。此种类型网络一个经典的例子是电影演员的合作网 络，其他例子包括公司董事网络，科研合作网络。另一个关于社会关系的可靠数据源是通 讯记录，例如电话、短信、电子邮件等。a i e l l o 等对由a t & t 长途网络一天内的通话所构 建的网络进行了研究 2 0 l 。e b e l 等利用e m a i l 服务商保留的日志文件重新构建了e l 大学五 千名学生之间的e m a i l 通讯模式【2 1 1 。最近，o n n e l a 等研究了包含四百六十多万个节点的移 动电话通信网络，该网络中移动电话用户为网络节点 2 2 1 ，相互之间若有通话记录则连接一 条无向边，用累积通话记录对边赋权。 ( 2 ) 信息网络 信息网络的类别有时也被称为“知识网络”。信息网络经典之例是学术论文之间的引文 网络。引文网络在p r i c e 早期论文中有所讨论，作者首次发现引文网络的入度和出度分布 都服从幂律分布。从那以后，出现了很多其他的有关引文网络的研究，特别值得一提的是 s e g l e n 和r o d n e r 所做的工作。信息网络另一个非常重要的例子是万维网网。万维网自从二 十世纪9 0 年代首次出现以来，关于它的研究非常多，特别有影响力的包括a l b e r t 等的研 究，k l e i n b e r g 等的研究以及b r o d e r 等的研究 2 4 1 。信息网络的其他一些例子还包括专利之 间的引用网络，p 2 p 网络等。 ( 3 ) 技术网络 第三种复杂网络是技术网络，即人类设计构造的网络，其典型目的是分配商品或资源。 电力网络是一个很好的例子，它是一个高伏电压三相传输线的网络，跨越一个国家或者国 家的一部分。其他的例子包括航空网络，公路网络，铁路网络，河流网络。另一个研究得 7 南京信息工程大学硕士学位论文 非常广泛的技术网络是因特网。由于因特网上计算机的数量庞大且经常变动，因 络结构的研究通常是粗略的。目前关于因特网路由器级或自治系统级拓扑结构的 丰富。 ( 4 ) 生物网络 生物网络的典型例子是代谢网络，它是代谢基质和代谢产物的刻画，如果已知代谢反应 存在，其作用于给定基质并产生指定产物，两者之间由有向边连接。蛋白质之间的相互作 用网络也是一种重要的生物网络，很多研究人员对其结构属性进行了研究。生物网络还有 一个研究得很多的例子就是食物网。构建完整的食物网工作量非常大，但近年来一些学者 对食物网的拓扑结构进行了统计学研究，例如s o l 6 ，m o n t o y a ，c a m a c h op a g eo u n n e 2 7 - 3 0 | 。 2 3 2 国内研究成果 就国内来讲，城市交通网络方面的复杂性研究才刚刚开始，2 0 0 6 年王品、彭其渊等人 采用复杂网络的研究方法【3 1 1 ，对成都市公共汽车交通建立了公交线路、公交换乘和邻近站 点3 种复杂网络，以d e l p h i 软件为辅助工具，得出了成都市公交网络的拓扑结构和一些静 态几何量参数，并运用这些静态几何量进行了网络的拓扑特性分析! 3 2 1 。同年，张译等人从 研究城市公交系统的网络宏观拓扑性质出剧3 3 】，将城市公共交通系统划分为公交站点网络 和公交线路网络，通过引入网络分析中一些常见的重要拓扑参数来对城市公共交通系统进 行分析，以北京市公交系统为例，计算并分析了这两种网络的拓扑参数，并从交通工程的 角度对这些拓扑参数的具体意义进行了研究，最后从交通工程和城市规划的角度为城市公 交系统的建设提出了一些建议瞰】。 田炜等人在2 0 0 8 年对复杂网络形成、特性和代表性研究成果简要总结的基础上，通过 对国际航运网络的实证分析，研究了国际航运网络表现出的小世界效应和无标度特性，对 其存在的一些个性进行了分析。将港口产业与港航服务企业等效为产品网络中的主导产品 与其互补产品，将航运企业等效为消费者，通过对产品网络中网络效应的分析，以及对消 费者两阶段预算分配过程的研究，对港航系统产品网络中网络效应特性的内生机理进行了 探讨，并指出某些特定领域内复杂网络统计特征源于产品系统的网络收益对产品效用的影 响【3 5 】。 刘宏鳃等人以城市为节点，城市间直航线路为边，实证地研究了中国城市航空网络的拓 扑性质。证明了中国城市航空网络是一个小世界网络，具有短的平均路径长度和大的簇系 数，且其度分布服从幂律分布，当度较小时，中国城市航空网络未表现出度相关性：而对于 3 第二章公路交通网络可靠性综述 度较大的节点，则呈现出负相关性。并进一步地以城市间直航计划每周提供的座位数为边 权，研究了网络的含权性质，发现该网络节点度权之间是幂律相关的，相关指数为1 3 7 | 3 6 1 。 这些研究都表明，包括轨道交通网在内的交通网络是典型的无标度复杂网络，它们具 有优先连接的特性并且持续成长，节点的分布遵循幂次定律，因此网络中存在着少量拥有 大量连接的“枢纽点”同时存在着大量拥有少量连接的节点。这些无标度网络对意外故障 具有惊人的强韧性，被“随机去除”破坏的主要是那些只拥有少量连结不重要的节点，随 机去除某些交通节点并不会造成整个交通网络的瘫痪，但如果蓄意对交通“枢纽点”进行 攻击和破坏，就会迅速导致整个网络瘫痪。这一特性本质上源于这些复杂网络的非同质拓 扑结构，这些基于复杂网络理论的分析大大提高了对交通运输网络可靠性和鲁棒性的科学 认识。因此，对区域交通网络可靠性的深入分析必须建立在复杂网络的理论基础上。 9 南京信息工程大学硕士学位论文 第三章复杂网络基础理论 3 i 图论基础与复杂网络基本概念 网络( n e t w o r k ) 在数学上用图( g r a p h ) 来表示，复杂网络可以用图论的语言和符号 精确简洁地加以描述。图的研究最早起源于1 8 世纪瑞士著名数学家e u l e r 的哥尼斯堡七桥 问题。图论不仅为数学家和物理学家提供了描述网络的语言和研究平台，而且其中结论和 技巧已经被广泛地移植到复杂网络的研究中。 一个具体的网络可以抽象为一个由点集v 和边集e 组成的图g = ，e ) 。节点数记为 n = i v l ，边数记为m = i e i ，v = v l ，v 2 ，v 3 ，v d 代表节点的集合，e = e l ，e 2 ，e 3 ，e m 代表边的集合。e 中每条边都有v 中一对点与之相对应，如果任意点对( v i ，v i ) 与( v j ，v i ) 对 应着同一条边，则该网络称为无向网络( u n d i r e c t e dn e t w o r k ) ，否则称为有向网络( d i r e c t e d n e t w o r k ) 。如果给每条边赋予相应的权值，那么该网络就称为加权网络( w e i g h t e dn e t w o r k ) ， 否则称为无权网络( o u t w e i g h e dn e t w o r k ) 。当然，无权网络也可以看作是每条边的权值都为 1 的等权网络。此外，一个网络中还可能包含多种不同类型的节点。例如，在社会关系网 络中可以用权表示两个人的熟悉程度，而不同类型的节点可以代表具有不同国籍、地区、 年龄、性别和收入的人。图3 1 给出了几个不同类型的网络的例子。 1 0 第三章复杂网络基础理论 瓜q ，| l ( a ) ( a ) 单一类型节点和边的无向网络 i 卜二 1 ， 厂 ( c ) ( c ) 节点和边权重变化的无向网络 j - 、o l - ( b ) ( b ) 不同类型节点和边的无向网络 围3 - 1 不同类型罔络的倒子 ( d ) ( d ) 有向网络 自然界中存在的大量的复杂系统都可以用形形色色的复杂网络加以描述。从统计物理 学的角度来看，网络是一个包含大量个体以及个体之间相互作用的系统。通常把个体视为 网络中的节点，把个体之间的相互联系视为节点和节点之间的联系。任何一个有着相互作 用的复杂系统，在一定的抽象下，都可以看作是一个网络。如册网络可以看成网页之间 通过超级链接构成的网络m 1 ：科学家合作网可以看作不同的科学家之间合作关系构成的网 络旧1 ，基因调控网络可以看作是不同的基因通过调控与被调控的关系构成的网络等啪1 。图 3 2 是一个简单网络的示意图。 南京信息工程大学硕士学位论文 2 3 5 图3 2 一个由5 个点和4 条边组成的简单同络示图 一个图可以用集合图形表示，这种表示有直观形象的优点。网络中节点的数目n 为网 络的大小：节点间相互连接的数目，即为边数l ( e ) ，这样，图还可以用矩阵表示，这样可 以运用代数的技巧解决图论的问题，而且有利于在计算机上进行运算。每一个图都可以定 义一个邻接矩阵( a d j a c e n c ym a t r i x ) 1 来