基于復雜網(wǎng)絡理論的城市路網(wǎng)結構特性分析

趙 玲,鄧 敏,王佳璆,彭東亮

(中南大學信息物理工程學院測繪與國土信息工程系,湖南長沙410083)

基于復雜網(wǎng)絡理論的城市路網(wǎng)結構特性分析

趙 玲,鄧 敏,王佳璆,彭東亮

(中南大學信息物理工程學院測繪與國土信息工程系,湖南長沙410083)

復雜網(wǎng)絡理論為研究網(wǎng)絡的拓撲結構和統(tǒng)計特征提供了新途徑。該文將復雜網(wǎng)絡理論應用于城市路網(wǎng),首先探討了復雜網(wǎng)絡的統(tǒng)計分析方法,選擇特征路徑長度、聚類系數(shù)、節(jié)點的度分布、網(wǎng)絡同配/異配性、網(wǎng)絡彈性作為度量指標。在總結分析現(xiàn)有路網(wǎng)建模方法基礎上,采用基于角度綜合的對偶方法進行路網(wǎng)建模。最后以長沙市路網(wǎng)為例,利用A rcGIS和MatLab分別處理路網(wǎng)空間數(shù)據(jù)和計算統(tǒng)計指標,分析其小世界特性、無標度特性以及同配異配性、網(wǎng)絡彈性等結構特性,得出了一些有益的結論。

城市路網(wǎng);復雜網(wǎng)絡;小世界;結構特性

自然界和現(xiàn)實社會中存在的許多復雜系統(tǒng)都可以通過網(wǎng)絡描述。20世紀90年代以前對網(wǎng)絡的研究僅局限于幾十個或者上百個頂點的圖。隨著復雜網(wǎng)絡中小世界效應和無標度特性的發(fā)現(xiàn),人們分析網(wǎng)絡的方法亦發(fā)生了改變,即從分析頂點數(shù)較少的圖及圖中頂點和邊的屬性轉變?yōu)檠芯看罅宽旤c數(shù)的圖的統(tǒng)計特性[1]。目前這種研究方法已經(jīng)滲透到各個學科領域,如社會科學中人際關系網(wǎng)、Internet/ WWW網(wǎng),生命科學領域的神經(jīng)網(wǎng)絡,交通領域的公交網(wǎng)絡等。

城市道路是支撐城市發(fā)展的骨架,近年來隨著我國城市化進程的快速發(fā)展以及政府對交通的大量投入,城市路網(wǎng)規(guī)模發(fā)展迅速,但是路網(wǎng)的發(fā)展始終無法緩解城市交通擁堵等問題。本文以城市路網(wǎng)為研究對象,采用對偶方法對其建模,利用復雜網(wǎng)絡理論的統(tǒng)計指標定量分析城市路網(wǎng)的結構特性,為進一步研究城市路網(wǎng)結構布局、道路交通性能以及解決城市交通堵塞等實際問題提供理論依據(jù)。

1 復雜網(wǎng)絡的統(tǒng)計分析方法

一個網(wǎng)絡是由節(jié)點和連接節(jié)點之間的邊組成。根據(jù)不同的連接方式,人們提出了不同的網(wǎng)絡模型,如規(guī)則網(wǎng)絡(Regular Networks)、隨機網(wǎng)絡(Random Networks)、小世界網(wǎng)絡(Small-wo rld Netwo rks)和無標度網(wǎng)絡(Scale-free Netwo rks)等。規(guī)則網(wǎng)絡中的節(jié)點數(shù)和邊數(shù)固定,每個節(jié)點都有相同的連接數(shù),即每個節(jié)點的度相同。隨機網(wǎng)絡的邊數(shù)具有不確定性,可視為一個概率事件。小世界網(wǎng)絡則是一種拓撲結構既不完全規(guī)則也不完全隨機,而是介于二者之間的網(wǎng)絡模型。它以概率 p隨機選擇規(guī)則網(wǎng)絡中的邊重新連接,即以“隨機重連”的方法構建網(wǎng)絡,體現(xiàn)了從規(guī)則到全隨機的演變(圖1)。這種網(wǎng)絡具有一個典型的特征:網(wǎng)絡上的節(jié)點在局部緊密相連,具有較大的聚類系數(shù),同時網(wǎng)絡平均最短距離較小,即從一個節(jié)點到任一其它節(jié)點只需經(jīng)過少量節(jié)點。1999年,Barabasi和A lbert指出:許多實際網(wǎng)絡的度分布并不呈現(xiàn)Poisson分布,而是冪律形式,這類網(wǎng)絡被稱為無標度網(wǎng)絡[2]。無標度網(wǎng)絡的主要特點為極少數(shù)節(jié)點有大量的連接,而大多數(shù)節(jié)點只有很少的連接。

