宋海權(quán)，郭 進(jìn)，劉 剛

(1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610031；2.成都理工大學(xué) 地球科學(xué)學(xué)院，四川 成都 610031)

?

基于復(fù)雜網(wǎng)絡(luò)的城市道路重要度評(píng)價(jià)及路網(wǎng)自動(dòng)綜合方法

宋海權(quán)1，郭 進(jìn)1，劉 剛2

(1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610031；2.成都理工大學(xué) 地球科學(xué)學(xué)院，四川 成都 610031)

利用復(fù)雜網(wǎng)絡(luò)理論，構(gòu)建城市復(fù)雜路網(wǎng)模型，基于該模型從道路的結(jié)構(gòu)和功能特征角度，以連接度、介中心和接近度為度量指標(biāo)定義道路重要度評(píng)價(jià)模型，并顧及路網(wǎng)的整體形態(tài)及路網(wǎng)的拓?fù)溥B通性，提出基于復(fù)雜網(wǎng)絡(luò)理論的路網(wǎng)綜合算法。為檢驗(yàn)方法有效性，針對(duì)成都市道路網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)分析。實(shí)驗(yàn)結(jié)果表明，該道路重要度評(píng)價(jià)模型較好地反映道路在整個(gè)路網(wǎng)結(jié)構(gòu)和功能上的重要程度，復(fù)雜路網(wǎng)綜合算法能較好地保持原始路網(wǎng)的整體形態(tài)結(jié)構(gòu)特征。

路網(wǎng)綜合；道路重要度；復(fù)雜網(wǎng)絡(luò)；拓?fù)溥B通

路網(wǎng)綜合是自動(dòng)制圖綜合研究的重點(diǎn)和難點(diǎn)內(nèi)容之一，其目的是從大比例尺地圖上提取部分關(guān)鍵道路生成小比例尺路網(wǎng)結(jié)構(gòu)，并保持所選路網(wǎng)的拓?fù)溥B通[1-3]。從網(wǎng)絡(luò)科學(xué)的角度，路網(wǎng)綜合又屬于網(wǎng)絡(luò)壓縮研究的范疇。對(duì)于規(guī)模龐大、結(jié)構(gòu)復(fù)雜的城市路網(wǎng)而言，路網(wǎng)綜合的難點(diǎn)在于如何保持原始路網(wǎng)的整體形態(tài)結(jié)構(gòu)特征及拓?fù)溥B通。

目前，學(xué)者們已經(jīng)提出很多路網(wǎng)綜合方法[4-8]。現(xiàn)有方法主要是利用傳統(tǒng)圖論從路網(wǎng)幾何結(jié)構(gòu)、層次特征等方面研究路網(wǎng)綜合問題，然而較少顧及路網(wǎng)的整體形態(tài)結(jié)構(gòu)和功能特征。近年來，復(fù)雜網(wǎng)絡(luò)理論在復(fù)雜系統(tǒng)結(jié)構(gòu)及功能分析方面的優(yōu)勢(shì)日趨突出[9-12]，利用復(fù)雜網(wǎng)絡(luò)理論可以彌補(bǔ)傳統(tǒng)圖論在大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)分析中的不足[13]。研究認(rèn)為，利用復(fù)雜網(wǎng)絡(luò)理論可以更為合理、準(zhǔn)確地分析道路之間的連接關(guān)系及交通動(dòng)力學(xué)特性[8,13-15]。本文認(rèn)為，每條道路對(duì)整個(gè)路網(wǎng)而言在結(jié)構(gòu)和功能上都有不同程度的貢獻(xiàn)，這種貢獻(xiàn)可以通過相應(yīng)的結(jié)構(gòu)和功能評(píng)價(jià)指標(biāo)進(jìn)行度量。為此，本文將利用復(fù)雜網(wǎng)絡(luò)理論，引入節(jié)點(diǎn)連接度、介中心和接近度等指標(biāo)，考慮不同道路在結(jié)構(gòu)和功能上對(duì)路網(wǎng)的貢獻(xiàn)，建立道路在整個(gè)路網(wǎng)中的重要度評(píng)價(jià)模型，進(jìn)而提出一種基于復(fù)雜網(wǎng)絡(luò)理論的城市路網(wǎng)自動(dòng)綜合方法。

1 城市道路網(wǎng)絡(luò)對(duì)偶拓?fù)淠Ｐ?/h2>

