蘭州市公交網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)與脆弱性分析

馬宇紅，李 憲，陳 閃，張 琴

(1.西北師范大學(xué)學(xué)報(bào)編輯部，甘肅蘭州 730070；2.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅蘭州 730070)

?

蘭州市公交網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)與脆弱性分析

馬宇紅1,2，李 憲2，陳 閃2，張 琴2

(1.西北師范大學(xué)學(xué)報(bào)編輯部，甘肅蘭州 730070；2.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅蘭州 730070)

基于復(fù)雜網(wǎng)絡(luò)理論，研究蘭州市公交網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)及其脆弱性.根據(jù)實(shí)證數(shù)據(jù)建立了蘭州市公交網(wǎng)絡(luò)的結(jié)構(gòu)模型，并應(yīng)用Fast Newman算法分析公交網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，給出了最優(yōu)的社團(tuán)劃分；從獲得的社團(tuán)結(jié)構(gòu)出發(fā)，分析了蘭州市公交網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的脆弱性，給出了各個(gè)社團(tuán)的脆弱集及脆弱性指標(biāo).研究結(jié)果表明，蘭州市公交網(wǎng)絡(luò)具有明顯的社團(tuán)結(jié)構(gòu)特性，社團(tuán)劃分受到城市獨(dú)特地形特性的影響；許多社團(tuán)在網(wǎng)絡(luò)中表現(xiàn)異常脆弱，社團(tuán)之間聯(lián)系稀疏，極易因?yàn)殡S機(jī)故障或蓄意攻擊而形成多個(gè)獨(dú)立的連通分支.

公交網(wǎng)絡(luò)；社團(tuán)結(jié)構(gòu)；社團(tuán)劃分；脆弱性

0 引言

交通問題是21世紀(jì)城市發(fā)展必須面對的重大問題，許多國家和地區(qū)通過大力發(fā)展公共交通運(yùn)輸體系來解決這一問題，一個(gè)穩(wěn)定高效的公交網(wǎng)絡(luò)對于人們的日常生活和城市的發(fā)展至關(guān)重要，所以分析城市公交網(wǎng)絡(luò)的脆弱性，確定相對脆弱部分，并在公交線路設(shè)計(jì)和結(jié)構(gòu)優(yōu)化過程中進(jìn)行有針對性的改善與防護(hù)是非常必要的.

隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)科學(xué)在20世紀(jì)末取得了突破性進(jìn)展，相關(guān)理論已經(jīng)滲透到了數(shù)學(xué)、物理學(xué)、生物學(xué)、社會(huì)學(xué)等諸多學(xué)科，成為一個(gè)跨學(xué)科的新興領(lǐng)域.復(fù)雜網(wǎng)絡(luò)理論[1]可以為許多實(shí)際問題的研究提供了新的視角和方法，運(yùn)用計(jì)算機(jī)技術(shù)和復(fù)雜網(wǎng)絡(luò)理論對各種實(shí)際網(wǎng)絡(luò)進(jìn)行模擬分析開始受到學(xué)者的廣泛關(guān)注，例如城市公交網(wǎng)絡(luò)性能分析[2]、電力系統(tǒng)安全評估[3]、通訊網(wǎng)絡(luò)故障檢測[4]等.

