基于复杂网络的武汉市公交网络的研究

1、数学建模课程论文公交网络的复杂性研究专业班级姓名学号任课老师星期一（三）楚扬杰星期二（四）何朗2010年月日基于复杂网络的武汉市公交网络的研究摘要本文运用复杂网络理论来研究武汉市公交网络，以武汉市公交站点为节点，这些公交车站在公交线路运行之中的合作运输关系抽象成边，由此形成武汉市复杂公交网络，建立了公交停靠站点网络模型和公交换乘网络模型。小世界效应和无尺度特征是复杂网络的两个典型的统计特征。我们要从复杂网络理论出发，研究公交网络上的一些统计特征，研究公交网络的增长机制，构造网络增长模型，通过对网络演化机制的研究，给出促进武汉市公交网络新的发展方案与模式。在实际的交通出行中，拥塞在交通网络中向相

2、邻的路段和节点进行传播，这类似与病毒在复杂网络中的传播，把复杂网络解决拥塞的理论应用到实际的公交网络中，就可以解决公交网络的拥塞问题，对拥塞的传播进行有效地控制。在设计规划公交网络时考虑网络的无尺度特性，使公交网络具有较高的鲁棒性，在某些交通路段出现交通故障的时候能够保持公交网络畅通。随着武汉市的扩建与改造，公交网络也在不断的扩建与改造，如何把有限的资金应用到最利于解决问题的根本之处不容忽视，通过对公交网络复杂性中的无尺度特性的进一步研究，找到公交网络的中心节点，就可以考虑资金分配等问题，进而延伸到公交网络的各种性能指标的设计（如拥塞、环境、能耗、收费等等）。由于武汉市公交网络太庞大，太复杂，

3、对于编程和作图有较大难度，目前本文只进行理论上的武汉市公交网络的复杂性研究，并不提供武汉市公交网络复杂性详细数据的分析与研究。关键词：复杂网络，公交网络，小世界效应，无尺度特性问题重述武汉市城市公共交通已初步形成了市场经济条件下以公共汽、电车为主,出租车和小公共汽车为辅,轮渡为补充的综合运输体系,公交服务水平和舒适度不断提高,满足了不同层次乘客出行的需要。常规公交仍是武汉市公共交通的主体,承担了72%的公交客流。作为公共交通辅助的出租车和小公共汽车,分别承担了公共交通客运量的21.5%和6.1%。轮渡作为武汉市公共交通的补充部分,也承担了公共交通客运量的0.40%。目前多数大中城市的客运主要依

4、靠高效的公交系统，因此公交线网的设置得是否合理会直接影响乘客出行时间、换乘以及系统运营成本。理想的公交线网布局应满足大多数交通需求的要求，具有服务范围广、直达率高(换乘率低)、非直线系数小、出行时间短以及可达性高(步行距离短)等特点。但是随着城市布局和人口分布情况的改变，公交线网的布局会逐渐不能满足需求，从而影响城市的进一步发展。这时，就需要通过调整原有的公交线网来满足乘客的需求，通常的调整方法是凭经验修改网络的局部线路。这种做法极大的依赖于设计者的实践经验，缺乏必要的连贯性和可靠性。城市交通网络的效率对城市的功能和市民的生活具有很大的影响,现实中的交通都受到特定交通路线的限制,如停靠站点、公

5、交线路等,因此改善城市交通网络的运输效率等问题都可以依靠复杂网络的相关理论来解决。目前，国内外有关复杂网络的应用研究领域主要在：Internet、社会关系网络、生物学领域内的各种网络等,但在公交网络方面的研究成果相对较少,相关的应用实例主要有:Sienkewicz等(2005a、2005b)分析了波兰的21个城市的公共运输网络的拓扑结构特性，随后，又进一步分析了波兰城市公共交通网络的聚集系数、匹配性和介数等特性。而关于复杂加权网络方面的研究近来受到了广泛的关注。Latora的课题组做了一系列的关于城市基础设施网络中心点的研究,提出了全局有效性和局部有效性的定义，并研究了波士顿地铁等网络的有效性

