城市路網(wǎng)模塊結(jié)構(gòu)探測及Hub路段診斷算法

胡郁蔥，陳海偉

(華南理工大學(xué)土木與交通學(xué)院，廣東 廣州 510640)

近年來，復(fù)雜交通網(wǎng)絡(luò)的研究引起了眾多學(xué)者的廣泛關(guān)注.一些實(shí)證研究表明，城市路網(wǎng)和其他網(wǎng)絡(luò)一樣，具有復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)和功能特性，可以用復(fù)雜網(wǎng)絡(luò)的思想對城市路網(wǎng)進(jìn)行研究［1-4］.

模塊結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)重要屬性，主要表現(xiàn)在每個(gè)模塊結(jié)構(gòu)內(nèi)的連接非常緊密，而模塊結(jié)構(gòu)之間的連接卻相對比較松散.圖1中網(wǎng)絡(luò)包含3個(gè)模塊結(jié)構(gòu)，分別對應(yīng)于虛線圓圈包圍的部分.每個(gè)模塊結(jié)構(gòu)內(nèi)部的節(jié)點(diǎn)聯(lián)系非常緊密，而不同模塊結(jié)構(gòu)的節(jié)點(diǎn)之間聯(lián)系就稀疏得多.

圖1 小型模塊結(jié)構(gòu)網(wǎng)絡(luò)示意圖Fig.1 Schematic of a small network with modular structures

許多研究揭示了交通網(wǎng)絡(luò)具有模塊結(jié)構(gòu)特性.文獻(xiàn)［1］研究了世界航空網(wǎng)絡(luò)中的模塊結(jié)構(gòu);文獻(xiàn)［5］基于艾哈邁達(dá)巴德等6個(gè)城市的交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，從統(tǒng)計(jì)學(xué)角度揭示了網(wǎng)絡(luò)中的模塊結(jié)構(gòu)特性;文獻(xiàn)［6］詳細(xì)論證了中國鐵路網(wǎng)絡(luò)的加權(quán)特性以及網(wǎng)絡(luò)中的模塊結(jié)構(gòu).但是，這些研究成果只涉及交通網(wǎng)絡(luò)模塊結(jié)構(gòu)的論證和描述，并未提出具體的城市路網(wǎng)模塊結(jié)構(gòu)劃分和評價(jià)方法，難以體現(xiàn)出模塊結(jié)構(gòu)劃分在交通規(guī)劃與設(shè)計(jì)上的應(yīng)用價(jià)值.

當(dāng)前，復(fù)雜網(wǎng)絡(luò)模塊結(jié)構(gòu)劃分算法主要包括圖形分割算法和分級聚類算法［7］.根據(jù)從網(wǎng)絡(luò)中添加或刪除邊，分級聚類算法可分為凝聚算法和分裂算法.分裂算法以 GN(Girvan-Newman)算法［8］為代表，其準(zhǔn)確性高，時(shí)間復(fù)雜度低，適合于中小型復(fù)雜網(wǎng)絡(luò).在GN算法中，為解決模塊結(jié)構(gòu)劃分何時(shí)終止的問題，引進(jìn)了一個(gè)衡量網(wǎng)絡(luò)劃分質(zhì)量的標(biāo)準(zhǔn)——模塊度.為了使GN算法能應(yīng)用于大規(guī)模復(fù)雜網(wǎng)絡(luò)，在GN算法的基礎(chǔ)上進(jìn)行了多種改進(jìn)［9-13］，但只是改進(jìn)了算法實(shí)現(xiàn)規(guī)則，并未對模塊度函數(shù)進(jìn)行更深入的研究.目前尚未見到城市路網(wǎng)模塊度的相關(guān)研究.

以上算法和模塊度研究的對象都是無權(quán)無向的抽象復(fù)雜網(wǎng)絡(luò)，研究方向主要側(cè)重于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)方面，尚未考慮實(shí)際交通網(wǎng)絡(luò)的特性，例如，流量和流向分布、用戶對路徑的選擇等.因此，這些算法和模塊度函數(shù)不能直接應(yīng)用于城市路網(wǎng).