復(fù)雜網(wǎng)絡(luò)的脆弱性研究源于Albert等[5]，此后，各種網(wǎng)絡(luò)模型和實(shí)際網(wǎng)絡(luò)的脆弱性問題引起了研究者的極大興趣[6-9]，相關(guān)研究致力于分析隨機(jī)故障或蓄意攻擊對網(wǎng)絡(luò)連通性的影響，即按照某種規(guī)則從網(wǎng)絡(luò)中刪除部分節(jié)點(diǎn)對網(wǎng)絡(luò)連通性及巨片規(guī)模的影響.同時(shí)，為了多角度衡量網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性，除了度、介數(shù)等傳統(tǒng)的度量外，一些新的中心性度量指標(biāo)，例如modal[10]、pagerank[11]等相繼被提出.但是，現(xiàn)有文獻(xiàn)多著重于節(jié)點(diǎn)故障對網(wǎng)絡(luò)魯棒性的影響，事實(shí)上，邊的脆弱性對網(wǎng)絡(luò)魯棒性的影響同樣重要，因此，本文從社團(tuán)結(jié)構(gòu)角度出發(fā)，分析蘭州市公交網(wǎng)絡(luò)的最優(yōu)社團(tuán)劃分，并確定各個(gè)社團(tuán)的脆弱集及脆弱性指標(biāo)，為交通部門優(yōu)化線路設(shè)計(jì)、增強(qiáng)網(wǎng)絡(luò)魯棒性提供參考.

1 社團(tuán)結(jié)構(gòu)分析與脆弱性評價(jià)方法

社團(tuán)結(jié)構(gòu)作為復(fù)雜網(wǎng)絡(luò)的一項(xiàng)重要性質(zhì)得到了廣泛關(guān)注，許多真實(shí)世界的網(wǎng)絡(luò)都已經(jīng)被證實(shí)具有社團(tuán)結(jié)構(gòu)[12-13].網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)指的是網(wǎng)絡(luò)中的節(jié)點(diǎn)可以被劃分為若干組，組內(nèi)節(jié)點(diǎn)之間連接緊密而不同組節(jié)點(diǎn)之間連接較為稀疏.對于公交網(wǎng)絡(luò)而言，分析它的社團(tuán)結(jié)構(gòu)可以幫助我們發(fā)現(xiàn)網(wǎng)絡(luò)中連通性較好的區(qū)域以及區(qū)域與區(qū)域之間連通性較差的部分，從而有針對性地改進(jìn)和防護(hù)那些脆弱部分，增強(qiáng)整個(gè)公交體系的魯棒性.

1.1 Fast Newman算法

網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)與計(jì)算機(jī)科學(xué)中的圖分割和社會(huì)學(xué)中的分級(jí)聚類有著密切關(guān)系，早在20世紀(jì)70年代初就已經(jīng)引起了研究者的興趣，一系列發(fā)掘社團(tuán)結(jié)構(gòu)的算法相繼被提出，如基于貪婪算法的Kernighan-Lin算法[14]、基于Laplace圖特征值的譜分解法[15]、基于分級(jí)聚類的Concor算法[16]和基于分裂方法的GN算法[12]等，而目前應(yīng)用最廣泛的是基于優(yōu)化模塊度的算法，如Fast Newman算法(簡稱FN算法)[17]等.在社團(tuán)劃分算法中，模塊度函數(shù)被用來評價(jià)社團(tuán)劃分的質(zhì)量，對于一個(gè)已知網(wǎng)絡(luò)，具有最大模塊度的社團(tuán)劃分即為最優(yōu)劃分.2004年，Newman和Girvan定義了模塊度函數(shù)[18]：

(1)

(2)

其中，ei為社團(tuán)i內(nèi)部邊的數(shù)量；di指屬于社團(tuán)i的所有節(jié)點(diǎn)度的和；m為網(wǎng)絡(luò)的總邊數(shù).

FN算法[17]是一種基于貪婪思想的凝聚算法，它通過尋找最大模塊度Qmax對應(yīng)的社團(tuán)劃分來確定網(wǎng)絡(luò)的最優(yōu)劃分.相比其他一系列算法，它的運(yùn)行速度顯著提升，算法復(fù)雜度為O((m+n)n)，其中n為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，m為網(wǎng)絡(luò)總邊數(shù).FN算法的具體步驟如下：

1)初始化網(wǎng)絡(luò)為n個(gè)社團(tuán)，即每個(gè)節(jié)點(diǎn)組成1個(gè)獨(dú)立社團(tuán).eij和ai分別定義為

ai=ki/2m,

