摘要: 按照网络拓扑结构特征划分,我们经常接触到的实际网络有完全规则网络(Completely Regular Networks)、完全随机网络(Completely Random Networks)、小世界网络(Small-world Networks)和无标度网络(Scale-free Networks).系统地对无标度网络的形成、特性和代表性研究成果进行简要总结,重点探讨交通运输网络的复杂性和相关问题,研究了城市公交网络的无标度特性及度分布指数,并以北京市公交网络为例完成了实证分析.进一步从理论上给出了怎样找到公交网络中的枢纽站点这一难题的研究思路、整体框架及求解算法,这是交通运输网络复杂性及其相关问题研究的关键.还分别从理论与应用两个层面给出了下一步研究工作的总体思路,为交通管理部门进行交通运输网络规划、设计、建设和管理提供了科学的研究手段和理论支持.
关键词: 交通运输网络;复杂性;无标度;小世界
0 前 言网络可以用来描述人与人之间的社会关系,物种之间的捕食关系,词与词之间的语义联系,计算机之间的网络联接,网页之间的超链接,科研文章之间的引用关系,以及科学家之间的合作关系,甚至产品的生产与被生产关系.现实网络一般存在四种形态:完全规则网络(Completely RegularNetworks)、完全随机网络(Completely RandomNetworks)、小世界网络(Small-world Networks)和无标度网络(Scale-free Networks).在小世界网络的研究兴起之后,越来越多的科学家投入到复杂网络的研究中去.无标度网络就是其中的一个重要方面.无标度网络指的是网络的度分布符合幂率分布,由于其缺乏一个描述问题的特征尺度而被称为无标度网络.它具有真实网络中最常见的两个特征:增长性(Growth)和偏好依附性(Preferentialattachment).第一个特征表明无标度网络可以不断地扩张.第二个特征则意味着两个节点连接能力的差异可以随着网络的扩张而增大;最初连接较多的节点可以形成更多的连接,即“富者愈富”.无标度网络具有如下三点特性:
(1)小世界网络特性.两点之间最短路径的长度一般远远小于整个网络的大小.最为着名的一个发现是英国社会心理学家Milgram通过观察提出“六度分离”,它是指任意两个人之间的最多连线数不会超过6条.换言之,任意两个不相识的人,经过中间最多不超过6人就可以使这两个人相识.
(2)聚类性.这是指网络包含了许多簇或圈,而在每个簇或圈内有相当高的连线密度,但在簇与簇(圈与圈)之间的连线密度却比较低.
(3)网络弹性.如果去除一个或多个点却导致了点间距离的大幅度增大,那么网络的有效性也就随之降低了.网络弹性是指去除点所能给网络带来的攻击效果. Albert等研究发现,Internet和万维网都具有极高的网络弹性,但却很难对付对网络Hub的蓄意攻击和协同式破坏.掌握了这些特性,可能导致许多领域出现新的应用.例如,电脑科学家可以据此设计出更有效的策略,以保护因特网免受电脑病毒的侵害.
尽管国外已有很多学者对网络复杂性进行了研究,还从实证的角度进行了相关分析,但就交通运输网络而言,相关研究成果还不多见,特别是从无标度和小世界网络特性方面分析的更是少见,而国内,还没有发现这方面的公开报道. Baraba′si和Albert(1999)首先介绍了无标度网络.他们开发了几个大型数据库用来描述大网络的拓扑结构,包括有WWW网络,演员合作网络和科学引用网络等等.此后,国内外许多学者从实证和传播的角度进行了一些研究,包括Internet网、电话网、电力网等等. Goh, Kahng和Kim(2003)研究了数据包在无标度网络中的传输,并且定义每个顶点的负荷量为数据包通过此顶点的累积量(当数据包沿着每一对顶点间最短路发送和接收时). KonstantinKlemm和Victor M. Eguiluz(2002)提出了基于节点具有有限记忆的网络增长模型,此模型体现了真实网络的特性:度分布规律和新连线的线性偏好依附特性.同时研究了无标度网络的高集聚性,表明了节点记忆对于正确描述动态增长网络的影响.
Chen(2004)等在BA模型的基础上对其进行了改进,考虑了所有节点在初始状态下都有初始吸引系数,因此集散点的形成与其初始吸引系数有关.但他们设定所有节点的初始吸引系数都是相同的.Moore和Newman ( 2000a, 2000b )、Pastor-Satorras和Vespignani (2001)、May和Lloyd(2001)等学者分别研究了小世界网络中病毒的传播、Internet网络的病毒传播及病毒在无标度网络中的动态传播模型等问题.迄今为止,对交通运输及相关网络复杂性的研究成果还比较少,较少的研究也主要集中在铁路、航空和地铁网络上. Latora和Marchiori(2002)对波士顿地铁的网络特性进行了初步研究;Sen(2002)等研究了印度铁路网络的Small-world特性;Jiang和Claramunt(2004)对城市街道网络进行了研究,以实例说明了此网络具有Small-world特性. Amaral(2000)等学者研究了航空网络的拓扑结构.而就国内而言,这方面的研究就更为罕见.就检索到的资料来讲,把无标度网络和小世界网络应用到交通运输及相关网络的研究尚无成果.
研究无标度网络,对于防备对交通运输网络遭到协同攻击和破坏、防治交通阻塞、提高网络可靠性等等都具有极其重要的理论和现实意义.无标度网络对意外故障具有惊人的强韧性,这一特性本质上源于这些网络的非同质拓扑结构.被“随机去除”破坏的主要是那些不重要的节点,因为这类节点的数目远大于集散节点.与那些几乎连结所有节点的集散节点相比,那些不重要的节点只拥有少量的连结.因而去除它们不会对网络拓扑结构产生重大的影响.这提高了我们对交通运输网络的科学认识,随机去除某些交通节点并不会造成整个交通网络的瘫痪,但如果我们蓄意对交通Hub进行攻击和破坏,就会迅速导致整个网络瘫痪.目前国外对网络复杂性具有一些研究成果,大部分还处在探索阶段,没有形成十分完善的理论.
1 城市公交网络的无标度特性1.1 城市公交网络构建现实世界中的交通网络都极其复杂,城市公交网络就是一个例子.定义:网络中的节点代表公交线路起终站点,边代表起终(Origin-Destination)站点之间的连线.这样,由许许多多的点和线组成的网络就构成了城市公交网络的基本框架.考虑到公交系统的具体组织和运行,我们可以归结出两种情形来表示O-D对之间的公交线路组织.图1表示从i到j和从j返回到i的线路,而在有些情况下,城市公交线路也有图2的情形,即公交线路的起讫点都为i,构成了公交网络中所指的“环”.为一个由8个公交站点、11条公交线路和1个环构成的简单城市公交网络示例图.
1.2 城市公交网络特性Baraba′si和Bonabeau (2003)通过计算机模拟和计算显示,具有优先连接的特性并且持续成长的网络,确实会发展成无标度网络,并且节点的分布也遵循幂次定律,虽然这个理论模型过于简化,且需要根据具体情况加以调整,但还是对现实世界中无标度网络的普遍存在性提供了解释.
通过直观分析与观察,城市公交网络具有如下两个特性:
(1)增长性.随着城市规模和社会经济活动的发展,新的公交站点不断进入公交网络中,如居民小区的不断出现导致了城市公交网络中公交站点数的持续增长.当然,其中也有部分公交站点由于其功能不再适应社会经济活动的发展和出行需求的变化,而被删除.根据北京统计局及北京公交网的有关数据资料,1949年北京的公交线路为11条,而2002年,北京的公交线路已经达到776条.这表明城市公交网络的发展是一个动态增长的过程.
(2)偏好依附性.在城市公交网络中一定存在几个大的公交站点,我们称之为“公交枢纽点”.这些枢纽点在城市公交网络中起着至关重要的作用,由于其吸引力要比其它节点大,所以新加入到网络中的节点更容易与之连接,这就是我们通常所说的“富者愈富”的思想.这种偏好依附性导致城市公交网络中有少数几个站点拥有大量的公交线路,而其它大量的公交站点却只拥有为数不多的少数几条公交线路.
根据Baraba′si和Bonabeau的理论,由于公交网络具有如上特性,它一定最终会演化成无标度网络.这只是理论上的结果,我们还需要从实证角度对此进行验证.
1.3 数据分析及结果下面以北京市公交网络为例,图4为北京市公交网络的拓扑示意图.北京市公交枢纽站及其公交线路数公交枢纽公交线路数公交枢纽公交线路数东直门32北京站36西直门13颐和园19动物园15前门15北京西站34四惠15然后,我们对北京市公交网络的拓扑特性进行了分析,图5表示了公交网络的连线数与累积概率之间的关系,而图6为其双对数图.
双对数图基本呈线性关系,表明公交网络是无标度网络.进一步的研究表明,北京市公交网络的度分布指数为2.24(Wu et al., 2004a).由于我们论证了北京的公交网络是无标度网络,从而也在一定程度上从理论上解释了为什么2004年7月11日突降大雨而导致北京交通陷于瘫痪.
2 拟解决的关键问题上述研究成果已经发表在Modern PhysicsLetters B上,既然公交网络为无标度网络,那么我们如何可以从理论上找到公交网络的集散点(枢纽)呢?如何将这种理论研究工作与实践性很强的公交网络平衡配流研究相结合是我们的研究方向之一.目前对于如何找到Hub点是国内外学者研究的一个难点和重要课题.如果可以应用公交网络平衡配流的思想找到公交网络的集散点,那么我们就可以对一个现实的交通网络应用无标度网络的理论进行网络规划、设计、建设及管理.基于这种研究思想,我们展开了相关研究,提出如下初步解决方案.
(1)应用公交网络用户平衡配流的方法确定公交网络中各条路段的流量;(2)应用极大熵模型求解平衡网络,得到唯一的路径流量;(3)利用已求得的路径流量从而可以得到网络中每个站点的流量;(4)根据流量的大小对站点进行排序;(5)计算各站点流量所占总流量的百分比;(6)找到公交网络中的Hub点.
上述执行用户平衡配流的公交网络是包含所有能够上下乘客的节点的网络,事先不知道哪些节点是Hub点.如果考虑城市交通拥挤是由多种交通工具共同表现出来和出行需求可以在多种交通工具之间转换的事实,这个网络还可以是与私家车道路网络组合而成的超级网络,从而需要研究超级网络上的混合均衡配流模型,由这个模型得到的公交站点进出流量就更加接近实际流量.对于能力约束问题,有两种处理办法:
(1)在不考虑能力限制的情况下,可以根据公交站点流量的百分比得到公交网络中的Hub点(原理:少数几个站点占有85%～90%的总流量),当然根据公交模型及具体城市的拥堵状况,此百分比应适当变化.
(2)在考虑能力限制时,可以利用第4步中得到的站点流量排序结果,依次删除站点,重新构建公交网络,然后再进行用户平衡配流,直到当去除某站点时,系统中90%的流量无法进行分配,从而得到公交网络中的Hub点.这也是目前为止,我们所知的唯一可以用定量分析的方法来确定交通中的Hub点的方法.
3 进一步的研究方向及初步研究成果无标度网络为我们研究交通运输网络的复杂性提供了新的思路.而且通过对交通运输网络的演化机制的研究,有可能给出促进交通科学与技术发展的新的方案与模式.在进行交通运输网络改造或规划过程中,管理部门要充分考虑到网络的增长机制及网络的拓扑特性,做到既不损害出行者的利益,又兼顾决策者的整体利益.
(1)既有交通运输网络的改扩建是一项非常复杂的系统工程,如何把有限的资金应用到最利于解决问题的根本之处不容忽视.也就是我们通常讲到的交通网络设计问题.如通过我们对公交网络的无标度特性研究,进一步又可找到公交网络中的Hub点,那么就可以考虑资金分配的问题(改扩建或新建),公交网络弹性问题等等,进而延伸到公交交通运输系统工程与信息2005年4月网络的各种性能指标的设计问题(如拥堵、环境、能耗、收费等等)中去.
(2)对现有网络增长机制进一步深入研究,构造考虑效用的交通网络增长非线性偏好依附模型,以便较好地描述从规则网络到无标度网络、小世界网络以及完全随机网络的整个网络增长模式.在此基础上,针对以往对于波士顿地下铁路网及印度铁路网的实证结果给以理论上的支持,从网络增长机制上对此类网络进行更为恰当的描述(Wu et al.2004b),为我国特大型城市发展地下铁路网提供决策上的支持.这方面的研究我们也取得了初步的成果,结果可见图7.
(3)交通阻塞已经成为当今城市交通的通病,也是令交通管理部门最为头疼的问题.在实际的交通出行中,阻塞在交通网络中向相邻的路段和节点进行传播,这类似于病毒在复杂网络中的传播,在对交通网络拓扑特性进行系统分析的基础上,应用SIR或SEIR模型进行模拟(Wu, Gao and Sun,2004),进而对阻塞的传播进行有效的控制.对此类问题的初步研究结果如图8所示.
(4)交通运输网络可靠性问题.可以预言,通过对交通运输网络复杂性的深入探讨,将对交通运输网络可靠性的研究产生不可估量的影响.
(5)复杂网络结构稳定性问题.对现有复杂网络的结构进行稳定性分析,找到其网络结构发生变化的阈值,进一步描述复杂网络形成的机理.
(6)进一步考虑具有主观选择的时变随机选择和无标度偏好依附混合模型的网络增长机制,导出其度分布函数,并针对不同的参数取值进行模拟研究(Wu et al., 2004c).此方向的研究也具有了初步成果,可见图9.
(7)其它相关交通运输网络问题的研究.如从复杂性网络角度来考虑O-D矩阵估计、交通环境污染的防治以及合理的土地使用、收费政策的制定和运输模式选择等问题.另外,可以进一步对与交通运输网络密切相关的一些问题,如物流网络、物流分销网络等进行实证研究,以此来带动交通运输网络复杂性的理论研究.
4 结论交通运输网络是一个复杂巨系统.本文从网络复杂性理论出发,构建了城市公交网络的拓扑图,对其无标度网络特性进行分析,并以北京市公交网络为例进行了验证.另外,本文提出了如何找到无标度网络中的集交通运输网络复杂性及其相关问题的研究散节点这一拟解决关键问题的研究思路和整体框架.
最后从理论和应用的角度给出了进一步研究工作的思路.通过对交通运输网络的演化机制的研究,有可能给出促进交通科学与技术发展的新的方案与模式.
参考文献[ 1 ] Amaral L A N. Scala A, Barthe′lemy M, StanleyH. E. Proc. Natl. Acad. Sci. (USA), 2000,97:
11149.
[ 2 ] Baraba′si A-L, Albert R. Emergence of scaling inrandom networks[J]. Science, 1999,286: 509.
[ 3 ] Baraba′si A-L, Bonabeau E. Scale-free networks[J]. Scientific American, 5 (2003) 60.
[ 4 ] Qinghua Chen, Dinghua Shi. The modeling ofscale-free networks [J]. Physica A, 2004, 335:
240.
[ 5 ] Goh K -I, Kahng B, Kim D. Packet transport andload distribution in scale-free network models[J].
Physica A, 2003, 318:72.
[ 6 ] Bin Jiang, Christophe Claramunt. Topologicalanalysis of urban street networks[J]. Environmentand Planning B, 2004,31: 151.
[ 7 ] Konstantin Klemm, Victor M Eguiluz. Highlyclustered scale-free networks[J]. Physical reviewE, 2002, 65:036123.
[ 8 ] Vito Latora, Massimo Marchiori. Is the Bostonsubway a small-world network? [J]. Physica A,2002, 314:109.
[ 9 ] May R M, Lloyd A L. Infection dynamics on scalefree networks [J]. Phys. Rev. E, 2001, 64:
066112.