圖1 WS小世界網(wǎng)絡模型Fig.1 Themodel of WS small world network

小世界網(wǎng)絡模型和無標度網(wǎng)絡模型的提出可以看做復雜網(wǎng)絡研究的開始,描述復雜網(wǎng)絡特性的屬性主要包括:特征路徑長度、聚類系數(shù)、節(jié)點的度分布、網(wǎng)絡同配或異配性以及網(wǎng)絡彈性度量。

(1)特征路徑長度也稱為網(wǎng)絡的平均路徑長度,是指網(wǎng)絡中所有節(jié)點對之間最短路徑長度的平均值,可表達為:

式中:n為網(wǎng)絡節(jié)點個數(shù);dij為第i個節(jié)點與第j個節(jié)點之間的最短路徑長度。

(2)聚類系數(shù)用于衡量網(wǎng)絡中“朋友的朋友也是朋友”現(xiàn)象。假設網(wǎng)絡中一個節(jié)點i有mi個鄰接節(jié)點,則節(jié)點i的聚類系數(shù)是指這mi個鄰接節(jié)點之間實際存在的邊數(shù)與最大可能邊數(shù)的比值。網(wǎng)絡的聚類系數(shù)C則是網(wǎng)絡中所有節(jié)點聚類系數(shù)的平均值。通常用聚類系數(shù)刻畫網(wǎng)絡的聚集情況。例如,在交通網(wǎng)絡中,較大的聚類系數(shù)體現(xiàn)了局部交通具有較好的連通性。

式中:mi為頂點vi的相鄰節(jié)點數(shù);li是這mi個節(jié)點間的連接邊數(shù)。

聚類系數(shù)與特征路徑長度是判定小世界網(wǎng)絡特性的兩個主要指標。若網(wǎng)絡同時具有較小的特征路徑長度和較大的聚類系數(shù),即為小世界網(wǎng)絡。一般可表示為:

式中:LRandom和CRandom分別代表具有相同規(guī)模的隨機網(wǎng)絡的特征路徑長度和聚類系數(shù),可表達為[3]:

(3)節(jié)點的度分布。網(wǎng)絡中節(jié)點的度是指與節(jié)點直接相連的邊的數(shù)量。在不同的網(wǎng)絡中,度的含義也不同。在城市路網(wǎng)中,度越大的道路通常代表連通性較好的關鍵道路。度分布則是指度為k的節(jié)點數(shù)(nk)占所有節(jié)點數(shù)(n)的比值,可表示為:

在Erdos和Renyi研究的隨機網(wǎng)絡中,節(jié)點的度分布一般服從二項分布或大 n極限下的 Poisson分布。但研究發(fā)現(xiàn),現(xiàn)實世界中大多數(shù)網(wǎng)絡的節(jié)點的度分布與隨機網(wǎng)絡截然不同,它遠遠偏離Poisson分布,明顯向右傾斜,服從冪律分布,即 P(k)～k-a,其表現(xiàn)是在累積度分布的雙倍刻度尺上近似呈現(xiàn)一條右傾的直線[1]。這里,累積度分布是指度大于或等于k的概率。

(4)網(wǎng)絡的同配/異配性可用來揭示網(wǎng)絡節(jié)點與節(jié)點之間的相關性。對于度數(shù)高的節(jié)點,其鄰居節(jié)點的度分布情況如何?一種方法可以計算鄰居節(jié)點的平均度指標,它是該節(jié)點的度 k的函數(shù)。當曲線是一條隨k遞增的曲線,則稱為同配性網(wǎng)絡,反之為異配性網(wǎng)絡。另一種方法可以通過計算網(wǎng)絡的同配性系數(shù)來刻畫,該系數(shù)可以表達為:

式中:ji和ki分別為第i條邊的兩個端點的度數(shù)。當系數(shù) r>0時,該網(wǎng)絡為同配性;當系數(shù) r<0時,網(wǎng)絡為異配性。