其中，ki為節(jié)點(diǎn)i的度；m為網(wǎng)絡(luò)總邊數(shù).

2)依次合并有邊相連的社團(tuán)對，并計(jì)算合并之后的模塊度增量ΔQ，

(3)

3)取ΔQ為最大值對應(yīng)的兩個(gè)社團(tuán)合并為一個(gè)社團(tuán).

4)重復(fù)步驟2)和3)，直到整個(gè)網(wǎng)絡(luò)被合并為一個(gè)社團(tuán)，結(jié)束算法.

1.2 社團(tuán)脆弱性方法

2011年，Claudio等[19]提出了一個(gè)度量來評價(jià)大規(guī)模網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的脆弱性.該方法根據(jù)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)劃分計(jì)算連接各社團(tuán)之間的邊，得到各個(gè)社團(tuán)的脆弱邊集，再通過計(jì)算每個(gè)社團(tuán)的相對脆弱性指標(biāo)來評價(jià)其脆弱性.當(dāng)某個(gè)社團(tuán)的脆弱邊因隨機(jī)故障或者蓄意攻擊而中斷時(shí)，該社團(tuán)就會(huì)與相鄰的其他社團(tuán)或者網(wǎng)絡(luò)的其余部分徹底分離，形成一個(gè)獨(dú)立的連通分支.如果所有社團(tuán)的脆弱邊全部中斷，網(wǎng)絡(luò)會(huì)迅速分裂成若干孤立的連通分支，彼此完全失去聯(lián)系.這種方法介紹如下：

給定一個(gè)具有確定社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)G=(V,E)，其中V是節(jié)點(diǎn)集，E是邊集，Cx(x∈Λ)表示網(wǎng)絡(luò)的社團(tuán)集，且對?x,y∈Λ,Cx∩Cy=?.網(wǎng)絡(luò)中社團(tuán)x和社團(tuán)y之間的脆弱集Vxy定義為

Vxy={(u,v)∈E,u∈Cx,v∈Cy,x≠y},

(4)

破壞Vxy中所有的邊即可使社團(tuán)x與社團(tuán)y失去直接聯(lián)系.社團(tuán)x，y之間的脆弱性指標(biāo)vxy定義為

(5)

(6)

移除Vx中所有的邊即可使得社團(tuán)x與網(wǎng)絡(luò)的其余部分完全失去聯(lián)系，變成一個(gè)孤立的連通分支.社團(tuán)x的脆弱性指標(biāo)vx定義為

(7)

最后，社團(tuán)x的相對脆弱值定義為

(8)

2 實(shí)例分析

本節(jié)應(yīng)用FN算法和Claudio脆弱性方法分析蘭州市公交網(wǎng)絡(luò)的結(jié)構(gòu)社團(tuán)劃分及其脆弱性，并給出每個(gè)社團(tuán)的脆弱集及相對脆弱性指標(biāo).

2.1 蘭州市公交網(wǎng)絡(luò)建模

在公交網(wǎng)絡(luò)建模過程中，對公交數(shù)據(jù)的處理遵循以下原則：

1)僅考慮城關(guān)、七里河、安寧、西固區(qū)線路，不考慮紅古、永登、皋蘭、榆中三縣一區(qū)線路.

2)一條公交線路在某些路段上下行站點(diǎn)不一致時(shí)，統(tǒng)一取上行線路站點(diǎn).

3)某些線路上下行?？空久灰恢碌珜?shí)際為同一地點(diǎn)時(shí)，將它們合并為一個(gè)站點(diǎn).例如城關(guān)黃河橋南與市政府、廣場南路西口與廣場南口等.

4)同一個(gè)站名具有多個(gè)停車點(diǎn)時(shí)視為同一站點(diǎn)，如蘭州西站東、南、西、北四個(gè)方向的停車點(diǎn)視為同一站點(diǎn).

5)不考慮蘭州軌道交通施工等因素導(dǎo)致的臨時(shí)線路調(diào)整.