在城市道路網(wǎng)絡(luò)建模方面，最常用的網(wǎng)絡(luò)拓?fù)浞椒ㄊ侵苯訉⒌缆烦橄鬄檫?或弧段)、交叉口抽象為節(jié)點(diǎn)，進(jìn)而建立具有地理空間意義的網(wǎng)絡(luò)模型。這種建模方法雖然可以較好地描述城市路網(wǎng)的幾何形態(tài)結(jié)構(gòu)，然而難以準(zhǔn)確反映道路之間的連接關(guān)系、結(jié)構(gòu)復(fù)雜性及道路的功能特征。利用基于對(duì)偶拓?fù)浞椒ǖ膹?fù)雜網(wǎng)絡(luò)理論可以很好地研究路網(wǎng)的結(jié)構(gòu)和功能復(fù)雜性。該建模方法將道路按路名映射為節(jié)點(diǎn)、交叉口映射為邊，進(jìn)而建立城市道路網(wǎng)絡(luò)的對(duì)偶拓?fù)淠Ｐ蚚16]。如圖1(a)為現(xiàn)實(shí)城市路網(wǎng)，且由9條道路構(gòu)成；(b)為采用傳統(tǒng)方法構(gòu)建的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其中1-9為道路名或編碼；(c)為基于傳統(tǒng)路網(wǎng)結(jié)構(gòu)建立的對(duì)偶拓?fù)淠Ｐ汀Ｑ芯勘砻?，利用?fù)雜網(wǎng)絡(luò)理論構(gòu)建的城市復(fù)雜路網(wǎng)模型能夠更加準(zhǔn)確地表達(dá)道路之間的連接關(guān)系，有助于深入分析路網(wǎng)的結(jié)構(gòu)和功能特征。圖2為成都市道路網(wǎng)絡(luò)結(jié)構(gòu)，其中(a)為幾何路網(wǎng)結(jié)構(gòu)，(b)為采用對(duì)偶拓?fù)錁?gòu)建的復(fù)雜路網(wǎng)模型。

(a)現(xiàn)實(shí)城市路網(wǎng)

(b)傳統(tǒng)方法構(gòu)建網(wǎng)圖1 城市道路網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>

(c)對(duì)偶拓?fù)淠Ｐ?/p>

(a)幾何道路網(wǎng)絡(luò)

(b)復(fù)雜路網(wǎng)模型

2 道路重要度評(píng)價(jià)方法

評(píng)價(jià)道路重要性對(duì)路網(wǎng)綜合至關(guān)重要，而針對(duì)復(fù)雜路網(wǎng)模型，則關(guān)鍵在于如何準(zhǔn)確評(píng)估節(jié)點(diǎn)的重要性。學(xué)者們?cè)诘缆分匾栽u(píng)價(jià)方面提出很多方法，這些方法主要集中在兩個(gè)方面：一方面，從道路等級(jí)的角度提取不同尺度下的道路；另一方面，將道路構(gòu)建成路劃，進(jìn)而通過評(píng)價(jià)路劃的重要性來提取關(guān)鍵道路?，F(xiàn)有方法主要是利用圖論和數(shù)學(xué)規(guī)劃理論分析道路的重要性[17]，較少綜合考慮道路結(jié)構(gòu)和功能特性。復(fù)雜網(wǎng)絡(luò)理論在網(wǎng)絡(luò)結(jié)構(gòu)及功能評(píng)價(jià)方面具有顯著優(yōu)勢(shì)。研究認(rèn)為，采用基于對(duì)偶拓?fù)涞膹?fù)雜網(wǎng)絡(luò)理論及其所提供的結(jié)構(gòu)化度量指標(biāo)可以更為合理、準(zhǔn)確地評(píng)估道路在整個(gè)路網(wǎng)中的交通特性及線路之間的連接關(guān)系。

2.1 評(píng)價(jià)指標(biāo)

1)節(jié)點(diǎn)度。度(或連接度，Degree)是網(wǎng)絡(luò)節(jié)點(diǎn)最為簡單而又最為重要的概念，是節(jié)點(diǎn)重要性度量的重要指標(biāo)之一。節(jié)點(diǎn)i的度定義為與該節(jié)點(diǎn)直接相連的其他節(jié)點(diǎn)的數(shù)量，一般用ki表示。研究普遍認(rèn)為，節(jié)點(diǎn)的連接度越高，則該節(jié)點(diǎn)相對(duì)越重要。