(5)網(wǎng)絡彈性研究的是網(wǎng)絡在節(jié)點失效或受到有意攻擊的情況下所表現(xiàn)出的特征。大部分網(wǎng)絡的功能都依賴于其關聯(lián)性,即依賴于節(jié)點與節(jié)點之間的路徑。如果網(wǎng)絡節(jié)點被刪除,將會導致節(jié)點之間的路徑長度增加,最終使節(jié)點之間的連接中斷,從而使整個網(wǎng)絡不連通。因此,網(wǎng)絡的彈性可以根據(jù)網(wǎng)絡平均路徑長度和網(wǎng)絡規(guī)模的變化來衡量,可以表達為:

式中:f表示刪除的節(jié)點數(shù)占原網(wǎng)絡總節(jié)點數(shù)的比例;Δs表示刪除節(jié)點后的最大連通子圖的變化;Δl表示平均路徑長度的變化。對于不同的節(jié)點刪除方式和不同結構的網(wǎng)絡其彈性度也不同。例如,可以從網(wǎng)絡中隨機刪除頂點,或者刪除一些指定節(jié)點,或者按照某一類別順序刪除節(jié)點等。研究發(fā)現(xiàn),無標度網(wǎng)絡對于意外故障有很強的彈性,但對于有意的攻擊卻很脆弱。

2 城市道路網(wǎng)絡建模方法

將城市道路網(wǎng)絡的拓撲結構抽象為網(wǎng)絡模型,目前主要有兩種方法:一種為主方法(Primal app roach)[4-6],是將道路的交叉口抽象為圖的節(jié)點,連接交叉口之間的路段抽象為邊或弧(圖2a1);這種方法的特點是簡單直觀,保留了較完整的地理相關性,是傳統(tǒng)交通網(wǎng)絡建模方法,也是目前大部分GIS軟件所采用的建模方法。另一種為對偶法(Dual app roach)[7,8],可以認為是主方法的對偶,即將道路抽象為節(jié)點,道路與道路的連接關系表示為圖的邊或弧。一條完整道路的構建是將連續(xù)的路段按一定的規(guī)則綜合而成,目前主要有軸線法[9]、名稱法[10]和角度法[7]。其中,軸線法采用軸線代表道路,是依據(jù)人的視覺將近似直線的路段合并為一條道路并用一條軸線表示(圖2b1);名稱法是指在合并路段時依據(jù)道路的名稱,將具有相同名稱的路段連接在一起(圖2c1);角度法的合并原則是依據(jù)格斯塔的連續(xù)性原則,通過計算路段與路段的夾角,并根據(jù)設定的夾角閾值生成道路(圖2d1)。圖2a2、圖2b2、圖2c2、圖2d2則分別是以上網(wǎng)絡模型所對應的連接圖。

圖2 幾種道路網(wǎng)絡模型比較Fig.2 Comparison of several street network models

實踐中這兩種建模方法各有特點。主方法直觀簡單,保留了路網(wǎng)的布局特點;對偶法忽略了地理實體的一些地理意義,如地理位置、道路長寬等,更適合探索網(wǎng)絡結構下的功能意義。對偶法中合并路段的幾種方法也各有優(yōu)缺點。例如,軸線法軸線的生成主要依據(jù)人的視覺判斷,合并規(guī)則引入主觀因素,因此不同的人可能得到不同的軸線地圖,即方法不具有唯一性;名稱法的局限性在于合并規(guī)則完全依賴屬性信息,忽略了空間特性并喪失了直觀性,在缺少道路名稱信息或信息不準確的情況下無法完成;角度法的合并則完全從圖形角度考慮,不受人為因素和屬性因素影響。因此,本研究采用對偶法中的角度法。具體算法描述如下:1)依次搜索各節(jié)點,計算每個節(jié)點處路段與路段的夾角值。2)找出夾角值最大的兩條路段,判斷夾角是否大于120°,是則合并兩條路段,賦予相同的 ID,否則不合并,并標記線段為已訪問。繼續(xù)判斷夾角值次之的兩條路段,如此反復。如果此節(jié)點有奇數(shù)條邊,則將單獨的路段賦予最小的角度值,直到此節(jié)點所有路段都標記為已訪問。3)重復第1、2步,直到所有節(jié)點判斷完畢。

3 實證分析

3.1 數(shù)據(jù)準備與處理

在本文實驗中,城市道路網(wǎng)選用2009年長沙市交通地圖,在A rcGIS 9.X平臺下完成空間數(shù)據(jù)的采集、編輯、處理。通過數(shù)字化得到可編輯的GIS路網(wǎng)數(shù)據(jù),經(jīng)過拓撲檢查以消除冗余線段、懸掛點和懸掛線,刪除孤立線段,得到一個包含有289個節(jié)點、501個路段的路網(wǎng)圖。為了進一步分析道路的拓撲關系,依據(jù)格式塔連續(xù)性原則,采用夾角法將滿足條件的路段合并為一條完整的道路,合并后共有77條道路、277個節(jié)點(圖3a)。根據(jù)對偶法抽象原則將一條道路抽象為節(jié)點,而道路與道路的連接關系表示為圖的邊,得到相對應的連接圖(圖3b)。