Hub路段是指那些一旦失效就會導(dǎo)致其他路段相繼失效，進(jìn)而產(chǎn)生連鎖反應(yīng)，最終導(dǎo)致整個(gè)路網(wǎng)癱瘓的關(guān)鍵路段，這種由Hub路段失效引起的路網(wǎng)癱瘓現(xiàn)象稱為路網(wǎng)的級聯(lián)失效.如何識別路網(wǎng)中的Hub路段并進(jìn)行應(yīng)急處理，已成為級聯(lián)失效研究中的關(guān)鍵問題.為評價(jià)路段的重要性，文獻(xiàn)［14］提出了一種基于路段選擇概率的路段重要性評價(jià)方法;文獻(xiàn)［15］指出應(yīng)從路段失效的后果來評價(jià)路段重要性.以上方法對確定路段重要性都具有重要的理論和實(shí)際意義，但這些方法只考慮了路段失效后對流量分布造成的影響，并沒有詳細(xì)考慮路網(wǎng)的拓?fù)浣Y(jié)構(gòu)特性所起的作用.

本文基于GN算法思想，結(jié)合城市交通網(wǎng)絡(luò)的特點(diǎn)，考慮路段權(quán)重和阻抗、交通流向和出行者的出行選擇行為等特征，提出一種適用于城市路網(wǎng)模塊結(jié)構(gòu)劃分及Hub路段診斷的算法——GN-T算法.該算法通過逐條移除介值最大的路段實(shí)現(xiàn)模塊結(jié)構(gòu)的劃分，從而診斷出路網(wǎng)中的Hub路段，其中，各路段的介值在每次移除后需要重新計(jì)算.同時(shí)，為確定路網(wǎng)模塊結(jié)構(gòu)的最佳數(shù)量，提出了一個(gè)改進(jìn)的模塊度函數(shù)，并以武昌城市路網(wǎng)為例對算法的有效性進(jìn)行驗(yàn)證.結(jié)果表明GN-T算法能較準(zhǔn)確地探測出路網(wǎng)中的模塊結(jié)構(gòu)并診斷出Hub路段.

1 GN-T算法

1.1 變量符號和術(shù)語定義

考慮有向城市路網(wǎng)G(N，A)，其中:N表示交叉口集合，A表示路段集合，且路段p∈A.O和D分別表示起點(diǎn)和終點(diǎn)集合，起點(diǎn)r∈O，終點(diǎn)s∈D.GN-T算法的主要變量符號和術(shù)語定義如下:

(1)Bp為路段介數(shù)，即路網(wǎng)中所有OD對之間的最短路徑通過路段p的次數(shù).

(2)wp為路段權(quán)重系數(shù)，表示不同等級和方向的路段p在路網(wǎng)中的相對作用大小.

(3)cp為路段介值，表示路段p的介數(shù)與路段權(quán)重系數(shù)的乘積.

(4)wij為模塊結(jié)構(gòu)i與j之間所有路段權(quán)重系數(shù)的平均值.

(5)wii為模塊結(jié)構(gòu)i內(nèi)所有路段權(quán)重系數(shù)的平均值.

(6)移除路段為算法每次迭代結(jié)果中介值最大的路段，也是路網(wǎng)中最有可能發(fā)生堵塞的路段.

(7)移除路段的順序是算法在每次迭代過程中介值最大的路段依次被移除的順序，移除路段的順序越靠前表明該路段在路網(wǎng)中越容易堵塞.

1.2 算法原理

城市路網(wǎng)由不同的模塊結(jié)構(gòu)組成，連接各模塊結(jié)構(gòu)的路段稱為連接路段.