圖1 蘭州市公交網(wǎng)絡(luò)Fig 1Image of Lanzhou bus transport network

蘭州市公交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖1所示，節(jié)點(diǎn)代表公交站點(diǎn)，邊代表公交線路上相鄰兩個(gè)站點(diǎn)之間的連邊.蘭州市公交網(wǎng)絡(luò)的拓?fù)湫再|(zhì)見表1.

表1 蘭州市公交網(wǎng)絡(luò)的基本拓?fù)湫再|(zhì)Tab 1 Basic topological properties of Lanzhou bus transport network

2.2 社團(tuán)劃分

通過執(zhí)行FN算法，我們得到蘭州市公交網(wǎng)絡(luò)的最優(yōu)社團(tuán)劃分為20個(gè)社團(tuán)，對應(yīng)的最大模塊度Qmax=0.838 8(圖2)，大于許多實(shí)際網(wǎng)絡(luò)Qmax介于0.3～0.7的范圍[18]，所以蘭州市公交網(wǎng)絡(luò)具有很強(qiáng)社團(tuán)結(jié)構(gòu)特性.規(guī)模最大的社團(tuán)包含65個(gè)節(jié)點(diǎn)，規(guī)模最小的社團(tuán)僅包含8個(gè)節(jié)點(diǎn).由于網(wǎng)絡(luò)規(guī)模較大，通過圖示或樹狀圖可視化具體的社團(tuán)劃分比較困難，所以我們僅給出每個(gè)社團(tuán)的規(guī)模及與其他社團(tuán)有邊相連的邊界點(diǎn)，不給出每個(gè)社團(tuán)包含哪些具體站點(diǎn)，詳見表2.

圖2 FN算法節(jié)點(diǎn)合并過程中的模塊度Q值Fig 2 The value of modular Q in the process of node merging by FN algorithm

從表2可知，社團(tuán)1,18,15,17,20是規(guī)模最大的5個(gè)社團(tuán)，分別包含65,58,43,42,42個(gè)公交站點(diǎn).結(jié)合具體的公交網(wǎng)絡(luò)可知，社團(tuán)1和社團(tuán)18在地理位置上彼此相鄰，社團(tuán)內(nèi)的公交站點(diǎn)占據(jù)了城關(guān)區(qū)的主要區(qū)域；社團(tuán)15位于西固區(qū)的主要區(qū)域，社團(tuán)17和社團(tuán)20分別位于安寧區(qū)和七里河區(qū)的主要區(qū)域.這些規(guī)模較大社團(tuán)的形成與蘭州市各區(qū)內(nèi)部公交線路相對密集的特性有著較大關(guān)系，自然容易形成聯(lián)系緊密的社團(tuán).

表2 蘭州市公交網(wǎng)絡(luò)各社團(tuán)的邊界站點(diǎn)Tab 2 The boundary nodes for communities of Lanzhou bus transport network

從各社團(tuán)的分布區(qū)域看，社團(tuán)4位于黃河北岸與白塔山之間的狹窄地段，社團(tuán)6,9,13,17分別位于黃河北岸九州、大砂坪、廟灘子、安寧地區(qū)；社團(tuán)5,7,12,14位于鐵路南側(cè)與南山之間的狹窄區(qū)域，而其余社團(tuán)則位于黃河南岸與鐵路北側(cè)的主城區(qū).這說明蘭州市公交網(wǎng)絡(luò)的社團(tuán)劃分明顯受到了蘭州市河谷型地形特性以及黃河與隴海、蘭新鐵路穿城而過對城市區(qū)域兩次切割的影響.

2.3 社團(tuán)脆弱性分析

通過計(jì)算得到各個(gè)社團(tuán)的脆弱集Vx及相對脆弱性指標(biāo)Rx的值見表3.