2.2 道路重要度評(píng)價(jià)模型

Mi=w1ki′+w2bi′+w3ci′.

(2)

式中:Mi為節(jié)點(diǎn)i的重要度；w1,w2,w3分別為節(jié)點(diǎn)度、介中心和接近度所占的權(quán)重。式(2)表明，該評(píng)價(jià)模型同時(shí)顧及道路的結(jié)構(gòu)和功能特征。在實(shí)驗(yàn)過程中，發(fā)現(xiàn)當(dāng)w1,w2,w3的取值相當(dāng)時(shí)(即w1=w2=w3)，評(píng)價(jià)結(jié)果較為合理、準(zhǔn)確。如圖3為利用本文方法提取的成都市路網(wǎng)的部分關(guān)鍵道路。結(jié)果顯示，所提取的關(guān)鍵道路較為準(zhǔn)確地反映了這些道路在整個(gè)城市路網(wǎng)中的重要性，這些道路在結(jié)構(gòu)和交通功能上都起到非常關(guān)鍵的作用。

圖3 關(guān)鍵道路提取結(jié)果

3 路網(wǎng)綜合方法

3.1 復(fù)雜路網(wǎng)自動(dòng)綜合算法

路網(wǎng)綜合的目的在于提取不同尺度下的重要道路構(gòu)建新的路網(wǎng)結(jié)構(gòu)。為此，本文提出基于道路重要度的城市復(fù)雜路網(wǎng)自動(dòng)綜合方法。根據(jù)道路重要度評(píng)價(jià)結(jié)果，按其重要度排序進(jìn)而獲得確定尺度下的道路。設(shè)原始道路網(wǎng)絡(luò)規(guī)模為N，道路選取比例為r，則所選取路網(wǎng)規(guī)模為N·r。路網(wǎng)綜合算法具體描述如下：

1)根據(jù)傳統(tǒng)路網(wǎng)拓?fù)浣Y(jié)構(gòu)，采用基于對(duì)偶拓?fù)涞膹?fù)雜網(wǎng)絡(luò)理論構(gòu)建其復(fù)雜路網(wǎng)模型G={V,E}；

2)計(jì)算復(fù)雜路網(wǎng)模型中所有節(jié)點(diǎn)的連接度、介中心和接近度，基于式(3)，計(jì)算所有道路(即復(fù)雜路網(wǎng)模型中所有節(jié)點(diǎn))的重要度；

3)將道路按重要度進(jìn)行降序排序，并根據(jù)選取比例提取最為重要的N·r條道路，構(gòu)建所選取的復(fù)雜路網(wǎng)模型Gr={Vr,Er}；

4)對(duì)所選路網(wǎng)進(jìn)行拓?fù)溥B通性檢查，并根據(jù)連通性保持算法確保網(wǎng)絡(luò)Gr的全局連通；

5)根據(jù)所選復(fù)雜路網(wǎng)模型構(gòu)建對(duì)應(yīng)的幾何網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，得到綜合后的道路網(wǎng)絡(luò)結(jié)構(gòu)。

3.2 網(wǎng)絡(luò)連通性保持算法

本文采用文獻(xiàn)[6]所給出的連通性保持方法，即通過增加最小數(shù)目的節(jié)點(diǎn)來連通整個(gè)網(wǎng)絡(luò)，具體算法過程如下：①獲取所選網(wǎng)絡(luò)Gr={Vr,Er}中的所有孤立節(jié)點(diǎn)，生成孤立節(jié)點(diǎn)集合Er′；②針對(duì)孤立節(jié)點(diǎn)i(i∈Er′)，計(jì)算距離i最近的節(jié)點(diǎn)j(j∈Er，j?Er′)，獲取i，j之間的最短路徑，并將路徑上所有節(jié)點(diǎn)v(v?Er，v∈E)添加到所選網(wǎng)絡(luò)Gr，并更新所有的節(jié)點(diǎn)信息和邊信息；③重復(fù)步驟②，直到Gr中無孤立節(jié)點(diǎn)。

4 實(shí)驗(yàn)與討論

