基于復雜網絡理論的城市路網結構特性分析

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

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

基于復雜網絡理論的城市路網結構特性分析

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

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

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

城市路網;復雜網絡;小世界;結構特性

自然界和現實社會中存在的許多復雜系統都可以通過網絡描述。20世紀90年代以前對網絡的研究僅局限于幾十個或者上百個頂點的圖。隨著復雜網絡中小世界效應和無標度特性的發現,人們分析網絡的方法亦發生了改變,即從分析頂點數較少的圖及圖中頂點和邊的屬性轉變為研究大量頂點數的圖的統計特性[1]。目前這種研究方法已經滲透到各個學科領域,如社會科學中人際關系網、Internet/ WWW網,生命科學領域的神經網絡,交通領域的公交網絡等。

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

1 復雜網絡的統計分析方法

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

圖1 WS小世界網絡模型Fig.1 Themodel of WS small world network

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

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

式中:n為網絡節點個數;dij為第i個節點與第j個節點之間的最短路徑長度。

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

式中:mi為頂點vi的相鄰節點數;li是這mi個節點間的連接邊數。

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

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

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

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

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

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

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

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

2 城市道路網絡建模方法

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

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

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

3 實證分析

3.1 數據準備與處理

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

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

3.2 網絡特征值計算與分析

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

表1 網絡特征值計算結果Table 1 The result of network characteristic value

3.3 節點的度分布

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

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

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

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

3.4 網絡同配/異配性

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

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

3.5 網絡彈性分析

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

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

圖8 路網規模變化Fig.8 The change of size of street network

4 結語

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

交通擁堵等問題提供了理論依據。

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

[2] 汪小帆,李翔.復雜網絡理論及其應用[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] 高中華,李滿春,陳振杰,等.城市道路網絡的小世界特征研究[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] 張勇,楊曉光.城市路網的復雜網絡特性及可靠性仿真分析[J].系統仿真學報,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);江蘇省資源環境信息工程重點實驗室開放基金項目(JS200901);中國博士后科學基金項目(20090461019)

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