分析脆弱集Vx(x=1,2,…,20)中的站點(diǎn)，我們發(fā)現(xiàn)他們相當(dāng)一部分位于黃河兩岸以及鐵路兩側(cè).由于黃河兩岸僅能通過黃河橋相連，而鐵路兩側(cè)僅能通過下穿道路連通，所以黃河北岸和鐵路南側(cè)區(qū)域與主城區(qū)聯(lián)系通道較少，并且這些區(qū)段又是蘭州市交通流量最密集的路段，例如西站雙洞子、城關(guān)黃河大橋等，這些站點(diǎn)在蘭州市公交體系中極其重要，一旦遭遇道路維修、交通事故、車輛限行等突發(fā)性交通狀況，很容易造成交通擁堵，甚至交通中斷.

從上述分析可以看出，蘭州市公交網(wǎng)絡(luò)不同社團(tuán)之間聯(lián)系較為稀疏，許多社團(tuán)表現(xiàn)異常脆弱，很容易因?yàn)閹讞l邊受到攻擊而被隔離于網(wǎng)絡(luò)之外.在日常運(yùn)營中，交通擁堵、道路維修等隨機(jī)事件很容易破壞公交網(wǎng)絡(luò)的連通性，如果以此為策略蓄意攻擊這些脆弱邊，那么網(wǎng)絡(luò)會(huì)迅速分裂成若干個(gè)孤立的連通分支.因此，在后續(xù)的公交線路設(shè)計(jì)與優(yōu)化過程中，應(yīng)該適當(dāng)增加公交線路串聯(lián)那些脆弱社團(tuán)之間的節(jié)點(diǎn)，增加社團(tuán)之間的連邊，從而提高網(wǎng)絡(luò)的抗毀性.另一方面，在城市建設(shè)中應(yīng)該考慮增加連接黃河南北兩岸和鐵路南北兩側(cè)之間的通道，使得公交線路設(shè)計(jì)更靈活，運(yùn)營更穩(wěn)健.

表3 蘭州市公交網(wǎng)絡(luò)各社團(tuán)脆弱集和相對脆弱值Tab 3 Vulnerability sets and relative vulnerability ofcommunities of Lanzhou bus transport network

3 結(jié)論

基于復(fù)雜網(wǎng)絡(luò)理論，從社團(tuán)結(jié)構(gòu)角度分析了蘭州市公交網(wǎng)絡(luò)的社團(tuán)劃分及社團(tuán)脆弱性.結(jié)果表明，蘭州市公交網(wǎng)絡(luò)具有典型的社團(tuán)結(jié)構(gòu)特性，大致可以被劃分為20個(gè)社團(tuán)，結(jié)構(gòu)劃分很大程度上受到蘭州市特有的河谷型城市地形特性以及黃河、鐵路對城市區(qū)域分割的影響；許多社團(tuán)在網(wǎng)絡(luò)中表現(xiàn)異常脆弱，社團(tuán)間的聯(lián)系極為稀疏，很容易因?yàn)殡S機(jī)故障或蓄意攻擊而成為孤立的連通分支.下一步，我們將在公交線路優(yōu)化設(shè)計(jì)中研究如何強(qiáng)化網(wǎng)絡(luò)的脆弱部分，從而提高其穩(wěn)健性，更好地服務(wù)于乘客出行和城市發(fā)展.

[1] NEWMAN M E J.Networks:AnIntroduction[M].New York:Oxford University Press,2010.

[2] YANG X H,CHEN G,CHEN S Y,et al.Study on some bus transport networks in China with considering spatial characteristics[J].TransportationResearchPartA,2014,69:1.

[3] SEKSAR P,MOHANTY S.An online power system static security assessment module using multi-layer perception and radial basis function network[J].ElectricalPowerandEnergySystems,2016,76:165.

[4] HONG S,YANG Y,ZIO E,et al.A novel dynamics model of fault propagation and equilibrium analysis in complex dynamical communication network[J].AppliedMathematicsandComputation,2014,247:1021.

[5] ALBERT R,JEONG H,BARABASI A L.Attack and error tolerance of complex networks[J].Nature,2000,406(6794):387.