6、，但是，由于其定义的地centrality只是利用了网络的拓扑结构信息,没有结合实际网络中交通流量的信息,因而不能完全适合城市交通网络。就国内来讲,城市交通网络方面的复杂性研究才刚刚开始。Wu和Gao等(2004、2005)较早地开展了复杂网络的理论与实证研究,分析了北京公交网络的无标度特性。Gao和Li(2005)利用元胞动机模拟道路交通流的特性,另辟蹊径地构造了交通流演化网络,发现该网络在大多数密度下可得到无标度特性。高自友等(2004)根据北京公交网络的无标度特性,结合公交网络平衡配流理论与方法,提出了寻找公交网络集散点的方法。本文以武汉市公交网络复杂性研究为例，介绍复杂网络在城市公交网

7、络研究中的应用，大体思路为：结合武汉市公交网络实际数据，构造两种不同的公交复杂网络模型：公交停靠站点网络模型、公交换乘网络模型；在这两个模型上研究武汉市公交网络的复杂特性，分析武汉市公交网络的小世界效应和无尺度特性；在公交停靠站点网络模型上，进一步对公交网络的鲁棒性与脆弱性进行分析。问题分析一、复杂网络简介复杂网络：复杂网络是大量真实复杂系统的抽象,它能够刻画复杂系统内部的各种相互作用或关系。平均路径长度(AveragePathLength):网络中任意两点之间的距离定义为连接两点的最短路径上的边数,网络中任意两个节点之间的距离的最大值称为网络的直径，记为D。网络的平均路径长度L定义为任意两点

8、之间的距离的平均值。度与度分布(Degree&DegreeDistribution):节点度是单个节点的属性中重要的概念，指的是与该点所连接的边数;度分布则表示节点度的概率分布函数P(k)，它指的是节点有k条边连接的概率。度是描述网络局部特性的基本参数；度分布函数则反映了网络系统的宏观统计特征。聚类系数(或称集群系数，ClusteringCoefficient)：节点的聚类系数被定义为它所有相邻节点之间的实际连接数目占可能的最大连接边数目的比例，网络的聚类系数C则是所有节点簇系数的平均值。介数(Detweenness):节点的介数定义为网络中经过该点的最短路径的数目,反映了节点的影响力，各种交

9、通枢纽都是介数较大的节点；类似地，可以定义边的介数，即经过该边的最短路径的数目，它反映了边的影响力，这对于在现实网络中发现和保护关键资源具有重要意义。规则网络是最简单的网络模型，其特点是每个节点的近邻数目都相同，如一维链、二维晶格、完全图等。用的最多的是最邻近耦合网络。规则网络具有较大的聚类系数和平均路径长度。随机网络与完全规则网络相反的是完全随机网络，其中一个典型的网络模型是ErdEs和Renyi提出的ER随机图模型ErdEs和Renyi的重要发现是ER随机图具有涌现或相变性质。ER随机图的节点度服从泊松分布，它具有较小的平均路径长度和较小的聚类系数。小世界网络实证研究表明，许多现实网络大都

10、表现出集群现象，由此引发人们对小世界网络的研究，作为从完全规则网络向完全随机网络的过渡，Watts和Strogtz于1998年引入了小世界网络模型，称为WS小世界模型。WS小世界模型的构造是从规则图开始，以概率P随机化重新连接网络中的每个边。小世界网络的节点度服从指数分布，可以同时拥有较大的聚类系数和较小的平均路径长度，这就是小世界特性。BA无标度网络：ER随机图和WS小世界模型的度分布与许多现实网络都不相符，用它们来描述现实网络具有很大的局限性，为了更好的描述现实网络，Barabasi和Albert考虑实际网络的增长特性(growth)和优先连接(preferentialattachment

11、)特性,提出了一个无标度网络模型，称为BA模型。BA无标度模型节点的度服从幂率分布，具有较小的聚类系数和平均路径长度。无标度模型对随机故障表现出良好的鲁棒性，但对蓄意攻击就显得比较脆弱，这都源于其存在集散节点。无标度网络的一些理论可以用于预防交通堵塞。二、复杂网络在公交网络中的应用公交网络是由代表真实系统中个体的节点与表示个体间关系的边组成的,基于与其它类型网络的比较,公交网络有如下几个独特的性质:（1）网络大小差别很大。停靠站的数目从几百到几千。（2）多路车都经过几个不同的站。（3）增长性,随着城市规模及经济的发展,新的公交站点不断的增加到网络中，当然也有部分公交站点由于其功能不适应城市发展