由于不同模塊結(jié)構(gòu)的節(jié)點(diǎn)之間的最短路必經(jīng)過連接路段，因此，連接路段將比模塊結(jié)構(gòu)內(nèi)的路段具有更大的介值，介值越大，表明各OD對之間的最短路徑通過該路段次數(shù)越多，通過該路段的交通量就可能越大，飽和度也越高，該路段也就更容易發(fā)生交通堵塞，在路網(wǎng)中的重要程度也越大.通過逐步移除這些介值最大的路段，可以將路網(wǎng)分割成不同的子網(wǎng)，即模塊結(jié)構(gòu)，而這些移除的路段很可能就是路網(wǎng)中的Hub路段.在城市路網(wǎng)中，快速路和主干路用于連接不同的區(qū)域，其路段交通量較大、飽和度較高、交通堵塞頻繁發(fā)生，極有可能成為路網(wǎng)中的Hub路段.

1.3 算法流程

基于GN-T算法，采用C++編寫了算法程序，并用JAVA語言編制了應(yīng)用軟件.

算法基本流程的步驟如下:

(1)程序初始化，讀取節(jié)點(diǎn)坐標(biāo)文件，得出城市路網(wǎng)的拓?fù)浣Y(jié)構(gòu)圖;

(2)讀取阻抗矩陣T，其中tp表示路段p上的阻抗，路阻函數(shù)采用BPR函數(shù);

(3)讀取路段權(quán)重系數(shù)矩陣W，其中wp表示路段p的權(quán)重系數(shù);

(4)利用廣度優(yōu)先搜索算法求得任意OD對之間的最短路徑，獲得每個(gè) OD對的最短路矩陣S;

(5)根據(jù)路段介數(shù)的定義，利用已經(jīng)獲得的最短路徑矩陣S求出各路段p的介數(shù)Bp;

(6)計(jì)算各路段介值cp，移除路網(wǎng)中介值最大的路段;

(7)計(jì)算城市路網(wǎng)模塊度函數(shù)，求得此時(shí)路網(wǎng)的模塊度Q;

(8)獲得模塊結(jié)構(gòu)數(shù)目N后，轉(zhuǎn)步驟(2)，讀取路網(wǎng)中更新的阻抗矩陣T和路段權(quán)重系數(shù)矩陣W;

(9)若路網(wǎng)中還有路段未被移除，轉(zhuǎn)步驟(2);否則，轉(zhuǎn)步驟(10);

(10)根據(jù)模塊度Q，獲得模塊度與模塊個(gè)數(shù)的關(guān)系變化圖以及城市路網(wǎng)分塊圖，算法結(jié)束.

1.4 算法關(guān)鍵點(diǎn)

由于算法的實(shí)現(xiàn)較為復(fù)雜，下面對算法中的幾個(gè)關(guān)鍵點(diǎn)進(jìn)行詳細(xì)說明:

(1)路段介數(shù)的計(jì)算通過廣度優(yōu)先搜索算法實(shí)現(xiàn).假設(shè)在每個(gè)時(shí)間點(diǎn)，所有OD對之間有1個(gè)單位的流量產(chǎn)生，且交通分配服從用戶均衡原則.根據(jù)所有OD對間的最短路計(jì)算路段介數(shù)和介值，將介值最大的路段從路網(wǎng)中移除，從而得到少了一條路段的新路網(wǎng).在新路網(wǎng)中，OD需求不變，交通需求重新分配，路段介數(shù)和介值也重新計(jì)算，新一輪計(jì)算結(jié)果中介值最大的路段也被刪去，如此類推，直到各個(gè)交叉口相互分離為止.

(2)路段介數(shù)可以理解為路段流量，而權(quán)重系數(shù)反映的是該路段在路網(wǎng)中所起作用的大小.本文把快速路單向3車道的通行能力歸一化為1，作為標(biāo)準(zhǔn)權(quán)重系數(shù)，把主干路單向的通行能力、次干路單向的通行能力、支路單向的通行能力與快速路單向3車道的通行能力的比值作為各自的權(quán)重系數(shù).