[6] LORDAN O,SALLAN J M,SIMO P,et al.Robustness of the air transport network[J].TransportationResearchPartE,2014,68(9):155.

[7] CALLAWAY D S,NEWMAN M E J,STROGATZ S H,et al.Network robustness and fragility:percolation on random graphs[J].PhysicalReviewLetters,2000,85(25):5468.

[8] CRUCITTI P,LATORA V,MARCHIORI M,et al.Efficiency of scale-free networks:error and attack tolerance[J].PhysicaA,2003,320(C):622.

[9] ALBERT R,ALBERT I,NAKARADO G L.Structural vulnerability of the North American power grid[J].PhysicalReviewE,2004,69(2):292.

[10] PETRESKA I,TOMOVSKI I,GUTIERREZ E,et al.Application of modal analysis in assessing attack vulnerability of complex networks[J].CommunicationsinNonlinearScience&NumericalSimulation,2010,15(4):1008.

[11] BRIN S,PAGE L.The anatomy of a large-scale hypertextual web search engine[J].ComputerNetworksandISDNSystem,1998,30(98):107.

[12] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].ProceedingsoftheNationalAcademyofSciences,2002,99(12):7821.

[13] FLAKE G W,LAWRENCE S R,GILES C L,et al.Self-organization and identification of Web communities[J].IEEEComputer,2002,35:66.

[14] KERNIGHAN B W,LIN S.A efficient heuristic procedure for partitioning graphs[J].BellSystemTechnicalJournal,1970,49:291.

[15] POTHEN A,SIMON H,LIOU K P.Partitioning sparse matrices with eigenvectors of graphs[J].SIAMJMatrixAnalAppl,1990,11:430.

[16] BREIGER R L,BOORMAN S A,ARABIE P.An algorithm for clustering relations data with applications to social network analysis and comparison with multidimensional scaling[J].JournalofMathematicalPsychology,1975,12:328.

[17] NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].PhysicalReviewEStatisticalNonlinear&SoftMatterPhysics,2004,69(6):279.

[18] NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in network[J].PhysRevE,2004,69:026113.

[19] CLAUDIO M R S,RAMIREZ M J E.Vulnerability metrics and analysis for communities in complex networks[J].ReliabilityEngineering&SystemSafety,2011,96(10):1360.

(責(zé)任編輯 馬宇鴻)

Analysis on community structure and vulnerability for Lanzhou bus transport network

MA Yu-hong1,2,LI Xian2,CHEN Shan2,ZHANG Qin2

(1.Editorial Department of the University Journal,Northwest Normal University,Lanzhou 730070,Gansu,China;2.College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,Gansu,China)

The community structure and its vulnerability are investigated for Lanzhou bus transport network based on complex network theory.Firstly,the bus transport network model of Lanzhou City is established based on empirical data，and then its community structure is discussed by use of Fast Newman algorithm,the optimal community division is given.Finally,the vulnerability of Lanzhou bus transport network is analysed from the perspective of the community structure,and the vulnerable set and vulnerability index of every community are determined in detail.The results demonstrate that Lanzhou bus transport network has obvious community structure characteristics,and the community division is influenced by its distinctive urban terrain features;a lot of communities are very weak in the network and the connection between different communities is rather sparse.So the network is fragile under random failures and deliberate attacks,it is very easy to form several independent connected branches.

bus transport network;community structure;community division;vulnerability

10.16783/j.cnki.nwnuz.2016.01.006

2015-07-07;修改稿收到日期:2015-10-22

國家自然科學(xué)基金資助項(xiàng)目(51368055)

馬宇紅(1971—)，男，甘肅天水人，副編審，博士.主要研究方向?yàn)榫W(wǎng)絡(luò)設(shè)計(jì)與優(yōu)化.

E-mail:mayh@nwnu.edu.cn

O 221.2；U 491.1+7

A

1001-988Ⅹ(2016)01-0025-06