12、及出行需求而被从原来的网络中删除。（4）偏好依附性,在城市公交网络中一定存在几个大的站点,我们称之为大站或集散点,它们在城市公交网络中起着重要的作用,通常新加入的站点更容易与之相连,这也符合我们所说的“富者愈富”的观点。（5）公交网络的描述方法有三种:一种是L空间方法,在此空间中,交通站点视为节点,若两个站点是某一交通线路上相邻的,那么它们就有连边;另一种是P空间方法,即交通站点视为节点,若两个站点有直达交通路线,那么它们就有连边，显然，在P空间中，最短路径就是两站之间需要转车的次数加1,而且这个距离比L空间的要小些;还有一种是K空间方法，与城市网络的第一种描述方法类似,即交通站点视为节点，若

13、两站点间在实际中是相连的,它们就有边。K空间方法构造的网络是L空间方法构造网络的子网络,而L空间方法构造的网络又是P空间公交网络和航空网络以及纯地铁网络又有着不同，航空网络中一条线路一般就只对应着两个站点，一个起点一个终点，而公交网络中一条线路覆盖很多个站点，所以公交网络是否也具有同航空和地铁网络相仿的小世界特性是值得我们去验证的。城市公交网络的设置是经过规划的，所以它不是随机图;而规划会受到多种因素的影响，这就决定了此网络不具有完全的规则性。定性的分析，城市公交网络具有无尺度特性。事实上，公交网络构成了一个复杂网络，但是已有的研究都忽略了一个基本事实，现实中的交通都受到特定交通路线的限制，而

14、且公交网络的点权分布的性质不同于其它加权网络，这个现象为复杂网络的进一步研究提出了新的问题。总体上来讲，基于交通行为特性的交通网络复杂性研究还处于起步阶段，相对的研究成果较少。城市交通系统是一个典型的、开放的、复杂的大系统，公交网络是城市交通网络的一个方面，在城市交通网络中的许多问题，在公交网络中也同样存在，比如:（1）城市公交网络中交通枢纽或Hub点（中心节点）的确定问题，这一问题的确定有利于对蓄意攻击进行预防，也有助于交通网络的设计。（2）城市交通拥堵的预防和控制方法。（3）公交网络设计及城市规划布局的相关问题。（4）城市交通网络鲁棒性和可靠性的研究。模型建立城市交通系统本身是由道路系统、

15、流量系统和管理系统组成的一个典型的、开放的复杂巨系统.城市交通网络由交叉路口和连接它们的街道组成，车辆在网络上行驶。其中的交叉路口或小区对应于节点,而街道对应于弧或边，车辆在边上行驶遇到的阻抗（可以用所花费的行驶时间来描述）对应于边上的权重。这样它就可以抽象为一个复杂加权网络。图2图5分别是来源于相关资料中的芝加哥、圣地亚哥、上海和北京的城市交通系统结构图。图2芝加哥交通系统结构图图3圣地亚哥交通系统结构图图4上海交通系统结构图北京而交il第的图图5北京交通系统结构图城市交通网络具有绝大多数复杂加权网络的特征：网络行为的统计性:对特大型或大型城市而言,其网络节点数十分巨大可有成千上万,从而大规

16、模性的网络行为一般都具有统计特性。网络连接的稀疏性:一个有N个节点的具有全局耦合结构的网络的节点连接数目为O(N2)，而实际存在的大型网络的连接数目通常为O(N)。连接结构的复杂性:大多数现实世界的大型网络的连接结构既非完全规则也非完全随机。（4）网络的时空复杂性:复杂网络的演化通常都具有空间和时间的复杂性,能够展示丰富多彩的复杂行为（如分岔和混沌）。（5）网络节点之间（或边上）的同步运动（包括同步混沌）。目前，将城市网络抽象为复杂网络，并进一步利用网络理论深入研究城市网络的各种特性，得到了广泛的关注。城市网络的抽象方法有两种：一种是将交叉口视为节点而将道路视为边，另一种是将道路映射为网络中的