(3)路段介值定義為路段介數(shù)和權(quán)重系數(shù)的乘積，不僅體現(xiàn)了流量的作用，還考慮了路網(wǎng)拓?fù)浣Y(jié)構(gòu)的影響.例如，在城市路網(wǎng)中，某輪搜索得出介數(shù)最大的路段為一條單向2車道的快速路路段，其介數(shù)為 2400，權(quán)重系數(shù)為0.67，通行能力為3600 pcu;介數(shù)第2的路段為一條單向3車道的主干路路段，其介數(shù)為2100，權(quán)重系數(shù)為0.83，通行能力為3000 pcu.如果以介數(shù)直接作為路段重要程度的評判標(biāo)準(zhǔn)，就應(yīng)把快速路刪去，但此時(shí)快速路的飽和度為0.67，主干路的飽和度為0.70，主干路堵塞程度更嚴(yán)重，則應(yīng)刪去主干路.如果考慮路網(wǎng)拓?fù)浣Y(jié)構(gòu)，即加入路段的權(quán)重系數(shù)，以介值作為路段重要程度的標(biāo)準(zhǔn)，則快速路的介值為1608，主干路的介值為1743，顯然主干路比快速路重要，應(yīng)刪去主干路，這與前面由路段飽和度得出的結(jié)論是一致的.因此，介值從流量和路網(wǎng)拓?fù)浣Y(jié)構(gòu)兩方面反映出路段的重要程度，更符合實(shí)際情況.

2 改進(jìn)的模塊度函數(shù)

為了獲得最優(yōu)的城市路網(wǎng)模塊結(jié)構(gòu)數(shù)量，本文結(jié)合城市路網(wǎng)自身的特點(diǎn)，加入路段權(quán)重系數(shù)矩陣，對模塊度函數(shù)進(jìn)行了改進(jìn)，以對城市路網(wǎng)模塊結(jié)構(gòu)劃分的優(yōu)劣進(jìn)行評判.

假設(shè)城市路網(wǎng)劃分為k個(gè)模塊結(jié)構(gòu)，定義兩個(gè)k×k維的對稱矩陣:

式中:eij為網(wǎng)絡(luò)中連接兩個(gè)不同模塊結(jié)構(gòu)i和j中節(jié)點(diǎn)的路段數(shù)占所有路段數(shù)的比例;

其中:n為連接模塊結(jié)構(gòu)i和j之間的路段編號;

q為連接模塊結(jié)構(gòu)i與j之間的路段總數(shù)(包括原始路網(wǎng)中的所有路段，不考慮是否被移除，即模塊度是根據(jù)完整的原始路網(wǎng)來計(jì)算的).

定義每行(列)中各元素與對應(yīng)路段平均權(quán)重系數(shù)的乘積之和為

式中:

Ai為連接模塊結(jié)構(gòu)i中節(jié)點(diǎn)與模塊結(jié)構(gòu)j中節(jié)點(diǎn)的路段數(shù)占所有路段數(shù)的比例.

定義模塊度為

式(5)表示網(wǎng)絡(luò)中連接兩個(gè)同類型節(jié)點(diǎn)的路段(模塊結(jié)構(gòu)內(nèi)部路段)的比例與同樣模塊結(jié)構(gòu)下任意連接這兩個(gè)節(jié)點(diǎn)的路段的期望值之間的差值.如果模塊結(jié)構(gòu)內(nèi)部路段數(shù)的比例不大于任意連接時(shí)的期望值，則Q=0.Q的上限為1，Q越大，說明城市路網(wǎng)的模塊結(jié)構(gòu)越顯著.文獻(xiàn)［8］的研究表明，Q最大時(shí)所對應(yīng)的模塊結(jié)構(gòu)數(shù)就是網(wǎng)絡(luò)中最優(yōu)的模塊結(jié)構(gòu)數(shù).在實(shí)際網(wǎng)絡(luò)中，Q值通常位于0.3 ～0.7 之間.

3 實(shí)例分析

本文選取武漢市武昌區(qū)交通網(wǎng)絡(luò)進(jìn)行實(shí)證研究.把信號交叉口抽象為節(jié)點(diǎn)，交叉口之間的路段抽象為邊，用AutoCAD2007繪制出2011年武昌主城區(qū)內(nèi)部交通網(wǎng)絡(luò)系統(tǒng)圖.該路網(wǎng)由快速路、主干路、次干路和支路構(gòu)成，如圖2所示.其中，路網(wǎng)節(jié)點(diǎn)總數(shù)為238個(gè)，邊總數(shù)為984條.

