基于結構熵的交通網絡特性研究城市群交通網絡特性

基于結構熵的交通網絡特性研究城市群交通網絡特性

1交通網絡特性研究人員認為，小世界的性質和無標度特征是許多實際網絡的共同特征。Watts和Strogtz于1998年在Nature上發(fā)表的一篇文章中引入一個比規(guī)則網絡和隨機網絡更接近現實的網絡——小世界網絡模型,也稱為WS小世界模型。小世界網絡的主要特性是較高的聚集系數和較小的平均最短距離。1999年,Barabási和Albert提出無標度網絡模型,簡稱BA模型,指出許多實際網絡的度分布具有某種冪指數的形式。無標度網絡的一個重要特征是絕大部分節(jié)點連通度較小,只有極少數節(jié)點具有較大連通度。在Watts和Strogatz、Barabási和Albert分別對復雜網絡的小世界現象和無標度特征進行研究之后,人們對大量不同領域的實際網絡的拓撲特征進行了實證研究。如演員網絡、萬維網、科學家合作網和新陳代謝網絡等。目前,將交通運輸網絡抽象為復雜網絡,利用復雜網絡理論深入研究系統(tǒng)分析交通運輸網絡的各種特性,得到了越來越廣泛的關注。WuJianjun和GaoZiyou等通過構建O-D網絡分析了北京市公交網絡的無標度及小世界特性。JulianSienkiewicz等研究了波蘭21個城市的公交系統(tǒng),采用兩種網絡模型對其進行分析。XuXinping等在L-空間和P-空間中給出了中國北京、上海、南京的公共汽車運輸網絡的統(tǒng)計性質。李英、周偉等以上海市的公共汽車交通系統(tǒng)中的?？空军c網絡為研究對象,計算了網絡的度分布、平均路徑長度、聚集系數等指標,表明上海市公共交通網絡是一個無標度復雜網絡。VitoLatora等研究了波士頓的地鐵網絡特性。KatherineA.Seaton等計算了Boston和Vienna兩個城市鐵路線路網絡的拓撲特征,并將該結果與相應的隨機二部圖的理論預測結果進行比較。Angeloudis和Fisk對世界地鐵網絡復雜性進行了研究。在中國城市群經濟社會快速發(fā)展的大背景下,長株潭城市群提出長沙、株洲、湘潭三市交通網絡同城化的建設目標,這對交通運輸發(fā)展提出了新的要求和挑戰(zhàn),使得全局研究城市群交通運輸網絡刻不容緩。為了切實從全局角度把握長株潭城市群域交通網絡的連通水平、網絡結構的合理有序性、網絡整體性能等,本文利用復雜網絡理論研究該群域交通網絡性質,以便對長株潭城市群交通運輸網絡規(guī)劃建設諸如中心城市內或城際間道路、樞紐的新建等提供理論支持。在對各中心城市交通網絡進行特性分析的基礎上,研究城市群交通網絡的特征如網絡特征路徑長度、道路的n階平均度、道路的n-聚集系數、網絡平均n-聚集系數、網絡失效彈性;定義并分析度為k的道路的介數中心性,定義并計算了一種基于介數中心性的結構熵。分析發(fā)現長株潭城市群交通網絡是小世界網絡,但不是具有無標度性。分析長株潭交通網絡的匹配關系,指出其異配性,并利用交通網絡的異配性探討城市群交通網絡的層階性。2復雜網絡拓撲的性質2.1交通網絡的復雜映射以城市群道路網絡為研究對象,采用對偶方法,將道路(而非路段)映射為網絡的節(jié)點,將道路間的交叉口映射為網絡的邊,構建交通網絡的復雜拓撲網絡。將該由道路網絡映射所得到的交通復雜網絡用無向無權圖表示為G=(V,E),其中,V是頂點集且|V|=N,E={(i,j):i,j∈V,i≠j}是邊集且|E|=M.圖所對應的鄰接矩陣表示為A=(aij)∈{0,1}N×N.2.2交通網絡節(jié)點的n階度dij:交通網絡中兩個節(jié)點i,j∈V之間的距離;ˉL:交通網絡的平均路徑長度;ˉLrand:隨機網絡的平均最短路長;N(n)(i):節(jié)點i∈V的n階鄰居集合,即N(n)(i)={j∈V:(i,i1),…,(in-1,j)∈E},n=1時N(n)(i)為通常的節(jié)點i的最近鄰居集合N(i);k(n):節(jié)點的n階度,n=1時為通常的節(jié)點度k,節(jié)點i∈V的n階度k(n)i=|N(n)(i)|,n=1時ki=|Ν(i)|=∑j∈Ν(i)aij;<k(n)>:交通網絡節(jié)點的n階平均度,n=1時為通常意義下的節(jié)點平均度<k>;n(k):度為k的節(jié)點數;P(k):網絡中任意一個節(jié)點度為k的概率;p(k):節(jié)點累積度分布概率,即p(k)∶=p{x≥k};C(n)i:節(jié)點i∈V的n-聚集系數,n=1時C(n)i為通常意義下節(jié)點i的聚集系數Ci;C(n)(k(n)):度為k(n)的節(jié)點的n-聚集系數,n=1時C(n)(k(n))為通常意義下度為k的節(jié)點i的聚集系數C(k);h:C與Crand的比值,即C/Crand;ˉC(n):交通網絡的平均n-聚集系數,n=1時ˉC(n)為通常的平均聚集系數ˉC;C:交通網絡的聚集系數;Crand:隨機網絡的聚集系數;PR:交通網絡的Pearson相關系數。注:除PR外所有數量值都是必然非負的。2.3網絡指標(1)平均最短路徑長度ˉL=∑i≥jdij(Ν2)(1)對于交通網絡G,平均最短路徑長度可以用廣度優(yōu)先搜索算法(BFS)來確定,時間復雜度為O(MN)。交通網絡的特征路徑長度表示連接網絡中任意兩條道路之間最短關系鏈中的道路條數。(2)nin節(jié)點平均n階度<k(n)>=∑i∈Vk(n)iΝ?n=1時<k>=∑i∈VkiΝ=2ΜΝ。節(jié)點平均n階度越大,則與該節(jié)點所代表的道路相連接的n階鄰居道路越多。(3)交通網絡中各道路聚集系數比聚集系數描述交通網絡中節(jié)點(對應于道路)的聚集情況,平均聚集系數則反映了整個交通網絡中道路的密集程度。平均聚集系數越大,道路密度越大。節(jié)點i-聚集系數的cniCi=節(jié)點之間實際存在的邊數總的可能邊數計算聚集系數的時間復雜度為O(M2N)。對n>1的情況,節(jié)點i的n-聚集系數C(n)i只需針對i的n階鄰居修改Ci計算公式即可得到,C(n)i描述了第i條道路的n階鄰居之間相互連接的程度。C(n)i∈,?n≥1。道路間存在邊的概率ˉC=∑kΡ(k)C(k)(2)其中,C(k)是度為k的道路的平均聚集系數,即度為k的道路其鄰居道路之間存在邊的概率。若平均聚集系數的計算公式中C(k)替換為C(n)(k(n)),n>1,則可得平均n-聚集系數ˉC(n),這里,C(n)(k(n))由n階度和n階度為k(n)的道路的鄰居之間存在的平均連接數得到。網絡聚集系數的定義C=∑kk(k-1)Ρ(k)C(k)(3)(4)網絡性能最短路徑鏈表定義度為k的道路的介數中心性BC(k)為BC(k)=∑i:ki=kBC(i)n(k)(4)BCi=∑s,t∈V,s≠tnspst(i)nspst(5)其中,BC(i)為交通網絡中節(jié)點i的介數中心性,nspst、nspst(i)分別為以s、t為始點和終點的全部最短路徑數目和這些最短路徑中過節(jié)點i∈V的數目。在交通網絡的節(jié)點類中定義一個鏈表,每個循環(huán)體計算O(N)次得到一條最短路徑鏈表,這樣通過對Dijkstra算法的改進可在O(N2)時間內找到nspst、nspst(i)的數值,同時獲得最短路徑序列。提出基于節(jié)點介數中心性來定義結構熵如下式,這樣定義的結構熵能反應交通網絡朝有序狀況。E(G)=-∑i∈VBC(i)lnBC(i)(6)為“p”的網絡失效彈性κ=m2kmk(7)其中,κ為網絡失效彈性參數,mk,m2k分別是P(k)的一階矩和二階矩,可用κ檢驗網絡失效彈性。κ的閾值為2,當κ值接近2時意味著網絡對失效的脆弱性,即一小部分的節(jié)點癱瘓將使網絡陷入多個不相連接的小群體。κ大于2則意味著較強的失效彈性。(5)網絡是異配網絡的匹配關系描述了網絡中度大的節(jié)點和度小的節(jié)點之間的關系。若度大的節(jié)點傾向于和度大的節(jié)點相連,則網絡是同配的;反之,若度大的節(jié)點傾向于和度小的節(jié)點連接,則網絡是異配的。已有研究表明許多社會網絡如人際關系網絡是同配的,而大部分生物網絡、技術網絡則是異配的。Newman指出計算邊的兩端節(jié)點的度的Pearson相關系數PR可以描述網絡的匹配關系。ΡR=Μ-1∑iki1ki2-[Μ-1∑i12(ki1+ki2)]2Μ-1∑i12(k2i1+k2i2)-[Μ-1∑i12(ki1+ki2)]2(8)其中,i=(i1,i2)∈E,ki1,ki2表示i1,i2的度。0≤|PR|≤1。當PR<0時,網絡是異配的;當PR>0時,網絡是同配的。3對城市群交通網絡特征的研究3.1cztuatn仿真選取長株潭城市群(CZTUA)的中心城市長沙市(CS)、株洲市(ZZ)和湘潭市(XT)以及城市群區(qū)域的主干公路和城市道路所構成的交通網絡作為研究對象,研究其復雜網絡拓撲性質。其中,CZTUATN1是一個非常簡化的網絡,只有41條道路,而CZTUATN2是一個相對較完整的網絡,有132條道路,涵蓋了城市群中現有的全部主要城際道路、城市主干道路和絕大多數城市主要街道。這種規(guī)模的交通網絡已足以用來研究其所具有的特性。利用VC++6.0連接Matlab7.0作為仿真工具,可以方便地進行仿真。為了便于比較,取與交通網絡具有相同節(jié)點數和連通度的隨機網絡,并計算其平均路長Lˉrand=lnΝ/ln<k>和平均聚集系數Crand=<k>/N。計算三中心城市和長株潭城市群交通網絡拓撲和相關指標,見表1、圖1至圖6。3.2交通網絡的無標度性根據3.1節(jié)結果,對網絡特性作如下分析。(1)三個中心城市交通網絡和城市群的兩個不同規(guī)模交通網絡都具有較短的平均最短路長,中心城市的平均最短路長不超過2.5,以長沙市的平均最短路長最短,而長株潭城市群交通網絡的平均最短路長不超過3.5;五個網絡都具有較大的聚集系數,尤其是CZTUATN2的聚集系數很高。因此,長沙、株洲、湘潭三個中心城市和長株潭城市群的交通網絡是小世界網絡。(2)五個網絡的失效彈性系數呈現和網絡聚集系數相似的規(guī)律,即以CZTUATN2的失效彈性最大,最為魯棒,CZTUATN1也較大,這說明整個長株潭交通網苗是比較抗失效的。四個網絡中只有XTTN顯示出對失效的脆弱性。(3)對長株潭城市群的五個交通網絡計算了介數中心性,這里以CSTN的介數中心性圖為例(圖1)揭示BC(k)與k的關系。由圖知,道路介數中心性與道路的聯通度是緊密相依的,道路的度越大,介數中心性越大,道路在交通網絡所處的地位越重要。(4)由各交通網絡結構熵的計算,依據E(G)/N可在一定程度上判斷并比較各網絡的有序性,CZTUATN2和CSTN的值最小,故二者具有相對而言更有序。(5)五個交通網絡的節(jié)點平均度都較大,二階平均度很大,這說明各個中心城市和城市群的交通網絡具有較好的連通性。(6)網絡CZTUATN2的高聚集性表明網絡在局部可能包含各種由高度連接的節(jié)點構成的子圖。事實上,長株潭城市群交通網絡是由三個發(fā)展相對獨立的中心城市交通網絡共同構成,自然包含了局部子圖。(7)以長沙、株洲、湘潭三個城市交通網絡的局部聚集系數為例,ZZTN的局部聚集系數明顯高于CSTN和XTTN,并且XTTN的局部聚集系數為零的相對較多,這說明ZZTN道路的鄰居道路之間比CSTN和XTTN中道路的鄰居道路之間具有更好的連通性。以CSTN道路的1、2-聚集系數的散點圖為例,研究發(fā)現,許多聚集系數為0的道路,其2-聚集系數卻不為0,若將其按大小順序排列作圖,則會得到更連續(xù)的圖,因此2-聚集系數能更好地辨識道路之間的聚集程度。(8)除了ZZTN,其他四個網絡的平均2-聚集系數都比平均聚集系數大許多,即這些網絡中道路的2-鄰居之間相對于道路的最近鄰居之間的連通度有較大變化和改善。網絡ZZTN的平均聚集系數相對其它網絡而言已經較大,其平均2-聚集系數沒有較大增加,這反映了該網絡中道路的2-鄰居之間連通性與道路的最近鄰居之間連通性差不多,已無多少改善,該網絡中道路間相互連接的程度較高。(9)由道路度k與該度相應道路數n(k)的關系可以清晰地看出,網絡中只有少數道路連通度比較大,絕大多數道路連通度較小;這顯示長株潭城市群的五個交通網絡都具有無標度網絡的特征。關于這些交通網絡的無標度性,將在3.3節(jié)中詳細給予論述。(10)中心城市的三個交通網絡和城市群兩個交通網絡的Pearson相關系數均為負,說明網絡是異配的,即網絡中度較大的道路傾向于和度較小的道路連接。三個中心城市交通網絡比城市群交通網絡具有更強的異配性。3.3節(jié)點累積度散點圖擬合現實中很多無標度復雜網絡的冪律指數不盡相同,許多自然和人工網絡的實際網絡常常具有一些非冪律特征,如指數截斷、小變量飽和等。下面對長株潭城市群交通網絡的研究表明網絡不具有冪律特征。作各中心城市及城市群的交通網絡節(jié)點累積度分布的loglog散點圖(圖2至圖6),并對這些(log(k),log(p(k)))散點圖分別進行擬合,得到五條擬合曲線,相應方程為(方程中x,y分別表示log(k),log(p(k)))y=-1.56x2+0.9012x-0.4645e-1y=-0.6780x3-0.1529x2+0.0528x+0.0283y=-1.2010x2+0.0561x+0.1714y=-1.0014x2.9981+0.0315y=-1.2380x2+0.6411x-0.0250這些方程都很好地擬合了散點分布圖。由此可知長沙市、株洲市和湘潭市三中心城市交通網絡及長株潭城市群交通網絡都不具有無標度性,因此,這些網絡不是無標度網絡。3.4道路連通度的計算由3.2節(jié)中分析我們已經明確五個交通網絡均具有異配性,且三個中心城市交通網絡的異配性較強,城市群交通網絡具有異配性,其異配性相對中心城市交通網絡的異配性弱些。五個交通網絡的異配性或許暗示了這些網絡可能具有層階性,下面作初步探討。現以交通網絡CZTUATN2為例,結合道路度與其相應道路數的關系,進一步探討網絡的匹配關系。道路連通度k∈I1∶={k∈Z+|k>30}的有G107、G320等2條國道;道路連通度k∈I2∶={k∈Z+|20≤k≤30}的有長沙市二環(huán)、株洲市環(huán)路、長沙市三環(huán)、湘潭市二環(huán)、G319、長沙市芙蓉路等6條中心城市環(huán)路和城市主軸道路;道路連通度k∈I3∶={k∈Z+|14≤k<20}的有G030、株洲市建設路、湘潭市建設路、紅旗路、湘江路和長沙市韶山路等6條道路;道路的連通度k∈I4∶={k∈Z+|11≤k≤13}的有長江路、株洲市人民路、新華路、G065、S211、勞動路、五一大道、湘府路、湘潭市韶山路、黃興路、長沙人民路、萬家麗路、湘潭市絲綢路等13條道路;k∈I5∶={k∈Z+|5≤k<11}的有曙光路、木蓮路、河