為檢驗(yàn)方法的有效性，本文以成都市市區(qū)道路網(wǎng)絡(luò)為實(shí)驗(yàn)數(shù)據(jù)，針對(duì)道路在不同尺度下的重要性進(jìn)行路網(wǎng)綜合實(shí)驗(yàn)分析。如圖4為選取比例為0.01、0.05、0.1和0.2等取值下的道路選擇結(jié)果。由實(shí)驗(yàn)結(jié)果可知：在不同選取比例下，所選路網(wǎng)均較好地保持原始路網(wǎng)的整體形態(tài)結(jié)構(gòu)，路網(wǎng)覆蓋了原始路網(wǎng)的整體范圍；在不同選取比例下，綜合路網(wǎng)均能保持拓?fù)溥B通，而且較好地保持了原始路網(wǎng)的密度特性，隨著選取比例的增大，增選道路較為合理；當(dāng)選取比例較小時(shí)，所選道路為環(huán)路及主干道，隨著選取比例的增加，道路的等級(jí)、層次結(jié)構(gòu)得以體現(xiàn)。

(a)選取比例為0.01

(b)選取比例為0.05

(c)選取比例為0.1

(d)選取比例為0.2

為進(jìn)一步說明本文方法的可行性，這里對(duì)所選路網(wǎng)與原始路網(wǎng)的拓?fù)湎嗨菩赃M(jìn)行對(duì)比實(shí)驗(yàn)分析。利用文獻(xiàn)[19-20]所給出的結(jié)構(gòu)相似性度量方法，以連接度為結(jié)構(gòu)度量指標(biāo)，計(jì)算所選路網(wǎng)對(duì)原始路網(wǎng)的結(jié)構(gòu)保持程度。為評(píng)估網(wǎng)絡(luò)u和υ的相似性，設(shè)Vu為網(wǎng)絡(luò)u的節(jié)點(diǎn)集，Vυ為網(wǎng)絡(luò)υ的節(jié)點(diǎn)集。

圖5 所選路網(wǎng)相似性分析

5 結(jié)論

路網(wǎng)自動(dòng)綜合是地圖學(xué)、網(wǎng)絡(luò)壓縮等研究的重點(diǎn)問題。本文針對(duì)傳統(tǒng)圖論在網(wǎng)絡(luò)結(jié)構(gòu)及功能評(píng)價(jià)方面的不足，采用基于對(duì)偶拓?fù)涞膹?fù)雜網(wǎng)絡(luò)理論構(gòu)建路網(wǎng)的復(fù)雜網(wǎng)絡(luò)模型，研究城市復(fù)雜路網(wǎng)的制圖綜合問題。引入連接度、介中心及接近度等結(jié)構(gòu)化指標(biāo)，顧及道路在整個(gè)路網(wǎng)中的結(jié)構(gòu)及功能特征，定義道路重要度評(píng)價(jià)模型。在此基礎(chǔ)上，考慮所選路網(wǎng)的拓?fù)溥B通性，通過道路重要度排序提出一種基于復(fù)雜網(wǎng)絡(luò)的城市復(fù)雜路網(wǎng)自動(dòng)綜合算法。為檢驗(yàn)本文方法的有效性，以成都市城區(qū)道路網(wǎng)絡(luò)為實(shí)驗(yàn)數(shù)據(jù)，針對(duì)路網(wǎng)在不同選取比例下進(jìn)行綜合實(shí)驗(yàn)分析，結(jié)果表明：本文路網(wǎng)綜合方法較好地顧及道路的結(jié)構(gòu)和功能特征，所選路網(wǎng)與原始路網(wǎng)在結(jié)構(gòu)上保持較高的相似度，較好地保持原始路網(wǎng)的整體形態(tài)特征及拓?fù)溥B通，路網(wǎng)的層次結(jié)構(gòu)及密度特性也得以體現(xiàn)。

[1] MACKANESS W A.Analysis of urban road networks to support cartographic generalization [J].Cartography and Geographical Information Systems,1995,22(4): 306-316.

[2] JIANG B,CLARAMUNT C.A structural approach to the model generalization of an urban street network [J].GeoInformatica,2004,8(2): 157-171.

[3] ZHOU Q,LI Z.Evaluation of properties to determine the importance of individual roads for map generalization [J].Advances in Cartography and Giscience,2011,5(1): 459-475.