圖3 長沙市路網(wǎng)及相對應的連接圖Fig.3 The Changsha street network and corresponding connection graph

3.2 網(wǎng)絡特征值計算與分析

根據(jù)連接圖,分別采用式(1)、式(2)得到路網(wǎng)的特征路徑長度和聚類系數(shù),相同規(guī)模隨機網(wǎng)絡的聚類系數(shù)和特征路徑長度由式(5)、式(6)計算得到,其結果列于表 1?？梢钥闯?C>>CRandom且 L≥LRandom,說明長沙市路網(wǎng)具有較小的特征路徑長度和較大的聚類系數(shù),是典型的小世界網(wǎng)絡。

表1 網(wǎng)絡特征值計算結果Table 1 The result of network characteristic value

3.3 節(jié)點的度分布

圖4a為節(jié)點的累積度分布圖,X軸表示節(jié)點的度,Y軸表示累積概率,約60%的道路節(jié)點的度低于平均值(7.2)。在實際路網(wǎng)中,這些度較低的道路主要具有補充連通整個城市網(wǎng)絡、完成局部交通的作用。只有不到40%的道路節(jié)點的度高于平均值,這些道路才是構成整個城市交通的骨干,是交通路徑轉換的主要道路,保證了整個路網(wǎng)的連通性。圖4b為累積度分布的log-log圖,圖形并不呈嚴格直線,在M atLab中對圖4a中的圖形進行擬合,發(fā)現(xiàn)圖形更符合指數(shù)分布:F(k)=1.32×e0.1665k,即長沙市路網(wǎng)的節(jié)點的度分布不滿足冪律分布,不是一個無標度網(wǎng)絡。

圖4 長沙市路網(wǎng)的累積度分布Fig.4 Cumulative degree distribution of Changsha street network

在路網(wǎng)中度最高的兩條線路,一條是繞城的二環(huán)線,與31條道路連接,另一條是貫穿長沙城南北的芙蓉路,與26條道路連接。從圖5中可知,長沙市道路節(jié)點的度與道路長度保持線性相關。道路長度必須與其容量相匹配,否則會降低其連通的有效性。

圖5 道路長度與節(jié)點的度的相關性Fig.5 The correlation of street length and degree

3.4 網(wǎng)絡同配/異配性

本研究通過計算節(jié)點的鄰居節(jié)點的平均度指標來分析長沙市道路與道路的相關性。圖6中 X軸表示節(jié)點的度(k),Y軸表示其鄰居節(jié)點的平均度(knn)。從圖6可以看出長沙市道路與道路相連的一種趨勢,度越大的節(jié)點其鄰居節(jié)點的平均度越小,即偏向與度數(shù)小的節(jié)點相連,是個異配性網(wǎng)絡。這是因為長沙市路網(wǎng)中只有少量道路的度較高,大量的道路度較低。

圖6 鄰居節(jié)點的平均度分布Fig.6 Average degree distribution of neighbor nodes

3.5 網(wǎng)絡彈性分析

本研究主要考查了度對網(wǎng)絡彈性的影響。根據(jù)對偶模型將道路按度從大到小排序,然后依次刪除道路,計算路網(wǎng)的規(guī)模以及路網(wǎng)的平均路徑長度,統(tǒng)計路網(wǎng)規(guī)模和平均路徑長度隨著節(jié)點數(shù)減少而產(chǎn)生的變化。如圖7所示,X軸為刪除節(jié)點的比例,Y軸為路網(wǎng)平均路徑長度,反映了度對平均路徑長度的影響。從圖7可看出,在刪除節(jié)點初期,網(wǎng)絡平均最短距離隨之增加,當刪除節(jié)點數(shù)達到總數(shù)的22%時,網(wǎng)絡平均路徑長度達到一個峰值,隨后呈下降趨勢。其原因是在道路堵塞或被破壞的初期,網(wǎng)絡平均路徑距離增加,而隨著道路的刪除,網(wǎng)絡分裂成多個孤立的路網(wǎng),網(wǎng)絡規(guī)模縮小引起平均路徑距離縮短,直到網(wǎng)絡崩潰。圖8為刪除節(jié)點比例與網(wǎng)絡規(guī)模的關系,可見路網(wǎng)規(guī)模的縮小與刪除節(jié)點比例呈線性關系。當刪除的節(jié)點為原來的30%時,路網(wǎng)規(guī)模大約只有初始的一半,達到崩潰的臨界點。

