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