調(diào)查得到了武昌區(qū)路網(wǎng)中不同等級道路的車道數(shù)、設(shè)計(jì)車速及單車道實(shí)際通行能力數(shù)據(jù)，見表1.

根據(jù)表1數(shù)據(jù)，把某單向3車道快速路的通行能力進(jìn)行標(biāo)準(zhǔn)化處理，作為快速路路段的權(quán)重系數(shù);其他道路路段通行能力與該快速路通行能力的比值作為路段權(quán)重系數(shù)，計(jì)算結(jié)果見表2.

在軟件中導(dǎo)入節(jié)點(diǎn)坐標(biāo)文件、時(shí)間矩陣文件和路段權(quán)重系數(shù)矩陣文件，程序運(yùn)行結(jié)果如圖3、圖4和表3所示.

武昌城市路網(wǎng)模塊結(jié)構(gòu)劃分的結(jié)果如圖4所示.圖4中紅色線段表示的的路段就是路網(wǎng)中被移除的路段，通過移除這些路段就可以劃分出路網(wǎng)的模塊結(jié)構(gòu).對應(yīng)的用AutoCAD2007繪制的模塊結(jié)構(gòu)劃分效果圖如圖5所示.

圖2 2011年武昌主城內(nèi)部交通網(wǎng)絡(luò)圖Fig.2 Map of Wuchang urban traffic network in 2011

表1 武昌各等級道路屬性Tab.1 Properties of roads of different grades in Wuchang urban traffic network

表2 武昌各等級道路路段權(quán)重系數(shù)Tab.2 Weight coefficients of roads of different grades in Wuchang urban traffic network

圖3 模塊度-模塊結(jié)構(gòu)數(shù)曲線Fig.3 Modularity vs.number of modular structures

圖4 結(jié)果圖及移除路段Fig.4 The resultant map and removed links

表3 路網(wǎng)中移除的路段(Hub路段)及順序Tab.3 The removed links(hub links)and their removal order

根據(jù)GN-T算法原理，移除的路段很可能就是武昌城市路網(wǎng)中的Hub路段，在程序運(yùn)行過程中移除的路段和順序見表3.根據(jù)調(diào)查所得資料顯示，表3中帶有#的路段均為武昌城市路網(wǎng)中的快速路和主干路，是武昌城市路網(wǎng)中的關(guān)鍵路段.目前這些路段經(jīng)常處于堵塞狀態(tài)，特別是在出行高峰期間，這些路段均出現(xiàn)不同程度的堵塞，而且與其連接的路段也由于受到波及而進(jìn)入堵塞狀態(tài).

在最嚴(yán)重的情況下，武昌路網(wǎng)中接近四分之一的交叉口處于短時(shí)癱瘓狀態(tài).而沒有標(biāo)記的路段均為主干路或次干路，路段飽和度均為0.8左右，在高峰期間也會陷入短時(shí)堵塞狀態(tài).究其原因是目前這些路段交通流過大，非機(jī)動車及行人交通在交叉口和路段中違法穿插，加之地鐵或道路施工使得某些路段封閉了近一半的車道、信號交叉口控制不協(xié)調(diào)等原因進(jìn)一步降低了路段和交叉口的通行能力，導(dǎo)致交通供需不平衡，從而引起車輛排隊(duì)堵塞.

圖5 9個(gè)模塊結(jié)構(gòu)Fig.5 Nine modular structures

從上述分析可以看出，GN-T算法所得的結(jié)果與實(shí)際情況基本相符，該算法能夠較準(zhǔn)確地診斷出武昌城市路網(wǎng)中的Hub路段，說明該算法在實(shí)際應(yīng)用中是有效的.

4 結(jié)束語