[4] 欒學(xué)晨,楊必勝,張?jiān)品?城市道路復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)化等級(jí)分析[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2012,37(6): 728-732.

[5] THOMSON R C,RICHARDSON D E.The good continuation principle of perceptual organization applied to the generalization of road networks [C]// Proceeding of 19th International Cartographic Conference,Ottawa: ICA,1999: 1215-1223.

[6] 徐柱,劉彩鳳,張紅,等.基于路劃網(wǎng)絡(luò)功能評(píng)價(jià)的道路選取方法[J].測(cè)繪學(xué)報(bào),2012,41(5): 769-776.

[7] CHEN J,HU Y,LI Z L,et al.Selective omission of road features based on mesh density for automatic map generalization [J].International Journal of Geographical Information Science,2009,23(8): 1013-1032.

[8] LIU G,LI Y S,LI Z,et al.Cartographic generalization of urban street networks based on gravitational field theory [J].Int.J.Mod.Phys.B,2014,28(20):1450133-17.

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

[10] BOCCALETTI S,LATORA V,MORENO Y,et al.Complex networks: structure and dynamics [J].Physics Reports,2006,424(4): 175-308.

[11] 程飛,姬東鴻.基于重疊社團(tuán)發(fā)現(xiàn)的微博話題檢測(cè)方法[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(6): 93-98.

[12] 文宏,樊曉平,張會(huì)福,等.無標(biāo)度網(wǎng)絡(luò)上的動(dòng)態(tài)局部路由策略設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(20): 10-14.

[13] 鄧亞娟,楊云峰,馬榮國,等.基于復(fù)雜網(wǎng)絡(luò)理論的公路網(wǎng)結(jié)構(gòu)特征[J].中國公路學(xué)報(bào),2010,23(1): 98-104.

[14] 楊柳青,宗剛,柳應(yīng)華.基于復(fù)雜網(wǎng)絡(luò)的路網(wǎng)交通擁堵評(píng)估仿真模型[J].計(jì)算機(jī)應(yīng)用研究,2014,31(3): 796-800.

[15] 李永樹,劉剛,張帥毅.基于GIS的多粒度復(fù)雜網(wǎng)絡(luò)模型[J].西南交通大學(xué)學(xué)報(bào),2012,47(3): 406-412.

[16] LIU Gang,LI Yongshu,YANG Jun,et al.Gravitational-field routing strategy considering the distribution of traffic flow.International Journal of Geographical Information Science,2014,28(1): 39-55.

[17] 赫南,李德毅,淦文燕,等.復(fù)雜網(wǎng)絡(luò)中重點(diǎn)性節(jié)點(diǎn)發(fā)掘綜述[J].計(jì)算機(jī)科學(xué),2007,34(12): 1-5.

[18] 李清泉,曾喆,楊必勝,等.城市道路網(wǎng)絡(luò)的介中心性分析[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2010,35(1): 37-41.

[19] Lü L Y,MEDO M,YEUNG C H,et al.Recommender systems [J].Physics Reports,2012,519: 1-49.

[20] 喬柱.城市大比例尺地形圖自動(dòng)化綜合的研究[J].測(cè)繪與空間地理信息，2015,38(7):172-173.

[責(zé)任編輯：張德福]

Auto generalization approach and importance evaluation of urban roads based on complex networks

SONG Haiquan1,GUO Jin1,LIU Gang2

(1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 610031,China；2.College of Earth Sciences,Chengdu University of Technology,Chengdu 610031,China)

Using the complex network theory,an urban complex road network model is constructed.On the basis of this model,from the point of the structural and functional properties of roads,the evaluation model of road importance is defined with the measures of node degree,betweenness centrality and closeness centrality.As the global morphology and topological connectivity of road networks are targetted,the generalization approach based on the complex networks theory is presented.In order to testify the efficiency of this method,experimental analysis is carried out with taking the Chengdu street networks as a case study.The results show that,the evaluation model of road importance reflects the significance of the road within the whole street network on structural and functional aspects,and the generalization approach of complex road networks retains the global morphological structural characteristic of the original road network.

generalization of road networks; road importance; complex network; topological connectivity

引用著錄：宋海權(quán)，郭進(jìn)，劉剛.基于復(fù)雜網(wǎng)絡(luò)的城市道路重要度評(píng)價(jià)及路網(wǎng)自動(dòng)綜合方法[J].測(cè)繪工程，2017，26(1)：08-12.

10.19349/j.cnki.issn1006-7949.2017.01.002

2015-12-29

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

宋海權(quán)(1981-)，男，博士研究生.

U491

A

1006-7949(2017)01-0008-05