羅海秀,趙海興,肖玉芝,冶忠林,馬海瑛,李發(fā)旭
1. 青海師范大學(xué) 計算機學(xué)院,西寧 810016; 2. 青海省藏文信息處理與機器翻譯重點實驗室,西寧 810008;3. 藏文信息處理教育部重點實驗室,西寧 810008
現(xiàn)實社會中存在著大量復(fù)雜交錯的網(wǎng)絡(luò)結(jié)構(gòu),如科研合作網(wǎng)絡(luò)、 電力資源分配網(wǎng)絡(luò)、 交通運輸網(wǎng)絡(luò)、 社會融合網(wǎng)絡(luò)等.20世紀(jì)末,Watts[1]和Barabasi[2]提出的小世界網(wǎng)絡(luò)模型和無標(biāo)度網(wǎng)絡(luò)模型在學(xué)術(shù)界掀起了復(fù)雜網(wǎng)絡(luò)的研究熱潮.隨著網(wǎng)絡(luò)規(guī)模的復(fù)雜化和結(jié)構(gòu)的多樣化,研究者們發(fā)現(xiàn)基于普通圖的復(fù)雜網(wǎng)絡(luò)中節(jié)點只能描述相鄰節(jié)點或邊的連接關(guān)系,并不能同時體現(xiàn)出節(jié)點和邊的依賴關(guān)系,也無法通過復(fù)雜網(wǎng)絡(luò)模型精準(zhǔn)地識別重要節(jié)點和邊.因此,復(fù)雜網(wǎng)絡(luò)的研究重心逐漸向超網(wǎng)絡(luò)結(jié)構(gòu)特性的探索研究過渡,超網(wǎng)絡(luò)以其自身獨具的多層性、 多維度、 多屬性等特性,在保證節(jié)點同質(zhì)性的同時,可以直接體現(xiàn)任意多個節(jié)點和超邊間的復(fù)雜關(guān)系,吸引了眾多學(xué)者的目光.Wang等[3]采用增長和優(yōu)先連接機制逐步生成超網(wǎng)絡(luò)動態(tài)演化模型并對網(wǎng)絡(luò)屬性進行分析.Ernesto等[4]研究了超網(wǎng)絡(luò)的子圖中心性和聚類系數(shù)等問題.胡楓等[5-6]構(gòu)建了BA無標(biāo)度超網(wǎng)絡(luò)和隨機超網(wǎng)絡(luò)演化模型,并分析了蛋白質(zhì)超網(wǎng)絡(luò)和科研合作超網(wǎng)絡(luò)的拓撲屬性.郭進利等[7-10]研究了非均勻超網(wǎng)絡(luò)中無標(biāo)度涌現(xiàn)問題,并在輿情傳播以及超網(wǎng)絡(luò)演化的內(nèi)在驅(qū)動力問題上進行了探索.在交通網(wǎng)絡(luò)的實際應(yīng)用中,黎耕等[11]通過計算分析成渝城市群功能多中心度,得出通過培育城市群多中心,能夠有效促進城市群內(nèi)其他城市的發(fā)展.在超網(wǎng)絡(luò)的實際應(yīng)用中,孫琳等[12]采用超網(wǎng)絡(luò)的研究方法分析了歐洲航空超網(wǎng)絡(luò)的特征.陸睿敏等[13]構(gòu)造了上海市公交超網(wǎng)絡(luò)并對網(wǎng)絡(luò)的拓撲特性以及魯棒性進行了分析.
復(fù)雜網(wǎng)絡(luò)性能研究中,網(wǎng)絡(luò)的抗毀性是系統(tǒng)在遭到針對性的蓄意攻擊或隨機攻擊時網(wǎng)絡(luò)仍能保持暢通且穩(wěn)定工作的能力.目前基于圖論的網(wǎng)絡(luò)抗毀性指標(biāo)有:連通度、 完整度、 離散度、 粘聚度以及網(wǎng)絡(luò)效率等[14],但這些指標(biāo)在網(wǎng)絡(luò)規(guī)模、 計算復(fù)雜度以及結(jié)果的精確性上皆有局限性,并不適合結(jié)構(gòu)復(fù)雜的大規(guī)模網(wǎng)絡(luò).隨后,吳俊等[15-17]引入了自然連通度指標(biāo)來衡量復(fù)雜網(wǎng)絡(luò)的抗毀性,該測度能精準(zhǔn)客觀地刻畫網(wǎng)絡(luò)的抗毀性.此外,馬秀娟等[18]結(jié)合超圖理論知識,仿真分析了無標(biāo)度超網(wǎng)絡(luò)上的相繼故障問題.結(jié)果表明,超網(wǎng)絡(luò)在遭受外部攻擊時,表現(xiàn)出既魯棒又脆弱的特性.因此,基于節(jié)點和超邊重要性的公交超網(wǎng)絡(luò)魯棒性的研究也頗有意義.
城市公共交通是市民快捷、 環(huán)保且低價出行的首要選擇,公交系統(tǒng)的髙效便捷對城市市民的出行、 運輸效率、 環(huán)境保護、 綠色出行以及經(jīng)濟發(fā)展都有重要意義[19-20].本文基于超圖理論,構(gòu)造了城市公交超網(wǎng)絡(luò)模型,相較于現(xiàn)有的研究工作,本文的主要貢獻在于結(jié)合超圖的2-section圖和線路理論進一步分析城市公交超網(wǎng)絡(luò)的特性,基于節(jié)點度、 超度以及介數(shù)中心性3個拓撲指標(biāo)識別超網(wǎng)絡(luò)中的關(guān)鍵節(jié)點,用超邊度識別超網(wǎng)絡(luò)中的關(guān)鍵超邊.此外,還構(gòu)造了與公交超網(wǎng)絡(luò)相依賴的以美團商家為節(jié)點,公交站點為超邊的美團超網(wǎng)絡(luò),探究了站點的分布對城市經(jīng)濟發(fā)展的影響.此外,基于自然連通度指標(biāo)分析了公交超網(wǎng)絡(luò)的節(jié)點和超邊在隨機和蓄意兩種攻擊方式下,超網(wǎng)絡(luò)的抗毀性,并結(jié)合網(wǎng)絡(luò)的抗毀性結(jié)果,提出了站點減壓策略來緩解蓄意攻擊對公交超網(wǎng)絡(luò)的影響.本文以青海省西寧市為例,其研究方法也適用于其他城市公交超網(wǎng)絡(luò)的研究與應(yīng)用,本文的研究結(jié)果可為城市交通系統(tǒng)的建設(shè)提供一定的理論依據(jù).
近年來,超網(wǎng)絡(luò)的理論研究與發(fā)展日漸完善,超網(wǎng)絡(luò)的知識也逐漸應(yīng)用到現(xiàn)實社會中,研究內(nèi)容主要有超網(wǎng)絡(luò)演化模型的構(gòu)建和超網(wǎng)絡(luò)動力學(xué)研究兩方面[3-6,8-13,17].
目前,超網(wǎng)絡(luò)的定義主要有兩種,一種是基于超圖理論的超網(wǎng)絡(luò),另一種是由不同類型的網(wǎng)絡(luò)相互連接構(gòu)成的超網(wǎng)絡(luò).前者的網(wǎng)絡(luò)節(jié)點連邊演化為超邊,超邊內(nèi)部允許多個節(jié)點存在,超邊之間通過公共節(jié)點彼此連接,其中關(guān)聯(lián)矩陣是描述超網(wǎng)絡(luò)最直接的表現(xiàn)形式.后者的概念最早由Denning[21]提出,指的是規(guī)模龐大,由多個網(wǎng)絡(luò)相互嵌套構(gòu)成的超級網(wǎng)絡(luò),又稱“多層網(wǎng)絡(luò)”或“多級網(wǎng)絡(luò)”[22],此類超網(wǎng)絡(luò)可以刻畫多個不同類型網(wǎng)絡(luò)之間錯綜復(fù)雜的多重關(guān)聯(lián)關(guān)系.
超圖的2-section圖和線圖的概念最早由Bretto[24]提出.超圖H=(V,E)的2-section圖記為[H]2,其中[H]2的節(jié)點集為H的節(jié)點集.若兩個節(jié)點在[H]2中有連邊當(dāng)且僅當(dāng)這兩個節(jié)點包含在超圖的同一條超邊中,因此,[H]2中的每一條超邊內(nèi)所有節(jié)點間是全連接的.超圖的2-section圖結(jié)構(gòu)顯示了網(wǎng)絡(luò)中所有節(jié)點之間的連接關(guān)系,相同超邊內(nèi)的節(jié)點之間全連接,不同超邊中的節(jié)點通過公共節(jié)點也可以間接連接,通過2-section圖的鄰接矩陣,可以求得網(wǎng)絡(luò)中節(jié)點的度分布情況,也可以求得網(wǎng)絡(luò)的聚集系數(shù)和節(jié)點的介數(shù)值,從而判斷出網(wǎng)絡(luò)整體的稀疏性以及網(wǎng)絡(luò)中的關(guān)鍵節(jié)點.
在文獻[3]中,線圖被稱為超網(wǎng)絡(luò)的投影網(wǎng)絡(luò),記為L(H)=(V′,E′),令超圖H沒有重復(fù)超邊,那么V′∶=E,并且如果H中的兩條超邊ei與ej滿足ei∩ej≠φ,那么在L(H)中節(jié)點ei與ej相鄰.線圖結(jié)構(gòu)顯示了網(wǎng)絡(luò)中超邊之間的連接關(guān)系,線圖的鄰接矩陣可用于求解網(wǎng)絡(luò)中超邊度分布.圖1給出了具有14個節(jié)點,7條超邊的超圖結(jié)構(gòu),對應(yīng)的2-section圖結(jié)構(gòu)以及對應(yīng)的線圖結(jié)構(gòu).
圖1 超圖的2-section圖與線圖的結(jié)構(gòu)特征
超圖H=(V,E)中,節(jié)點的度是節(jié)點vi相鄰其他節(jié)點的總數(shù),記為ki,節(jié)點vi的超度d(vi)指節(jié)點vi所在的超邊數(shù)目.定義超圖H的鄰接矩陣為A=(aij)N×N,關(guān)聯(lián)矩陣為C=(cij)N×M.節(jié)點vi的度和超度表示如下:
(1)
(2)
其中節(jié)點vi的度分布p(ki)是超圖H中節(jié)點度ki占所有節(jié)點總數(shù)的概率大?。洖?/p>
(3)
節(jié)點vi的超度分布p(d(vi))是指在超圖H中節(jié)點超度d(vi)占所有節(jié)點總數(shù)的概率大小,即:
(4)
超圖H=(V,E)中,超邊度定義為與超邊ej至少存在1個公共節(jié)點的超邊的數(shù)目,記為d(ej).超邊超度[7]指超邊ej中所有節(jié)點總數(shù),記為ds(ej).公交超網(wǎng)絡(luò)中,超邊超度是線路中所包含站點的總數(shù).在關(guān)聯(lián)矩陣C中,超邊ej的超邊超度ds(ej)為C的第j列所有元素之和,即:
(5)
復(fù)雜網(wǎng)絡(luò)的介數(shù)中心性簡稱介數(shù)[25],表示網(wǎng)絡(luò)中節(jié)點i恰好經(jīng)過所有最短路徑的數(shù)目與最短路徑總數(shù)的比值.介數(shù)值在公交超網(wǎng)絡(luò)中可以反映站點的擁堵情況以及對換乘情況的影響.基于超圖理論,將超網(wǎng)絡(luò)轉(zhuǎn)化為2-section圖形式,計算節(jié)點的介數(shù)值,表達式如下:
(6)
其中,gpq代表網(wǎng)絡(luò)中所有的最短路徑的數(shù)目總和,gpq(i)表示節(jié)點i正好經(jīng)過所有最短路徑的數(shù)目,1/(n-1)(n-2)是歸一化因子.
基于超圖的公交超網(wǎng)絡(luò)中,節(jié)點為公交站點,超邊代表一條線路中所有的站點集合.采用Java編程程序?qū)?shù)據(jù)進行整合,通過算法控制,構(gòu)建了該公交超網(wǎng)絡(luò)節(jié)點的鄰接矩陣和超邊的鄰接矩陣,以及節(jié)點和超邊間非對稱的關(guān)聯(lián)矩陣.之后采用Python應(yīng)用程序,基于各矩陣特征,分別分析了網(wǎng)絡(luò)的度分布、 超度分布、 超邊度分布、 聚集系數(shù)、 介數(shù)值等特征屬性.
城市公交超網(wǎng)絡(luò)構(gòu)建步驟如下:
1) 初始化:定義超網(wǎng)絡(luò)中節(jié)點集合為vi,超邊集合為ek,其中i=1,2,…,n,k=1,2,…,m.
2) 檢查超網(wǎng)絡(luò)中全部的節(jié)點,若遍歷得到節(jié)點vi和vj出現(xiàn)在同一條線路中,那么將節(jié)點vi和vj添加到對應(yīng)的超邊ek中.
3) 循環(huán)執(zhí)行步驟2),直至所有站點和線路數(shù)據(jù)全部被檢索完畢,算法結(jié)束.
依據(jù)超網(wǎng)絡(luò)的構(gòu)建算法,本文對西寧市公交站點和線路數(shù)據(jù)進行收集、 清洗和整理完善,最終得到540個公交站點以及91條公交線路,并分析其拓撲特性.在西寧市公交超網(wǎng)絡(luò)中,一條線路中最多包含62個站點,一個站點上最多可經(jīng)過27條線路,該超網(wǎng)絡(luò)的網(wǎng)絡(luò)規(guī)模適中,其中超度值較大的站點承擔(dān)公交超網(wǎng)絡(luò)中大部分的換乘工作.
1)節(jié)點度及度分布
公交超網(wǎng)絡(luò)的站點度值越大表明該站點在整個網(wǎng)絡(luò)中的連通性就越好.圖2是西寧市公交超網(wǎng)絡(luò)的度分布,其中,少部分節(jié)點擁有較高的度值,而大部分節(jié)點度值相對較小,整體分布極其不均勻,表明網(wǎng)絡(luò)中只有少數(shù)節(jié)點發(fā)揮著關(guān)鍵作用.最大的兩個度值分別為337和317,對應(yīng)于五岔路口站和昆侖橋站,這兩個站點為西寧市的核心站點,地處城市中心位置,人員流動密集并且道路通達性較好.
圖2 西寧市公交超網(wǎng)絡(luò)的度分布
2) 節(jié)點的超度及超度分布
站點的超度值由站點和線路兩個數(shù)據(jù)集同時分析得到,它表示所有線路中途經(jīng)該站點的線路數(shù)目.圖3為節(jié)點的超度分布,圖4是雙對數(shù)坐標(biāo)系下超度分布曲線的擬合,結(jié)果顯示公交超網(wǎng)絡(luò)的超度分布趨于冪律分布,冪指數(shù)Slope=-2.038 3,網(wǎng)絡(luò)具備BA無標(biāo)度特性.此外,分析數(shù)據(jù)集可知,最大的兩個超度值為27和26,同樣是五岔路口和昆侖橋站,這表明經(jīng)過這兩個站點的公交線路數(shù)目較多,該公交站點的換乘量較大,換乘選擇更多.結(jié)合表1數(shù)據(jù)得到,站點的超度值和度值是正相關(guān)的,節(jié)點重要性對于交通擁堵、 換乘選擇、 交通網(wǎng)絡(luò)系統(tǒng)整體的通達性以及抗毀性能等方面都有著重要的意義.
圖3 節(jié)點的超度分布
表1 站點超度值與度值比較
圖4 雙對數(shù)下的超度分布擬合
3) 超邊度及超邊超度
超網(wǎng)絡(luò)模型不僅能識別關(guān)鍵節(jié)點,還可以識別關(guān)鍵超邊.公交超網(wǎng)絡(luò)中,如果一條線路鄰接其他線路的數(shù)量越多,那么通過該線路,乘客換乘到其他站點或是線路的選擇性就會更多.超邊超度反映的是一條超邊中節(jié)點的總數(shù),即單條線路所包含的公交站點的總數(shù)量,該公交超網(wǎng)絡(luò)的平均超邊超度值為23,即平均每條線路包含23個站點.如圖5所示,超邊度分布近似于正態(tài)分布,說明網(wǎng)絡(luò)中線路分布較為均勻,表2是超邊度值排名前20的線路,分析表中數(shù)據(jù)得到,超邊超度的值也會影響超邊度值,因為線路中站點數(shù)目越多,其線路鄰接其他線路的數(shù)量就越多.因此,超邊超度值較大的路線,它的超邊度值也較大.
圖5 超邊度分布
表2 超邊度值排名前20的線路
關(guān)鍵線路對于市民日常的出行選擇以及交通系統(tǒng)對客運量的安排規(guī)劃有著一定的指導(dǎo)作用.
4) 平均路徑長度和聚集系數(shù)
平均路徑長度描述了從某一站點任意到達其他站點之間的距離,即從站點i抵達站點j時中途需要換乘的線路數(shù)量.通過數(shù)據(jù)計算得到西寧市公交超網(wǎng)絡(luò)的平均路徑長度約為1.91892,近似為2,由此可知,在西寧市從某一站點到另一站點平均換乘兩次便可到達.聚集系數(shù)反映出線路之間的緊密程度,計算得到該超網(wǎng)絡(luò)的聚集系數(shù)約為0.6953,較大的聚集系數(shù)和較小的平均路徑長度均表明西寧市交通超網(wǎng)絡(luò)具有小世界特性.
5)介數(shù)
除了節(jié)點的度和超度,節(jié)點的介數(shù)也是衡量節(jié)點重要性的指標(biāo)之一.表3列出了西寧市公交超網(wǎng)絡(luò)介數(shù)值排名前12名的站點.由表1可知,介數(shù)值較大的站點的度值和超度值也較高,通過衡量這3個測度,可以準(zhǔn)確地識別網(wǎng)絡(luò)的關(guān)鍵節(jié)點.西寧市公交超網(wǎng)絡(luò)的關(guān)鍵節(jié)點分別是昆侖橋站、 五岔路口站.這些關(guān)鍵節(jié)點承載了公交超網(wǎng)絡(luò)大部分的客運量,客流壓力較大,如果在這些關(guān)鍵節(jié)點處發(fā)生交通擁堵或者交通事故,將對整個交通系統(tǒng)的正常運行造成危害,甚至可能會導(dǎo)致整個交通網(wǎng)絡(luò)癱瘓.結(jié)合交通擁堵指數(shù),進一步驗證了關(guān)鍵節(jié)點對交通擁堵情況的影響.智能CT實時數(shù)據(jù)顯示,西寧市的交通擁堵延時指數(shù)為1.47,平均速度為29.41 km/h,按照區(qū)域擁堵排名,在四區(qū)中最擁堵區(qū)域為城西區(qū),擁堵指數(shù)為1.75,平均速度為24.81 km/h; 其次為城中區(qū),擁堵指數(shù)為1.65,平均速度為25.45 km/h.按照城市商圈擁堵排名,最擁堵區(qū)域為虎臺區(qū)域,擁堵指數(shù)為2.02,平均速度為18.38 km/h.在城西區(qū),超度值和介數(shù)值較大的站點均占41%以上,而虎臺商圈也位于城西區(qū).結(jié)果證實,這些關(guān)鍵站點對整片區(qū)域甚至整個交通網(wǎng)絡(luò)的擁堵狀況影響甚大,為改善交通擁堵狀況,應(yīng)在這些核心節(jié)點處實行分流策略,降低站點處的車流量,緩解交通壓力.
表3 介數(shù)值排名前12名的站點
本文應(yīng)用超圖的2-section圖和線圖的理論知識,將公交超網(wǎng)絡(luò)轉(zhuǎn)化為超圖的形式,目的是借助它的2-section圖和線圖的鄰接矩陣,分析得出該公交超網(wǎng)絡(luò)的度分布、 介數(shù)中心性等拓撲屬性.學(xué)者陸睿敏所構(gòu)造的公交超網(wǎng)絡(luò)中,站點為超邊,線路為節(jié)點,通過與上海市公交超網(wǎng)絡(luò)的實驗結(jié)果對比,發(fā)現(xiàn)這兩個公交超網(wǎng)絡(luò)均符合小世界特性,有著較大的聚集系數(shù)和較小的平均路徑長度,線路分布較為均勻,站點分布呈現(xiàn)冪律分布.因此,應(yīng)用超圖的2-section圖和線圖的理論知識,同樣也能準(zhǔn)確地分析超網(wǎng)絡(luò)的結(jié)構(gòu)屬性.
現(xiàn)實世界中,基于網(wǎng)絡(luò)的超網(wǎng)絡(luò)更能全面描述整個城市不同類型網(wǎng)絡(luò)之間的相互連接和制約關(guān)系,它的涵蓋面更廣,節(jié)點種類更加豐富,連邊關(guān)系更加復(fù)雜多樣.該超網(wǎng)絡(luò)最早由Kurant等[26]提出,但真正掀起網(wǎng)絡(luò)科學(xué)中相互依存網(wǎng)絡(luò)研究熱潮的是Buldyrev[27]等在2010年Nature上發(fā)表的關(guān)于相互依存網(wǎng)絡(luò)級聯(lián)失效問題的研究,這種相互依存超網(wǎng)絡(luò)中蘊含著很多的數(shù)據(jù)信息,在當(dāng)今大數(shù)據(jù)時代,超網(wǎng)絡(luò)為探索不同類型群體之間的相互作用和相互制約等關(guān)系提供了有利的分析工具.通過采集現(xiàn)實網(wǎng)絡(luò)的數(shù)據(jù)信息,再結(jié)合數(shù)學(xué)圖論、 統(tǒng)計學(xué)以及動力學(xué)等知識就可以構(gòu)造相互依存超網(wǎng)絡(luò),對相互依存超網(wǎng)絡(luò)進行特性分析,能夠挖掘出很多對社會發(fā)展有用的重要信息,發(fā)現(xiàn)新的商機,對城市經(jīng)濟效益和社會效益等諸多方面帶來更大的提升.
基于相互依存網(wǎng)絡(luò)的理論知識,構(gòu)造了與公交超網(wǎng)絡(luò)相依存的美團超網(wǎng)絡(luò).該超網(wǎng)絡(luò)以站點為超邊,站點周圍2km范圍內(nèi)的美團美食商家為節(jié)點,其擁有540條超邊和10311個節(jié)點,該美團超網(wǎng)絡(luò)模型的構(gòu)建算法與公交超網(wǎng)絡(luò)構(gòu)造算法一致.
對比分析公交站點的超度值以及美團超網(wǎng)絡(luò)的超邊超度值,即站點周圍的美團美食商家數(shù)目,得出站點的分布與城市經(jīng)濟發(fā)展之間的關(guān)系.圖6顯示了站點的超度值與美團商家數(shù)目的比較,得到超度值與商家數(shù)目成正比關(guān)系,即超度值較大的站點周圍有較多的商家,經(jīng)濟發(fā)展也較為繁華.但也有例外,比如五岔路口站,它的超度值為27,但是附近美團美食商家數(shù)僅有兩家,這是因為該站點地處五條道路匯聚口,道路繁雜,周邊幾乎都是道路,只存在少量商戶,所以在分析站點超度值和美團商家數(shù)的對應(yīng)關(guān)系時,還應(yīng)該切合實際,結(jié)合理論和實際兩方面來闡述社會現(xiàn)象.通過兩個超網(wǎng)絡(luò)之間的關(guān)聯(lián)關(guān)系,得出站點的分布對于城市經(jīng)濟發(fā)展有較大影響,因此,超網(wǎng)絡(luò)的特性更能反映現(xiàn)實系統(tǒng)之間的關(guān)聯(lián)關(guān)系,對真實世界多維系統(tǒng)的研究也更有意義.
圖6 站點超度值與美團商家數(shù)目對比圖
超圖的2-section圖[H]2中,節(jié)點集為V={v1,v2,…,vn},若在超圖H中,兩個節(jié)點包含在同一條超邊中,則這兩個節(jié)點在[H]2中用一條普通邊相連接,因此,該超網(wǎng)絡(luò)的鄰接矩陣A=(aij)N×N就是相對應(yīng)2-section圖的鄰接矩陣.由于該矩陣為對稱矩陣,則令λ1≥λ2≥…≥λN為A(H)的特征根,稱集合{λi}為超圖H的鄰接矩陣特征譜.在超網(wǎng)絡(luò)中,該指標(biāo)結(jié)合網(wǎng)絡(luò)的內(nèi)部結(jié)構(gòu),通過計算網(wǎng)絡(luò)中不同長度閉合路徑數(shù)目的加權(quán)和來刻畫網(wǎng)絡(luò)中替代途徑的冗余性,并且該指標(biāo)在刪除節(jié)點和超邊上是嚴(yán)格單調(diào)的,這就能清楚地識別網(wǎng)絡(luò)在經(jīng)歷每一次攻擊后,自然連通度值的細微變化,從而有效地分辨在不同攻擊下,網(wǎng)絡(luò)抗毀性的強弱.更重要的是該測度在網(wǎng)絡(luò)不連通時仍然有效[7].
由于節(jié)點之間的抗毀性來源于網(wǎng)絡(luò)中替代途徑的冗余性,則網(wǎng)絡(luò)中所有的閉途徑數(shù)目用超網(wǎng)絡(luò)鄰接矩陣的特征值進行表示,這樣網(wǎng)絡(luò)的魯棒性就可以通過其鄰接矩陣的特征值計算得到,定義超網(wǎng)絡(luò)的自然連通度為
(7)
其中,λi為超網(wǎng)絡(luò)鄰接矩陣的特征根.
本文將自然連通度值作為衡量公交超網(wǎng)絡(luò)抗毀性的度量指標(biāo),結(jié)合python程序求解該超網(wǎng)絡(luò)的自然連通度值并分析實驗結(jié)果,繪制實驗對比圖.實驗分別設(shè)計了在隨機攻擊和蓄意攻擊兩種攻擊策略下,網(wǎng)絡(luò)自然連通度值的變化趨勢.
1) 隨機攻擊策略
隨機攻擊中,分別討論了節(jié)點和超邊失效下網(wǎng)絡(luò)的抗毀性.首先,對節(jié)點和超邊編號并隨機排序; 考慮兩種失效方式:① 節(jié)點失效下,依據(jù)節(jié)點編號隨機刪去10個節(jié)點,記錄一次數(shù)據(jù),直至網(wǎng)絡(luò)中所有節(jié)點刪除完畢,實驗終止.② 超邊失效下,依據(jù)超邊編號隨機刪去一條超邊,記錄數(shù)據(jù),直至網(wǎng)絡(luò)中所有超邊刪除完畢,實驗終止.
2) 蓄意攻擊策略
蓄意攻擊中,同樣考慮了節(jié)點和超邊兩種失效方式.節(jié)點失效下,依據(jù)兩個節(jié)點重要性指標(biāo),分別比較了節(jié)點在基于超度值和介數(shù)值兩個指標(biāo)攻擊下網(wǎng)絡(luò)的抗毀性.超邊失效下,依據(jù)超邊重要性指標(biāo),即超邊度值來衡量網(wǎng)絡(luò)的抗毀性.首先,依據(jù)節(jié)點的超度值以及介數(shù)值分別從大到小將節(jié)點進行排序,隨后,從超度值較大的節(jié)點開始依次刪除,每刪除10個節(jié)點記錄一次自然連通度值,直至所有節(jié)點刪除完畢,實驗結(jié)束.基于介數(shù)值的攻擊同超度值一樣.在超邊攻擊中,按照超邊度值從大到小依次對超邊進行排序,隨后,依次刪除1條超邊度值較大的超邊,每刪除1條超邊,記錄一次實驗結(jié)果,直至所有超邊刪除完畢,實驗終止.
超網(wǎng)絡(luò)抗毀性結(jié)果如圖7所示,隨機攻擊策略下,分別統(tǒng)計了10次實驗結(jié)果的數(shù)據(jù),即當(dāng)網(wǎng)絡(luò)中100個節(jié)點失效時,自然連通度值下降了12,網(wǎng)絡(luò)中10條超邊失效時,自然連通度值下降了83.在蓄意攻擊中,10次實驗后,基于超度值攻擊100個節(jié)點后自然連通度值下降了69,基于介數(shù)值攻擊100個節(jié)點后自然連通度值下降了77,而基于超度值攻擊了10條超邊后,自然連通度值下降了76.從實驗數(shù)據(jù)得知,節(jié)點攻擊中,隨機策略下網(wǎng)絡(luò)抗毀性最強; 其次是對超度值的蓄意攻擊,最弱的是基于介數(shù)值的蓄意攻擊.而在超邊攻擊中,前14次實驗并不能準(zhǔn)確判斷魯棒性的強弱,攻擊了14條超邊后,隨機攻擊超邊的抗毀性要強于基于超邊度值的蓄意攻擊.
圖7 不同條件下自然連通度值比較
城市交通網(wǎng)絡(luò)中,基于站點和線路的蓄意攻擊往往會影響交通網(wǎng)絡(luò)的順暢運行,小到妨礙市民出行,大到不可預(yù)估的經(jīng)濟損失,因此,如何制定策略來提升網(wǎng)絡(luò)的抗毀能力,顯得尤為重要.通過對比分析超網(wǎng)絡(luò)在隨機攻擊與基于超度值和介數(shù)值的蓄意攻擊下網(wǎng)絡(luò)的受損情況以及核心站點的分布情況,本文提出對公交站點實行減壓策略,減少較大超度值站點處的線路通行數(shù)量以及客運量,以此來應(yīng)對蓄意攻擊.
站點減壓策略主要分為兩個步驟:首先,線路實行站點隔站??糠绞剑饕窃谶B續(xù)的幾個超度值較大的站點之間實行分站??浚源藖斫档秃诵墓?jié)點處的線路通行數(shù)量,降低網(wǎng)絡(luò)擁塞幾率; 其次,在超度值較小的站點之間可適當(dāng)增設(shè)新的站點,多分配線路,這樣可以增強網(wǎng)絡(luò)的連通度,提升網(wǎng)絡(luò)的冗余線路數(shù)量,為道路擁塞提供多條備選路徑,以此緩解交通壓力.
針對上述策略,本文對現(xiàn)有的公交超網(wǎng)絡(luò)進行數(shù)據(jù)模擬,實驗首先增設(shè)了100個新站點,分別位于連續(xù)的超度值較小的站點之間,同時,對超度值大于10的站點進行隔站線路??坎呗裕谛碌某W(wǎng)絡(luò)構(gòu)造完成之后,同樣采取5.2中的攻擊策略對新超網(wǎng)絡(luò)進行攻擊,結(jié)果如圖8所示.通過與未加策略的蓄意攻擊結(jié)果對比發(fā)現(xiàn),本節(jié)提出的站點減壓策略確實能有效緩解網(wǎng)絡(luò)的崩潰壓力,其中,基于超度攻擊的網(wǎng)絡(luò)抗毀性仍然強于基于介數(shù)的攻擊.
圖8 站點減壓策略下自然連通度值比較
基于超圖的公交超網(wǎng)絡(luò)結(jié)構(gòu)模型不同于普通網(wǎng)絡(luò)的結(jié)構(gòu),超網(wǎng)絡(luò)每條超邊內(nèi)部節(jié)點之間是全連接的,相比于普通網(wǎng)絡(luò),網(wǎng)絡(luò)的緊密程度更大,網(wǎng)絡(luò)中冗余鏈路也較多.因此,超網(wǎng)絡(luò)的抗毀性比同規(guī)模的普通網(wǎng)絡(luò)的抗毀性更強,一旦某些節(jié)點受到攻擊,網(wǎng)絡(luò)仍有許多備選路徑,可維持網(wǎng)絡(luò)暢通,這也是公交超網(wǎng)絡(luò)的優(yōu)勢.但是一旦一些關(guān)鍵節(jié)點或線路發(fā)生交通堵塞或交通事故,就可能導(dǎo)致網(wǎng)絡(luò)局部甚至全局流通性能下降.因此,通過對站點實行減壓策略,再配合對網(wǎng)絡(luò)規(guī)模的調(diào)整,就可以有效緩解網(wǎng)絡(luò)的交通壓力,增強網(wǎng)絡(luò)的抗毀性.
本文基于超圖理論構(gòu)建了城市公交超網(wǎng)絡(luò)模型,研究了該超網(wǎng)絡(luò)的節(jié)點超度、 超邊度、 超邊超度、 聚集系數(shù)、 平均路徑長度以及介數(shù)等拓撲屬性,并進行了仿真實驗,識別了該超網(wǎng)絡(luò)的關(guān)鍵節(jié)點和超邊,并基于節(jié)點重要性分析了關(guān)鍵節(jié)點對城市商圈地理位置的影響和該超網(wǎng)絡(luò)的魯棒性,提出了應(yīng)對蓄意攻擊的站點減壓策略.實驗結(jié)果表明,本文所構(gòu)建的公交超網(wǎng)絡(luò)具備小世界網(wǎng)絡(luò)特性,站點的分布反映出城市經(jīng)濟的發(fā)展情況.從整體上看,超度值較大的站點周圍美團商家數(shù)多,而更多的站點周圍只有很少甚至沒有美團商家,大部分站點附近經(jīng)濟發(fā)展力度不夠.在公交超網(wǎng)絡(luò)的抗毀性分析中,節(jié)點失效下,網(wǎng)絡(luò)對隨機攻擊的承受能力較強,在基于介數(shù)值較大節(jié)點的蓄意攻擊中,魯棒性最弱.超邊失效下,基于超邊度值攻擊的魯棒性要弱于隨機攻擊的魯棒性.針對這些屬性,本文提出的站點減壓策略,能夠有效恢復(fù)蓄意攻擊后的超網(wǎng)絡(luò),能為交通系統(tǒng)的統(tǒng)籌安排提供參考.