17、节点，将道路的交叉口映射为节点间的连边。本文通过第一种方法将城市公交网络抽象为复杂网络模型，下面介绍公交网络的两类复杂网络模型。公交停靠站点网络模型我们可以通过自然地方式构造一个公交停靠站点网络模型，顶点是公共汽车停靠站点，如A、B,如果有公交线路通过A与B,且这些线路在A与B之间都没有停靠站点，则A与B之间有一条边。图6给出了一个具有10个站点14条边的公交停靠站点网络模型。停靠站点网络模型保留了公共交通网络基本的拓扑特征，可以通过讨论它的基本几何量如平均路径长度、度分布等来研究公共交通网络的拓扑性质。公交停靠站点网络模型上的基本几何量的实际意义：平均最短路径放映了交通系统中任意两个站点之间

18、最少的站点数目，度分布则联系着通过各个站点附近公交线路的密集程度。为了更直接的揭示停靠站点在公交网络中的作用，还可以为停靠站点网络赋权值，使之成为加权复杂网络。定义边的权重为边所在的公交线路的数目，边权放映了有多少条线路通过该地段，也反映了该地段在交通网络中的重要性，在考虑建设快速通道的时候应该对具有较高边权的地段进行。定义点权为停靠站点所有边的边权之和，点权说明了该停靠站点在公交网络中的地位，为使公共交通网络更加方便快捷，就应该加强这些停靠站点的建设。图7给出了武汉市交通结构图和根据公交停靠站点网络模型构造的武汉市公交网络模型。687*5LH=.I.!h沙ui洽案11at龙口uftULMAH

19、ttfWVI变山厂夭J-Z/：-PQgO;A厂酌期办、白五山1介1：.vW*hI孑“/扃7电炉，毘坯北込理叫6-；卜昴“6逼/J用产E件*办弘ff-iS-SU蓟知图7武汉市交通结构图和公交武汉市公交停靠站点网络模型公交换乘网络模型换乘情况是刻画公交系统可达性的一个重要指标。为了研究公交系统的换乘情况，可以建立公交换乘网络模型，其顶点是停靠站点，如果站点之间有一条公交线路通过则有一条边连接。这种方式构成的网络是一个无权网，且同一条公交线路上的各个站点之间是完全连接的。定义顶点之间的距离为连接两个顶点之间的最少边边数，则距离代表了从某一停靠站点到另一停靠站点之间的换乘次数加一。图8给出了一个公交换

20、乘复杂网络的模型，其中包含了2条公交线路，12个停靠站点，公交线路一是：1-2-3-4-5-6-8-10，；公交线路二是：12-11-10-9-2-3-4-5-7。两条线路在2、3、4和5部分相同，也即在线路2-3-4-5部分重合。公交换乘网络中每一条公交线路的所有站点之间都是有连边的，构成了一个完全图，每条公交线路构成的完全图之间重叠构成了公交换乘网络。模型分析交通网络由于其现实中的重要性、复杂性，需要从新的研究视角来分析其特征，从而为解决交通的实际问题服务，小世界网络的研究适应了这种需求。一个网络的网络特性可以从宏观和微观上描述一个网络的特点，而这些特点一般都是现实指标的体现。交通网络是否

21、合理，是否高效，是否规划的能够方便人们便捷出行，减少出行时间等等，很多这种问题都可以通过研究网络性质来得到验证和体现。小世界网络可以被用来作为一种验证网络的合理性的工具，也为网络的规划、修改和扩充提供了理论依据。结合武汉市公交网络数据，在公交停靠站点网络模型和公交换乘网络模型上分别验证其是否具有小世界性质，并分析意义及其合理性。网络模型的增长性和优先连接两种机制，有助于解释中心节点（Hub）的存在：当新节点出现时，它们更倾向于连接到已经有较多连接的节点，随着时间的推进，这些节点就拥有比其他节点更多的连接数目。这种“富者愈富”的过程，有利于早期节点，使得它们更有可能成为中心节点。公交网络是不断增