本文基于復(fù)雜網(wǎng)絡(luò)模塊結(jié)構(gòu)理論，結(jié)合城市路網(wǎng)的特點(diǎn)和運(yùn)行特性，提出了劃分城市路網(wǎng)模塊結(jié)構(gòu)的GN-T算法，并應(yīng)用于武昌城市路網(wǎng)模塊結(jié)構(gòu)探測及Hub路段診斷中.程序運(yùn)行所得結(jié)果表明，武昌城市路網(wǎng)表現(xiàn)出較明顯的模塊結(jié)構(gòu)特性，該算法診斷出的武昌城市路網(wǎng)中的Hub路段與實(shí)際情況相符，驗(yàn)證了GN-T算法適用于劃分該路網(wǎng)的模塊結(jié)構(gòu).

揭示復(fù)雜網(wǎng)絡(luò)中的模塊結(jié)構(gòu)已成為理解網(wǎng)絡(luò)功能的有力工具.在對城市路網(wǎng)模塊結(jié)構(gòu)進(jìn)行了有效劃分并診斷出Hub路段后，應(yīng)對路網(wǎng)拓?fù)浣Y(jié)構(gòu)與網(wǎng)絡(luò)功能之間的關(guān)系作進(jìn)一步探究，以更好地掌握城市交通運(yùn)行機(jī)理，揭示城市路網(wǎng)級聯(lián)失效過程的機(jī)理，并做出相應(yīng)的應(yīng)急處理方案，這將是未來的研究方向.

［1］GUIMERA R，MOSSA S，TURTSCHI A，et al.The world-wide air transportation network:anomalous centrality， community structure， and cities'global roles［C］∥ Proceedings of the National Academy of Sciences USA.Washington D.C.:［s.n.］，2005:7794-7799.

［2］盧守峰，楊兆升，劉喜敏.基于復(fù)雜性理論的城市交通系統(tǒng)研究［J］.吉林大學(xué)學(xué)報(bào):工學(xué)版，2006，36(3):153-156.LU Shoufeng，YANG Zhaosheng，LIU Ximin.Research on urban traffic system based on complexity theory［J］.Journal of Jilin University:Engineering and Technology Edition，2006，36(3):153-156.

［3］SEN P，DASGUPTA S，CHATTERJEE A，et al.Small world properties of the Indian railway network［J］.Physical Review E，2003，67:036106.

［4］SIENKIEWICZ J，HOLYST J A.Statistical analysis of 22 public transport networks in Poland［J］.Physical Review E，2005，72:046127.

［5］PORTA S，CRUCITTI P，LATORA V.The network analysis of urban streets:a dualapproach［J］.Environment and Planning B:Planning and Design，2006，33(5):705-725.

［6］LI X G，GAO Z Y，LI K P，et al.The relationship between microscopic dynamics in traffic flow and complexity in network［J］.Physical Review E，2007，76:016110.

［7］汪小帆，陳關(guān)榮，李翔.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］.北京:清華大學(xué)出版社，2006:156-162.

［8］NEWMAN M E J，GIRVAN M.Finding and evaluating community structure in networks［J］.Physical Review E，2004，69:026113.

［9］RADICCHI F，CASTELLANO C，CECCONI F，et al.Defining and identifying communities in networks［J］.Proc.Natl.Acad.Sci.，2004，101:2658-2663.

［10］CLAUSET A，NEWMAN M E J，MOORE C.Finding community structure networks［J］.Physical Review E，2004，70:066111.

［11］CAPOCCI A，SERVEDIO V D P，CALDARELLI G，et al.Detecting communities in large networks［J］.Computer Science，2004，3243:181-187.

［12］FORTUNATE S，LATORA V，MARICHIORI M.A method to find community structures based on information centrality［J］.Physical Review E，2004，70:056104.

［13］DUCH J， ARENASA. Community detection in complex networks using extreme optimization［J］.Physical Review E，2005:72:027104.

［14］TAYLOR M A P，D'ESTE G M.Critical infrastructure and transport network vulnerability:developing a method for diagnosis and assessment［C］∥Proceedings of the Second International Symposium on Transportation Network Reliability (INSTR).Christchurch:［s.n.］，2004:96-102.

［15］JENELIUS E，PERERSEN T， MATTSSON L G.Importance and exposure in road network vulnerability analysis［J］.Transportation Research Part A，2006，40:537-560.