圖7 路網(wǎng)平均特征路徑長度變化Fig.7 The change of average path length of street network

圖8 路網(wǎng)規(guī)模變化Fig.8 The change of size of street network

4 結語

復雜網(wǎng)絡理論為研究網(wǎng)絡的拓撲結構特性和統(tǒng)計特征提供了新途徑。本文將復雜網(wǎng)絡理論應用于城市路網(wǎng),以長沙市路網(wǎng)為例,利用復雜網(wǎng)絡理論中的特征路徑長度、聚類系數(shù)、節(jié)點的度分布、同配/異配性指數(shù)、網(wǎng)絡彈性等指標定量分析城市路網(wǎng)的結構特性,揭示其復雜網(wǎng)絡特性。結果表明,長沙市路網(wǎng)是典型的小世界網(wǎng)絡,但不是無標度網(wǎng)絡,是異配性網(wǎng)絡,而且當按節(jié)點的度大小刪除道路時,刪除約30%時會使整個路網(wǎng)崩潰。上述結果為進一步研究長沙市路網(wǎng)結構布局、道路交通性能以及解決城市

交通擁堵等問題提供了理論依據(jù)。

[1] NEWMAN M E J.The structure and function of comp lex networks[J].SIAM Review,2003,45(2):167-256.

[2] 汪小帆,李翔.復雜網(wǎng)絡理論及其應用[M].北京:清華大學出版社,1996.27-29.

[3] WA TTS D J,STROGATZ S H.Collective dynamics of smallwo rld netwo rk[J].Nature,1998,393(4):440-442.

[4] PORTA S,CRUCITTI P,LA TORA V.The netwo rk analysis of urban streets:A p rimal app roach[J].Environment and Planning B:Planning and Design,2006,33(5):705-725.

[5] CRUCITTIP,LA TORA V.Centrality measures in spatial netwo rks of urban streets[J].Physical Review E,2006,73(3): (036125-1)-(036125-5).

[6] 高中華,李滿春,陳振杰,等.城市道路網(wǎng)絡的小世界特征研究[J].地理與地理信息科學,2007,23(4):97-101.

[7] PORTA S,CRUCITTI P,LA TORA V.The netwo rk analysis of urban streets:A dual app roach[J].Physica A,2006,369: 853-866.

[8] 張勇,楊曉光.城市路網(wǎng)的復雜網(wǎng)絡特性及可靠性仿真分析[J].系統(tǒng)仿真學報,2008,20(2):464-469.

[9] H ILL IER B,HANSON J.The Social Logic of Space[M].U K: Cambridge University Press,1984.218-224.

[10] JIANGB.A topological pattern of urban street networks:Universality and peculiarity[J].Physica A,2007,384:647-655.

Abstract:Comp lex netwo rk theo ry p rovides a new app roach for exp lo ring the topological structure and statistical character of urban street netwo rks.In this paper,comp lex netwo rk theo ry is app lied to urban street netwo rks.Firstly,some app roaches fo r analyzing comp lex netwo rks are described.Some indexes such as characteristic path length,clustering coefficient,degree distributions,assortative o r disassortative coefficient,network resilience are choose.Furthermore,themethodsof themodeling of urban street netwo rk are summarized,and the angle-based dualmethod is used.Finally,taking Changsha street networksas an examp le,p rocessing spatial data and statistical index based on A rcGISand MatLab,some comp lex network p ropertiesof Changsha street networks are analyzed and some conclusions are made.

Key words:urban street netwo rks;comp lex networks;small world;structural p roperty

Structural Property Analysis of Urban Street Networks Based on Complex Network Theory

ZHAO Ling,DENGM in,WANGJia-qiu,PENGDong-liang
(Info-physics Engineering Institute,Central South University,Changsha 410083,China)

TU 984.191

A

1672-0504(2010)05-0011-05

2010-04-27;

2010-07-05

地理空間信息工程國家測繪局重點實驗室開放基金項目(200916);江蘇省資源環(huán)境信息工程重點實驗室開放基金項目(JS200901);中國博士后科學基金項目(20090461019)

趙玲(1975-),女,博士研究生,講師,主要從事城市道路網(wǎng)絡空間分析等方面的研究。E-mail:ling_dang@163.com