22、长的，随着城市经济的发展及规模的扩大，在不同的时期一些新的公交线路会增加到公交网络中，也有很少一部分旧的公交线路会被剔除，但总体的公交线路还是不断增长的，新的公交线路及公交站点会不断地出现以满足需求。在公交网络中，存在少量节点度很大的节点，这些节点我们可以称之为“交通中心节点”。当建立一条新的公交线路时，这些“交通中心节点”比其他公交节点有更大的可能性存在于这条新的公交线路上，比普通的公交节点具有更大的研究意义。为了更直接的揭示停靠站点在公交网络中的作用，还可以为停靠站点网络赋权值，使之成为加权复杂网络。定义边的权重为边所在的公交线路的数目，边权放映了有多少条线路通过该地段，也反映了该地段在交

23、通网络中的重要性，在考虑建设快速通道的时候应该对具有较高边权的地段进行。定义点权为停靠站点所有边的边权之和，点权说明了该停靠站点在公交网络中的地位，为使公共交通网络更加方便快捷，就应该加强这些停靠站点的建设。结合武汉市公交网络数据就可以分析每一条公交线路、每一个公交停靠站点在公交网络中的作用大小，为进一步规划提供了理论依据。模型评价基于复杂网络理论，本文建立了公交停靠站点网络模型和公交换乘网络模型，为解决实际问题提供了一种研究方法。但鉴于此命题可以扩充到研究城市交通网络，深入研究分析，我认为以下问题将是今后城市交通网络复杂性问题的研究主题:城市交通网络中交通枢纽或Hub点的确定问题自从2001

24、年“911”事件之后,如何利用复杂网络的相关理论来有效预防城市重要基础设施可能遭到的攻击,尤其是蓄意攻击,以保证国家和城市的安全,成为各国科学家和研究机构的热点课题。首先要解决的问题就是如何寻找网络中的Hub点，这是一个理论难题。城市交通网络的Hub点的确定不仅有利于对蓄意性攻击进行预防,而且有助于交通网络设计问题的解决,即如何将有限的资金最有效地应用到网络改扩建或新建工程中。在这方面我们已进行了初步的研究。下一步需要考虑交通网络中，结合城市交通用户与系统平衡配流理论及破坏性实验，寻找城市交通系统Hub点的方案；不同拓扑结构特性以及网络规模对Hub点位置的影响，网络演化到何种程度会引起Hub点

25、发生变化等等问题。城市交通网络的时空复杂性及普适性演化机制城市交通网络演化的一个重要特点是同时具有时间与空间上的复杂分布问题，交通网络节点位置是网络演化过程的首要问题。可以根据交通网络流量分布及阻抗分布的特点，利用概率统计分布模型来确定网络新节点的时空分布，给未来城市规划提供科学合理的选点方案。对现有网络演化机制进一步深入研究，探索复杂网络的普适性形成机制，构造无标度网络、小世界网络以及完全随机网络等的统一演化模型。在此基础上，将道路交通流、网络交通流模型与复杂网络特性相结合进行相关科学研究，探讨未来城市交通系统的一般演化规律，探索网络结构相变的阈值，进一步描述复杂网络形成的机理，最终目标是形

26、成描述交通网络动力学一般规律的数学刻画.为我国特大型城市交通网络的发展提供决策上的支持。城市交通拥堵的预防控制方法当前，日益严重的城市交通拥堵问题已大大影响了城市的经济建设和社会发展的运行效率，给人们的生活和工作带来了极大的不便与损害。因此城市交通拥堵是当前最为关键的城市交通问题。一般来说，城市交通拥堵的产生有三种方式:暂时路障、永久能力瓶颈和随机波动。城市交通拥堵通过分岔过程产生路段间排队的延伸，每个排队依次在各路段的交叉口产生新的分岔。最初，分支的拓扑结构类似于一棵简单的树，但在某种状态下，排队会沿一个街区四周排成长队从而形成一个封闭的环，从而造成局部交通瘫痪。在其它地方也可能出现这种状况

