基于复杂网络的城市路网可靠性研究

基于复杂网络的城市路网可靠性研究

大规模城市路网的研究城市路网不仅受到山坡、洪水等自然灾害的破坏，而且受到人类恶意攻击和交通堵塞的影响。这导致了部分网络损坏。网络损坏增加了其他网络的负荷，使网络超载，损害了其交通功能。以这种方式，失效会传导至整个网络，导致更多的破坏，造成路网交通运输能力和效率明显降低。然而城市路网作为生命线网络在灾难后所表现的性能极为复杂，因为它不仅仅和路网的供给下降相关，而且其必须满足各类OD需求、行程时间和路径长度的约束要求，而这些要求又和城市路网本身拓扑性质密切相关。因此要缓解城市路网受到自然灾害和交通堵塞的影响，必须深刻认识路网拓扑性质的变化规律，深化城市路网鲁棒性和可靠性的研究，在此基础上对路网进行控制与管理。然而由于图论研究方法滞后，数理统计计算量太大，使得研究的路网规模较小、结构简单，一般仅仅几个节点，难以抓住路网拓扑性质、鲁棒性和可靠性的变化规律。图论研究的新进展为研究大规模城市路网带来了契机。上世纪90年代以前几个世纪的图论研究局限于几百个顶点以下的图，研究方法是传统的看图分析方法以及矩阵计算方法。1998年以后图论，复杂网络的研究进入了新阶段，Watts、Strogatz和Barabási、Albert两个研究小组在98、99年分别在Nature、Science杂志上发表文章引入了小世界(Small-World)网络模型和无尺度(Scale-Free)网络。以此为标志，人们利用计算机研究具有大量（通常是几千、几万以上）顶点和连边构成的大规模网络的统计性质，这种趋势已经影响到各个学科研究，如生命科学领域的各种网络（如细胞网络、蛋白质作用网络、神经网络）、Internet/WWW网络，流行性疾病的传播网络，等等。首先判断城市路网究竟是小世界网络还是无尺度网络，然后考虑研究城市路网遭受恶意破坏模型或随机失效模型，为预防城市交通网络遭受恶意破坏、随机失效进而瘫痪提供科学的预防政策，并进一步的探索路网局部失效或破坏后的救援方案，以最大程度地减小路网失效带来的损失。1节点度参数的描述对城市路网而言，每一步的发展都是经过规划的，但是规划取决的因素很多，考虑的各个因素的侧重点也不一样，以至于看不出建设的网络有什么简单的、确定的法则，这样的网络具有随机的成分。然而正是由于其网络节点数十分巨大，可能有成千上万，从而使得大规模性的路网仍然具有统计特性。为计算方便引入一个邻接矩阵来表示连接的、无方向的、无权值的网络：复杂网络具有很多与规则网络和随机网络不同的统计特征，其中最重要的是小世界效应（small-worldeffect）和无标度特性（scale-freeproperty）。描述这些特征的参数有：网络平均路径距离（Averagepathlength）：所有节点间的最短路所包含的边数平均值。比较著名的例子就是“六度分离”原则。网络簇系数（Clusteringcoefficient）：节点簇系数是它所有相邻节点之间连边数占最大可能连边数的比例，网络簇系数C则是所有节点簇系数的平均值，即这里，li是和顶点vi直接连接的顶点之间的连接边数，mi为直接连接的顶点数。专门用来衡量网络节点聚类成团的程度。其计算方法如图1所示：顶点i直接连接的顶点数量为4，而4个顶点间存在的边数为4，则节点i的簇系数为节点度分布(DegreeDistribution)：根据文献，把含有k个连接度的节点数总和占所有节点的比例，即n(k)含有k个连接的节点数量，N为整个网络的节点数。而节点度是指一个节点拥有相邻节点的数目。在许多实际的网络中，可能大部分节点只有少数几个连边，而少数节点却拥有大量的连边，该参数正是为了描述这样的特征。简言之，综合大的簇系数和小的平均距离两个统计特征的效应的网络就是小世界网络。而无尺度网络的特点是：节点度服从幂律分布，就是说具有某个特定节点度的节点数目与该特定的度之间的关系，可以用一个幂函数近似地表示：p(k)=αk-γ，这里，k为节点度，α为常数，γ为度分布指数。很显然，无尺度网络绝大多数节点和其他节点连接较少，而少数节点拥有很多的连接。2城市路网的映射路网的基本组成元件包括交叉口、路段两类。首先在区分道路的等级与车道数的基础上，重新定义道路的起讫点，为了不失一般性，一条道路按照如下规则进行界定，一条路分为2条或者以上的时候（例如xxx市路网中的长江东路、长江西路），按照车道数是否相同区分为是否是多条道路，若相同则定义为一条路，否则，则反之；然后将道路映射为网络中的节点，将交叉口映射为节点间的连边，那么整个现实中的道路网就被抽象、简化为一张普遍意义上的“复杂网络”，这样映射出的复杂网络反映了高度抽象的道路间的相互联结关系，而不反映纯粹地理意义上的联结。其目的也就是探究交通网络经过映射后所表现出的新网络特性。在现实世界中，具有类似映射关系的网络系统很多，比如WWW中网页链接关系、论文引用关系等。以合肥市包河区路网为例，包河区是一个相对封闭的路网，如图2所示，包括6条主干道、1条次干道，28条支路，共计35条。按照上述的映射规则，将包河区路网映射为如图3反映的道路拓扑关系的网络。受篇幅限制，表1仅列出了其中的8条道路的3个特性指标。根据统计结果，23条道路的相交道路数在1～5之间，仅仅有3条道路在10条以上，大部分道路的相交道路很少。其次，道路的相交道路越多，其最短路径就越短，反之，相交的道路越少，其最短距离也就越大。此外对簇系数而言，大部分道路的簇系数为零，簇系数越大，簇系内部的通达性也越好，换句话说对短距离交通越有利。将上述的映射关系推广到如图4所示合肥市市区路网，其映射后如图5所示。通过映射更大规模的城市路网，揭示路网的拓扑网络特征，判断路网是小世界网络或者是无尺度网络，为进一步研究城市交通路网控制和设计提供参考。首先要确定的是城市路网究竟具备哪种网络特征。表2列举了世界上部分城市路网的平均节点度、网络的平均距离L以及簇系数C。首先，根据表2的统计结果，这几个城市的道路之间的平均“距离（交叉口数）”小于7，换句话说，在城市道路网络上，城市道路之间仅仅隔着几个交叉口。此外，合肥、耶乌勒、慕尼黑和威尼斯四个城市的簇系数簇系数较小，因此这两个指标表明城市路网是小世界网络。其次需要判断路网是否具有无尺度网络特征，图6是该市路网的道路节点度和对应节点度的累积概率之间的关系，而图7表示该市道路节点度和对应的累积概率间的双对数关系，两者基本呈线性关系，这表明合肥市的路网是一个无尺度网络，其分布指数为1.547。综上所述，合肥市的路网既是一个小世界网络，又是一个无尺度网络。3城市路网的道路失效仿真人们对城市路网的依赖程度日益提高，凸现了一个广受关注的问题：在受到自然灾害、恐怖袭击、交通堵塞等袭击的情况下，城市路网到底有多可靠？在给出路网相关的拓扑指标，利用这些指标对路网网络属性判断后，接下来要探索的是城市路网的可靠性。而网络可靠性不但和网络顶点、连边数多少相关，也和网络拓扑结构密切相关。例如无尺度网络拓扑就可以承受意外的故障，但面对协同式攻击却很脆弱:5-10%的关键集散节点失效会导致系统彻底崩溃，而随机攻击高达80%的节点，系统仍然强韧的继续工作。那么城市路网在道路失效或者受到攻击的情况下，其拓扑结构是否也扮演类似的角色呢？城市路网中的道路失效或者受到攻击的情况下，路网的可靠性和鲁棒性的主要表现就是在网络平均距离的变化、以及仍然依附在剩余路网上的道路数量。根据城市道路的失效地点的重要性以及失效顺序，城市网络的道路失效形式可以分为如表3的两种情形。对城市路网的映射网络而言，其节点的失效意味着该条道路上所有的交叉口都同时失效，或者说整条道路都失效了。实际上更为可能的是道路上的交叉口一个、或几个交叉口失效。因此，本文在对路网失效仿真时，在城市路网的映射网络上选择如图8所示的交叉口的失效方式。城市路网的道路失效后，无论在紧急救援情况下还是在正常通勤条件下，无论是救援车辆还是社会普通车辆，人们希望用最短的时间到达出事地点，以及能否到达目的地。因此对交通影响较大的主要是最大的路网平均距离以及路网的规模，图8所示，原先A、B节点间的最短距离在连边断裂后，也就是交叉口失效后，其最短距离从原先的2变成12。与此同时，网络分裂为4个孤立碎片。下面对上述随机断裂方式和蓄意攻击方式进行仿真。3.1节点间连边的仿真算法路网道路蓄意攻击失效的思想如下：首先选择路网复杂网络中的节点度最大的两个节点间的连边进行断裂，统计网络的规模以及网络路径距离。再次计算各个节点的节点度，再次选择节点度最大的两个节点间的连接断裂，统计网络的规模以及网络路径距离。如此反复直到网络上所有的节点间的连边全部断裂。其仿真的算法步骤如下：1)初始化网络的路径距离，L=l0,l0的计算方法参见步骤4)，网络规模为S(0)=N;2)计算相交道路的节点度的乘积，即其中3)构造矩阵D=(dij)N×N,(i,j=1,2,…,N)，设dkn=max(max(D))，则令M中的元素mkn=0,mnk=0，从而生成新的权矩阵M(t),(t=1,2,…)；若dij=0，停止；4)利用Floyd最短路径算法，计算新网络的最短距离；其中(b)输入权矩阵其中就是i,j间最短距离；(d)网络的连边在断裂后，统计剩余最大一簇网络中含有的节点数量，也就是网络的规模。具体计算方法是：在矩阵Rs中划去整行或者整列均为∞的元素，剩余的行数即为剩余网络的节点数量，记为S(t);(e)在矩阵Rs中划去整行或者整列均为∞的元素后，计算网络的平均距离lt，其中5)回到步骤2);3.2蓄攻击的初始网络模型路网道路随机失效仿真则相对比较简单：首先随机选择网络权矩阵的元素，假设其选择的元素为mkn，令mkn=0,mnk=0，统计网络的规模以及网络路径距离。如此反复，直到网络上所有的节点间的连边全部断裂。为了更加直观的表示网络的规模、平均距离随着连边失效数量的变化的趋势，图9、图10中的坐标刻度均采用相对值，横坐标均采用相对失效的网络连接数，即已经失效的连边数量占初始网络连边的比例大小，图9、图10纵坐标分布对应于初始网络的最短距离、网络规模相对值。从图9可以看到，和城市路网在随机失效的情况相比，在蓄意攻击同样数量的路口情况下，其网络的平均距离增加的更快。由于网络的运输效率和网络的平均距离成反比例关系，换句话说，蓄意攻击使路网运输效率降低更快，其影响程度是随机失效的1～3倍左右。另外在蓄意攻击的初始阶段，网络平均距离随着攻击路口的增加而增加，到顶点后，迅速降低，其原因在于网络分裂成多块碎片，造成网络本身的规模缩小，引起网络平均距离的减小，网络最后崩溃，网络平均距离也就为0。从图10可以看到，在蓄意攻击的情况下，路网规模和受攻击交叉口的数量基本呈线性递减关系，在蓄意攻击达到50%的情况下，路网规模只有初始的一半以下，此时路网已经处在崩溃的临界点；而随机失效同样在达到50%的情况下，路网仍然在接近完好，之后才开始逐步减小。综上所述，无尺度路网对意外的道路失效具有惊人的强韧性，这一特性本质上正是源于该类型路网的拓扑结构。其实质在于，随机去除的方式所破坏的主要是那些不重要的路口，因为它们的数目远大于关键性道路的重要路口。与那些几乎连结关键道路的交叉口相此，那些不重要的节点只拥有少量的连结。因而去除它们不会对网络拓扑结构产生重大的影响。但是，对集散节点的依赖，也带来了一个严重问题：面对蓄意攻击时，路网不堪一击。通过上面的仿真，只要去除少数主要集散节点，就可导致路网溃散。4城市路网可靠性仿真本文将复杂网络理论应用到城市路网，分析城市路网的复杂网络性质和可靠性。首先，本文通过在路网中引进了无尺度特征、节点度指数以及簇系数等概念，重点研