27、，同时伴随着更多的封闭环；因此树将发展成为一种更精确的可称为“网格”的形态(见图9，Wright&Roberg,1998)。在实际的交通出行中，某一路段的拥堵在城市交通网络中会逐渐向相邻的路段和节点进行传播，因此深入研究拥挤瓶颈处交通流形成机理以及城市交通网络这一特定的复杂加权网络的演化规律，可从本质上解释城市交通拥堵机理，进而造成局部交通瘫痪的根本原因。所以在对交通网络拓扑特性进行系统分析的基础上，结合城市交通网络本身的演化特性，构建符合实际的城市交通拥堵传播模型，同时探讨网络节点在传播中重要性的度量，分析不同拓扑结构特性对拥堵传播的影响,进而提出有效地缓解和预防交通拥堵的道路规划及控制策略

28、,是具有重大科学意义的课题。要特别注意将道路交通流状态、网络交通模型与复杂交通网络演化相结合进行系统而深入地研究(见图10)。(a)结构(W封阿坏图9网格状交通网络的阻塞传播类型城市交通网络的鲁棒性和可靠性的研究是城市可持续发展需要解决的关键性问题之一。因为网络局部的失效会增加网络其它部分的负担,潜在的使其超载并破坏其功能。以这种方式,失效会遍布整个网络,导致更多的破坏。我们认为,应该考虑路段的阻抗与网络拓扑结构的相关性,来研究城市交通网络的遭受协同式攻击模型或局部网络失效模型,并探索网络局部失效或被破坏后的补救方案,以最大程度地减小网络失效带来的损失,为预防城市交通网络遭受恶意破坏进而瘫痪提

29、供科学的预防策略。城市交通网络设计及城市规划布局的相关问题城市交通网络规划问题一直是交通领域中的重要问题之一。在相同条件下,哪种结构的城市交通网络具有最大的承载能力?从系统最优和用户最优的角度分别分析对于城市交通网络何种网络结构将是最适宜的(即网络的总阻抗最小)。从而用以指导城市交通网络设计,为城市的长期结构规划提供决策支持.在探讨Hub点的确定时,我们提到过关于交通运输网络的规划问题,这里要强调的是,确定了要修建的或扩建的道路后,如何对道路的能力进行规划：考虑了阻抗的相关性,探讨不同阻抗分布对复杂交通网络中的运输方式的影响,并给出节点或边上流量的分布,最终找出控制城市交通网络演化的基本动力学

30、规律,为科学地规划道路的通行能力提供理论依据。城市交通网络相关问题的研究在分析交通网络拓扑特性的基础上,可以从复杂网络的角度来考虑OD矩阵估计、交通环境污染的防治以及合理的土地使用、收费政策的制定和运输模式选择等问题。另外,还可以进一步对与城市交通网络密切相关的一些问题,如物流网络、物流分销网络等进行实证研究,以此来带动城市交通网络复杂性问题的理论研究。以上问题只是一个简单的罗列介绍，并不是全部问题所在。这反映了复杂网络理论在城市交通网络研究上的实用性和发展潜力，从侧面表现了复杂网络理论在公交网络系统研究上的优缺点，同时带给了我们巨大的挑战。小结本文在提出问题，分析问题之后，给出了两种公交网络模型，分别为公交停靠长点网络模型和公交换乘网络模型。在这两个模型的基础上，分析了公交网络的小世界特性和无尺度特性，包括小世界网络中的集聚系数和特征路径长度及无尺度网络中的节点的度分布、边的权值分布和点的权值分布，结合武汉市公交网络数据，在公交停靠站点网络模型和公交换乘网络模型上分别验证其是否具有小世界性质，并分析意义及其合理性。复杂网络的理论还在进一步发展,到目前为止,规则网络、随机网络、小世界网络和无标度网络是比较完善、成型的网络模型,但现实中的每一种网络系统都有其自身的特殊性质,它有可能是各种网络