對(duì)偶圖節(jié)點(diǎn)重要度的道路網(wǎng)自動(dòng)選取方法

劉 剛，李永樹(shù)，楊 駿，張喜平

西南交通大學(xué) 地球科學(xué)與環(huán)境工程學(xué)院，四川 成都 610031

1 引 言

道路選取是地圖綜合中的重要操作之一，指在比例尺縮小后將數(shù)據(jù)中不符合目標(biāo)尺度要求的冗余目標(biāo)舍棄，篩選出重要道路構(gòu)成路網(wǎng)并保持所選路網(wǎng)的拓?fù)溥B通性［1－3］。道路選取的主要困難在于所選路網(wǎng)應(yīng)保持原始路網(wǎng)的整體結(jié)構(gòu)和局部關(guān)鍵結(jié)構(gòu)［4］。目前，選取方法的研究主要集中在兩個(gè)方面：基于路網(wǎng)線狀表示的方法［5－8］和基于路網(wǎng)構(gòu)面表示的方法［3，9－10］。這些方法從不同的角度選取道路，例如考慮道路的幾何、拓?fù)?、等?jí)等屬性［11－12］。在眾多屬性中，連通關(guān)系和幾何特征是道路最基本、最重要的屬性，它們是構(gòu)成路網(wǎng)整體形態(tài)及影響路網(wǎng)功能的關(guān)鍵因素。因而，采用道路幾何與連通關(guān)系進(jìn)行道路選取其方法的實(shí)用性較高［8］。

文獻(xiàn)［2］基于圖論提出一種結(jié)構(gòu)化道路選取方法，指出通過(guò)路段重要性評(píng)價(jià)來(lái)提取道路，拓展了道路選擇的研究思路。然而，由于其方法獨(dú)立地使用連接中心度和鄰近中心度進(jìn)行道路提取，很難得出一致的選取結(jié)果。文獻(xiàn)［7］提到“路段”和“路徑”的重要區(qū)別，引入路劃的概念進(jìn)而提出一種基于路劃的道路選取方法。該方法不直接對(duì)單個(gè)路段作選取，而是從道路自然延伸形態(tài)的角度通過(guò)采用感知分組原理構(gòu)造更大的選取單元，即路劃，且道路選取的衡量標(biāo)準(zhǔn)為路劃長(zhǎng)度。該方法有效地顧及了道路的幾何屬性，但忽略了路網(wǎng)的拓?fù)涮匦裕瑑H依靠路劃長(zhǎng)度進(jìn)行道路選取較難保持原始路網(wǎng)的整體結(jié)構(gòu)及連通關(guān)系。

在文獻(xiàn)［2，7］的基礎(chǔ)上，文獻(xiàn)［8］考慮道路幾何結(jié)構(gòu)和連通關(guān)系，提出以路劃為選取單元、以路劃網(wǎng)絡(luò)功能為選取指標(biāo)的道路選取方法，認(rèn)為道路的重要性體現(xiàn)在道路在路網(wǎng)中的功能，并將此功能定義為道路在全局意義上提供跨越空間的通路和在局部意義上提供連接空間的通路，其道路選取結(jié)果優(yōu)于文獻(xiàn)［7］。然而，該方法將路劃作為單個(gè)對(duì)象處理，沒(méi)有考慮路劃之間的相互作用，可能導(dǎo)致路劃網(wǎng)絡(luò)功能評(píng)價(jià)缺乏準(zhǔn)確性和可靠性。此外，如果兩相鄰路段屬性（如等級(jí)）存在較大差異，很難保證采用感知分組原理所構(gòu)造的路劃的合理性。

總體而言，目前道路選取方法大多還是基于圖論和GIS網(wǎng)絡(luò)分析理論。采用圖論和GIS網(wǎng)絡(luò)分析方法對(duì)于研究路網(wǎng)的結(jié)構(gòu)特征具有一定的積極作用，但不能很好地描述路網(wǎng)結(jié)構(gòu)的整體形態(tài)及復(fù)雜性［13］。為此，本文試圖采用基于對(duì)偶拓?fù)浞椒ǖ膹?fù)雜網(wǎng)絡(luò)理論來(lái)研究道路的選取問(wèn)題。通過(guò)引入m階鄰居節(jié)點(diǎn)的概念，將對(duì)偶圖中節(jié)點(diǎn)的重要度定義為節(jié)點(diǎn)自身及1到m階鄰居節(jié)點(diǎn)重要度貢獻(xiàn)的總和，并以節(jié)點(diǎn)度、介中心及節(jié)點(diǎn)間距離為度量參數(shù)建立節(jié)點(diǎn)重要度評(píng)價(jià)模型，進(jìn)而提出一種基于對(duì)偶圖節(jié)點(diǎn)重要度評(píng)價(jià)的道路選取方法。

2 網(wǎng)絡(luò)拓?fù)鋱D的建立及拓?fù)浣Y(jié)構(gòu)特征指標(biāo)

2.1 道路網(wǎng)絡(luò)的對(duì)偶拓?fù)浔磉_(dá)

在GIS領(lǐng)域，最常用的網(wǎng)絡(luò)拓?fù)浞椒ㄊ侵苯訉?duì)實(shí)際路網(wǎng)做抽象，即以道路為邊、交叉口為節(jié)點(diǎn)建立廣義路網(wǎng)拓?fù)洌?4］。近年來(lái)，復(fù)雜網(wǎng)絡(luò)理論逐漸運(yùn)用到交通、GIS領(lǐng)域，有助于深入分析路網(wǎng)結(jié)構(gòu)的復(fù)雜性及功能特性。利用對(duì)偶拓?fù)浞椒▽⒌缆钒绰访成錇楣?jié)點(diǎn)、交叉口映射為邊可以建立基于廣義路網(wǎng)拓?fù)涞膶?duì)偶圖。如圖1所示，圖1（a）為實(shí)際路網(wǎng)，圖1（b）為廣義路網(wǎng)拓?fù)?，圖1（c）為基于廣義路網(wǎng)拓?fù)涞膶?duì)偶圖。較廣義路網(wǎng)拓?fù)?，采用?duì)偶拓?fù)淠芨由钊氲胤治雎肪W(wǎng)結(jié)構(gòu)及其對(duì)路網(wǎng)功能的影響，可以進(jìn)一步分析道路之間的連接關(guān)系、線路的交通特性、路網(wǎng)的連通性、可靠性以及道路在整個(gè)路網(wǎng)中的重要程度。

圖1 交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.1 Transportation network topology structure

2.2 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征指標(biāo)

設(shè)G＝ ｛V，L｝ 是基于廣義路網(wǎng)拓?fù)浣⒌膶?duì)偶圖，其中V是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合且節(jié)點(diǎn)數(shù)量為N，L為網(wǎng)絡(luò)中所有邊的集合。

2.2.1 節(jié)點(diǎn)度

節(jié)點(diǎn)度是指網(wǎng)絡(luò)拓?fù)渲信c此節(jié)點(diǎn)直接相連的邊的數(shù)量，記為k，它是研究網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的基本參數(shù)。目前普遍認(rèn)為節(jié)點(diǎn)度可以直接反映節(jié)點(diǎn)的重要性，度越高，則該節(jié)點(diǎn)越重要。

2.2.2 節(jié)點(diǎn)介中心

節(jié)點(diǎn)介中心是度量網(wǎng)絡(luò)節(jié)點(diǎn)重要性的方法，給出在網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)處通過(guò)的最短路徑的情況，反映了節(jié)點(diǎn)在網(wǎng)絡(luò)路徑選擇中的重要程度［15］。理論上兩節(jié)點(diǎn)之間最短路徑只有一條，特別是針對(duì)道路網(wǎng)絡(luò)而言，兩點(diǎn)間很少有兩條以上的最短路徑。故這里設(shè)P（i，j） 為節(jié)點(diǎn)i與j之間的唯一最短路徑，用σ（i，j｜μ） 表示以i、j為起訖節(jié)點(diǎn)且通過(guò)節(jié)點(diǎn)μ的最短路徑數(shù)量，如果μ在路徑P（i，j）上，那么σ（i，j｜μ） ＝1；否則，σ（i，j｜μ）＝0。這樣，μ的介中心定義為

式中，i∈V，j∈V且i≠j，通過(guò)提取所有節(jié)點(diǎn)對(duì)間的最短路徑，便可計(jì)算每個(gè)節(jié)點(diǎn)的介中心。

2.2.3 節(jié)點(diǎn)距離

節(jié)點(diǎn)距離是指兩個(gè)節(jié)點(diǎn)之間最短路徑上的邊數(shù)，用d表示。如果節(jié)點(diǎn)i和j之間不存在路徑，則dij→∞。網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間距離的最大值為網(wǎng)絡(luò)的直徑D，任意兩個(gè)節(jié)點(diǎn)之間距離的平均值為網(wǎng)絡(luò)的平均路徑長(zhǎng)度L

3 對(duì)偶圖節(jié)點(diǎn)重要度評(píng)價(jià)方法

3.1 m階鄰居節(jié)點(diǎn)

在已有研究中，通常將與某節(jié)點(diǎn)直接相連的節(jié)點(diǎn)稱(chēng)作該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。一定程度上，節(jié)點(diǎn)的重要性受其鄰居節(jié)點(diǎn)的影響，但不是只有相鄰節(jié)點(diǎn)才會(huì)影響其重要性。為此，這里對(duì)鄰居節(jié)點(diǎn)的概念作如下擴(kuò)展：對(duì)于網(wǎng)絡(luò)G＝ ｛V，L｝ 中節(jié)點(diǎn)i（i∈V），將與i距離為1的節(jié)點(diǎn)稱(chēng)做i的1階鄰居節(jié)點(diǎn)，該類(lèi)節(jié)點(diǎn)構(gòu)成的集合稱(chēng)做i的1階鄰居節(jié)點(diǎn)集，記為π（1）（i）；同理，與i距離為2的節(jié)點(diǎn)為2階鄰居節(jié)點(diǎn)，其構(gòu)成的集合稱(chēng)做i的2階鄰居節(jié)點(diǎn)集，記為π（2）（i）；如此類(lèi)推，則與i距離為m的節(jié)點(diǎn)稱(chēng)為i的m階鄰居節(jié)點(diǎn)，其構(gòu)成的集合為i的m階鄰居節(jié)點(diǎn)集，記為π（m）（i）。圖2所示，節(jié)點(diǎn)i的1階鄰居節(jié)點(diǎn)集為｛a，b，c，d，e，f，g｝，2階鄰居節(jié)點(diǎn)集為｛h，j，v｝。由于網(wǎng)絡(luò)上沒(méi)有節(jié)點(diǎn)存在D＋1階鄰居節(jié)點(diǎn)，故m的取值應(yīng)滿足D≥m≥0。

圖2 鄰居節(jié)點(diǎn)示意圖Fig.2 Sketch map of neighbors

3.2 節(jié)點(diǎn)重要度評(píng)估策略

評(píng)估節(jié)點(diǎn)重要性的方法有很多，且本質(zhì)上都是源于圖論和基于圖的數(shù)據(jù)挖掘［16－18］。筆者認(rèn)為，節(jié)點(diǎn)重要性并不完全由節(jié)點(diǎn)自身屬性所決定，在一定程度上還受到相鄰節(jié)點(diǎn)及距離更遠(yuǎn)節(jié)點(diǎn)的影響，故節(jié)點(diǎn)重要性是節(jié)點(diǎn)自身及多階鄰居節(jié)點(diǎn)共同作用的結(jié)果。從空間自相關(guān)的角度，兩個(gè)對(duì)象距離越近，則對(duì)彼此的依賴越強(qiáng)。由此，距離當(dāng)前節(jié)點(diǎn)越近的節(jié)點(diǎn)，其對(duì)該節(jié)點(diǎn)重要性的貢獻(xiàn)越大。研究表明，很多復(fù)雜系統(tǒng)的某些特性隨距離增加都表現(xiàn)出指數(shù)衰減趨勢(shì)。這里，不妨假設(shè)鄰居節(jié)點(diǎn)的重要度貢獻(xiàn)隨距離的增加呈指數(shù)衰減形式。

式中，Ii為節(jié)點(diǎn)i的重要性指標(biāo)；δ為節(jié)點(diǎn)的屬性值，如節(jié)點(diǎn)度、介中心等。由公式（3）可知，該評(píng)價(jià)函數(shù)綜合考慮了節(jié)點(diǎn)自身及1到m階鄰居節(jié)點(diǎn)的重要度貢獻(xiàn)，且距離i越遠(yuǎn)，其對(duì)i的重要度貢獻(xiàn)越小。為便于理解，這里不妨將m稱(chēng)做節(jié)點(diǎn)重要度評(píng)估所考察的鄰居節(jié)點(diǎn)深度。

對(duì)于網(wǎng)絡(luò)節(jié)點(diǎn)而言，其重要性并不完全取決于節(jié)點(diǎn)的度、介中心或其他特性，需要同時(shí)顧及這些因素，才能對(duì)節(jié)點(diǎn)的重要性作出較為準(zhǔn)確的評(píng)估。假設(shè)選取n個(gè)評(píng)價(jià)指標(biāo)，δi，j為節(jié)點(diǎn)i的第j個(gè)指標(biāo)值。由此，可以定義節(jié)點(diǎn)i的重要度評(píng)價(jià)模型

3.3 道路網(wǎng)對(duì)偶圖節(jié)點(diǎn)重要度評(píng)價(jià)

道路選取的基本原則是從大比例尺路網(wǎng)中按規(guī)則選擇重要的道路。所以，如何評(píng)價(jià)道路的重要性是道路選取的關(guān)鍵。筆者認(rèn)為，道路重要性評(píng)估需要考慮道路的拓?fù)鋵傩约捌鋵?duì)路網(wǎng)傳輸過(guò)程的影響。將對(duì)偶圖節(jié)點(diǎn)按度進(jìn)行排序，可以在一定程度上反映節(jié)點(diǎn)的重要性。節(jié)點(diǎn)度越高，則該節(jié)點(diǎn)越重要。但僅從節(jié)點(diǎn)度的大小并不能準(zhǔn)確地表達(dá)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度。除了度值，節(jié)點(diǎn)的重要性還跟其在網(wǎng)絡(luò)中所處位置、與之相連的其他節(jié)點(diǎn)的重要性密切相關(guān)。中心性是度量網(wǎng)絡(luò)節(jié)點(diǎn)重要性的主要方法，而節(jié)點(diǎn)介中心又是中心性度量的主要方法之一，它給出了在網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)處通過(guò)的最短路徑，反映了節(jié)點(diǎn)連通能力的聚集度及對(duì)網(wǎng)絡(luò)傳輸過(guò)程的影響程度［15，19－20］。為此，綜合考慮度和介中心指標(biāo)，顧及節(jié)點(diǎn)自身及1到m階鄰居節(jié)點(diǎn)的重要度貢獻(xiàn)，基于公式（7）建立如下路網(wǎng)對(duì)偶圖節(jié)點(diǎn)重要度評(píng)價(jià)模型

4 基于節(jié)點(diǎn)重要度評(píng)價(jià)的道路網(wǎng)自動(dòng)選取方法

4.1 道路網(wǎng)自動(dòng)選取方法

基于節(jié)點(diǎn)重要度評(píng)價(jià)結(jié)果，可以依據(jù)對(duì)偶圖中節(jié)點(diǎn)的重要度由高到低選取一定數(shù)量的節(jié)點(diǎn)，由此構(gòu)建所選取的對(duì)偶圖，然后基于最小規(guī)模原則通過(guò)增加節(jié)點(diǎn)的方式保持該對(duì)偶圖的連通性，最后根據(jù)道路與對(duì)偶圖節(jié)點(diǎn)的映射關(guān)系得到所選取的道路網(wǎng)絡(luò)。設(shè)原始對(duì)偶圖規(guī)模為N，為獲取不同比例尺下的路網(wǎng)結(jié)構(gòu)，假設(shè)按一定比例選取該比例下最重要的道路，且選取比例為S。由此，可以定義制圖綜合后得到的對(duì)偶圖的規(guī)模為

由此，可以提出一種基于路網(wǎng)對(duì)偶圖節(jié)點(diǎn)重要度評(píng)價(jià)的道路選取方法，具體過(guò)程如下：

（1）構(gòu)建路網(wǎng)的對(duì)偶圖G＝ ｛V，L｝，建立其節(jié)點(diǎn)與原始廣義路網(wǎng)拓?fù)渲械缆烽g映射關(guān)系。

（2）獲取對(duì)偶圖中任意節(jié)點(diǎn)i的1到m階鄰居節(jié)點(diǎn)集：π（1）（i）、π（2）（i）、…、π（m）（i）。

（4）根據(jù)公式（8），計(jì)算每個(gè)節(jié)點(diǎn)的重要度Ii。

（5）針對(duì)所有節(jié)點(diǎn)，按重要度從大到小進(jìn)行排序，得到一組新的節(jié)點(diǎn)序列v1、v2、v3、…、vN。

（7）對(duì)Gs＝｛Vs，Ls｝進(jìn)行連通性檢查，按4.3中的連通性保持算法確保Gs全域的連通性。

（8）基于對(duì)偶圖Gs＝ ｛Vs，Ls｝，根據(jù)節(jié)點(diǎn)與道路間的映射關(guān)系從原始廣義路網(wǎng)拓?fù)渲刑崛s網(wǎng)絡(luò)中所有節(jié)點(diǎn)相應(yīng)的道路，進(jìn)而構(gòu)建選取比例S下的道路網(wǎng)絡(luò)。

4.2 連通性保持算法

道路選取的基本要求是保持選取后路網(wǎng)的拓?fù)溥B通。根據(jù)對(duì)偶圖的構(gòu)建原則可知，保持廣義路網(wǎng)拓?fù)涞倪B通等價(jià)于保持對(duì)偶圖的拓?fù)溥B通。由此，針對(duì)選取比例S下選取的對(duì)偶圖Gs＝｛Vs，Ls｝，本文通過(guò)增加最小數(shù)目的節(jié)點(diǎn)來(lái)連通所選網(wǎng)絡(luò)。具體的連通性保持算法如下：

（1）提取對(duì)偶圖Gs＝｛Vs，Ls｝中的所有孤立節(jié)點(diǎn)，形成孤立節(jié)點(diǎn)集V′s。

（2）針對(duì)任意節(jié)點(diǎn)i（i∈V′s），計(jì)算距離i最近的某節(jié)點(diǎn)j（j∈Vs且j?V′s），獲取i與j之間的最短路徑，將路徑上所有節(jié)點(diǎn)v（v?Vs）添加到Gs，更新Vs、Ls，并從V′s中移除i。

（3）重復(fù)步驟（2），直到對(duì)偶圖Gs＝｛Vs，Ls｝中無(wú)孤立節(jié)點(diǎn)。

5 試驗(yàn)與討論

根據(jù)成都市城區(qū)2007年交通圖，按路名提取全部共1484條道路，構(gòu)建原始廣義路網(wǎng)拓?fù)?，如圖3所示?；谠撀肪W(wǎng)結(jié)構(gòu)，采用對(duì)偶拓?fù)浞椒?gòu)建路網(wǎng)對(duì)偶圖，包含1484個(gè)節(jié)點(diǎn)，5226條邊，網(wǎng)絡(luò)平均路徑長(zhǎng)度L＝3.913 0，節(jié)點(diǎn)平均度＝7.043 1，網(wǎng)絡(luò)直徑D＝7。這里，認(rèn)為度和介中心同等重要，即ω1＝ω2＝0.5。

圖3 成都市城區(qū)廣義路網(wǎng)結(jié)構(gòu)Fig.3 Generalized road network of Chengdu city

為檢驗(yàn)本文方法的有效性，針對(duì)原始路網(wǎng)在不同選取比例下進(jìn)行道路選取試驗(yàn)。圖4給出了選取比例為0.01、0.05、0.10、0.20、0.30、0.40等6種取值下的道路選取結(jié)果，且m＝4，α＝1，γ＝0.5。從圖中可以看出：① 在各選取比例下，即便選取比例非常小，所選路網(wǎng)保持拓?fù)溥B通，較好地覆蓋了原始路網(wǎng)的整體范圍；② 在各選取比例下，所選路網(wǎng)保持了原始路網(wǎng)的整體結(jié)構(gòu)；③ 在各選取比例下，路網(wǎng)密度特征得以保持，原始路網(wǎng)中相對(duì)密集（或稀疏）的區(qū)域在所選路網(wǎng)中仍得以體現(xiàn)；④ 隨著選取比例的增大，所增選的道路較為合理，有效地顧及了原始路網(wǎng)的密度和整體結(jié)構(gòu)，道路層次性得以體現(xiàn)。由此可知，本文道路選取方法較好地顧及了道路的拓?fù)浜臀恢眯畔?，能較好地滿足道路網(wǎng)自動(dòng)綜合的基本要求。

圖4 不同選取比例下道路選取結(jié)果Fig.4 Roads selection results at various selection ratios

此外，試驗(yàn)發(fā)現(xiàn)，無(wú)論選取比例為何值，選取的路網(wǎng)均能保持良好的拓?fù)溥B通，幾乎無(wú)需用連通性保持算法進(jìn)行連通性修復(fù)，這不僅確保了算法的運(yùn)算效率，同時(shí)說(shuō)明本文方法在路網(wǎng)選取初期便具備良好的連通保持特性。由此可知，本文方法具有較高的穩(wěn)定性和可靠性。

由本文算法原理可知，鄰居節(jié)點(diǎn)深度m的取值直接影響道路重要性評(píng)價(jià)結(jié)果，并最終影響道路的選取效果。若m取值太小，道路重要度評(píng)價(jià)主要依賴道路自身特性，可能導(dǎo)致評(píng)價(jià)結(jié)果不合理、不準(zhǔn)確；若m取值太大，大量較遠(yuǎn)的鄰居節(jié)點(diǎn)將參與重要度評(píng)價(jià)過(guò)程，增大算法的運(yùn)算負(fù)荷，而且也有可能對(duì)道路重要度評(píng)價(jià)造成負(fù)面效果。為此，針對(duì)本文方法在m取值下進(jìn)行了道路選取試驗(yàn)。由于m的取值只有在［0，D］范圍內(nèi)才有意義，所以，只需對(duì)0≤m≤7的值進(jìn)行試驗(yàn)。結(jié)果發(fā)現(xiàn)，當(dāng)m達(dá)到一定值后，所選取的道路將不再隨m的持續(xù)增大而變化，道路選取過(guò)程表現(xiàn)出較強(qiáng)的可靠性和穩(wěn)定性。

由本文方法原理可知，導(dǎo)致這種動(dòng)力學(xué)現(xiàn)象的原因在于對(duì)偶圖節(jié)點(diǎn)的重要度指標(biāo)與m之間的約束關(guān)系。為此，給出了5條關(guān)鍵道路的重要度隨m的變化情況，如圖5所示。結(jié)果顯示，當(dāng)m較小時(shí)，節(jié)點(diǎn)的重要度I隨m取值的增大變化較大，即I對(duì)m較為敏感；當(dāng)m大于對(duì)偶圖的平均路徑長(zhǎng)度L時(shí)，節(jié)點(diǎn)的重要度I將不再隨m的增加而變化，道路重要性評(píng)價(jià)進(jìn)入穩(wěn)定狀態(tài)。由此，可以得出一個(gè)重要結(jié)論：只要m取值大于對(duì)偶圖的平均路徑長(zhǎng)度L，本文方法便能得到穩(wěn)定的道路重要性評(píng)價(jià)結(jié)果，保證道路選取的準(zhǔn)確性和可靠性。

圖5 道路重要度指標(biāo)I與m的關(guān)系Fig.5 The relation of Iand m

根據(jù)圖5中所選道路，采用目視查看方法可以得出選取的道路網(wǎng)絡(luò)保持了原始路網(wǎng)的整體結(jié)構(gòu)及拓?fù)溥B通性。為進(jìn)一步論證本文方法的有效性，需要采用定量評(píng)價(jià)的方法分析道路選取效果。已有研究表明，網(wǎng)絡(luò)的度分布與其拓?fù)浣Y(jié)構(gòu)緊密相關(guān)，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)性質(zhì)及網(wǎng)絡(luò)上的動(dòng)力學(xué)行為等均緊密依賴于網(wǎng)絡(luò)的度分布，而對(duì)于無(wú)標(biāo)度網(wǎng)絡(luò)而言，其度分布則完全由度分布指數(shù)所確定［21］。

為進(jìn)一步分析所選取路網(wǎng)與原始路網(wǎng)的拓?fù)涮匦裕芯克x路網(wǎng)對(duì)原始路網(wǎng)拓?fù)浣Y(jié)構(gòu)的保持程度，分別對(duì)原始對(duì)偶圖及不同選取比例下提取的對(duì)偶圖的度分布情況進(jìn)行了統(tǒng)計(jì)分析，結(jié)果分別如圖6和圖7所示，且α＝1，γ＝0.5，ω1＝ω2＝0.5。統(tǒng)計(jì)結(jié)果顯示：原始對(duì)偶圖中節(jié)點(diǎn)的度分布服從冪律分布，說(shuō)明該城市道路網(wǎng)絡(luò)具有無(wú)標(biāo)度特性；對(duì)于所選取的道路，無(wú)論選取比例為何值，道路網(wǎng)絡(luò)的度分布均表現(xiàn)出無(wú)標(biāo)度特性，同時(shí)發(fā)現(xiàn)其冪律指數(shù)均近似等于原始對(duì)偶圖的冪律指數(shù)。由此表明，本文方法選取的路網(wǎng)沒(méi)有改變?cè)悸肪W(wǎng)的無(wú)標(biāo)度特性，較好地保持了原始路網(wǎng)的整體拓?fù)浣Y(jié)構(gòu)。

圖6 原始道路網(wǎng)絡(luò)的度分布Fig.6 The degree distribution of original road network

6 結(jié) 論

道路的自動(dòng)選取是道路網(wǎng)自動(dòng)綜合領(lǐng)域的關(guān)鍵問(wèn)題，其主要困難在于選取的道路應(yīng)保持原始路網(wǎng)的整體結(jié)構(gòu)。認(rèn)為道路選取的關(guān)鍵在于準(zhǔn)確、合理地評(píng)價(jià)道路的重要性。為此，利用對(duì)偶拓?fù)浞椒?gòu)建基于廣義路網(wǎng)拓?fù)涞膶?duì)偶圖，顧及道路的位置及拓?fù)湫畔?，定義針對(duì)該對(duì)偶圖的節(jié)點(diǎn)重要度評(píng)價(jià)模型，據(jù)此提出以道路重要度為考察指標(biāo)的道路選取方法。

以成都市城區(qū)路網(wǎng)為試驗(yàn)數(shù)據(jù)，針對(duì)不同選取比例和不同鄰居節(jié)點(diǎn)深度進(jìn)行道路選取試驗(yàn)。結(jié)果表明：本文方法選取的路網(wǎng)能較好地保持原始路網(wǎng)的整體結(jié)構(gòu)、拓?fù)溥B通性、路網(wǎng)密度及覆蓋范圍，道路層次性得以體現(xiàn)；引入m階鄰居節(jié)點(diǎn)評(píng)價(jià)道路重要性是合理的，顧及節(jié)點(diǎn)自身及m階鄰居節(jié)點(diǎn)的重要度貢獻(xiàn)有助于衡量道路在拓?fù)浼皫缀挝恢梅矫娴闹匾?；從路網(wǎng)的度分布可知，所選路網(wǎng)能較好地保持原始路網(wǎng)的拓?fù)涮匦?，且不依賴于選取比例；本文方法以道路的幾何、連通關(guān)系為考察數(shù)據(jù)，不依賴于道路屬性數(shù)據(jù)，方法適用性較強(qiáng)；在保持路網(wǎng)整體結(jié)構(gòu)、路網(wǎng)密度、拓?fù)涮匦约奥肪W(wǎng)層次性等方面，本文方法優(yōu)于單純按路劃長(zhǎng)度以及按網(wǎng)絡(luò)中心度選取的效果；同時(shí)，試驗(yàn)還揭示了一個(gè)重要的動(dòng)力學(xué)現(xiàn)象，即當(dāng)m大于對(duì)偶圖的平均路徑長(zhǎng)度L時(shí)，道路重要度評(píng)價(jià)趨于穩(wěn)定，得到的評(píng)價(jià)結(jié)果較為可靠，保證道路選取結(jié)果的有效性。

圖7 不同選取比例下道路網(wǎng)絡(luò)的度分布Fig.7 The degree distribution of road network at various selection ratios

［1］ MACKANESS W A.Analysis of Urban Road Networks to Support Cartographic Generalization［J］.Cartography and Geographic 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］ HU Yungang，CHEN Jun，LI Zhilin，et al.Selective Omission of Road Features Based on Mesh Density for Digital Map Generalization［J］.Acta Geodaetica et Cartographica Sinica，2007，36（3）：351－357.（胡云崗，陳軍，李志林，等.基于網(wǎng)眼密度的道路選取方法［J］.測(cè)繪學(xué)報(bào)，2007，36（3）：351－357.）

［4］ CHEN Bo，WU Fang，QIANG Haizhong.A Study on Road Networks’Auto－selection Algorithms［J］.Journal of Image and Graphics，2008，13（2）：2388－2393.（陳波，武芳，錢(qián)海忠.道路網(wǎng)自動(dòng)選取方法研究［J］.中國(guó)圖象圖形學(xué)報(bào)，2008，13（2）：2388－2393.）

［5］ CHAUDHRY O，MACKANESS M.Rural and Urban Road Network Generalization：Deriving 1：250，000from OS Master Map［C］∥ Proceedings of International Cartographic Conference.Coruna：［s.n.］，2005.

［6］ TOUYA G.A Road Network Selection Process Based on Data Enrichment and Structure Detection［J］.Transactions in GIS，2010，14（5）：595－614.

［7］ THOMSON R C，RICHARDSON D E.The Good Continuation Principle of Perceptual Organization Applied to the Generalization of Road Networks［C］∥Proceedings of 19th International Cartographic Conference.Ottawa：ICA，1999：1215－1223.

［8］ XU Zhu，LIU Caifeng，ZHANG Hong，et al.Road Selection Based on Evaluation of Stroke Network Functionality［J］.Acta Geodaetica et Cartographica Sinica，2012，41（5）：769－776.（徐柱，劉彩鳳，張紅，等.基于路劃網(wǎng)絡(luò)功能評(píng)價(jià)的 道 路 選 取 方 法 ［J］.測(cè) 繪 學(xué) 報(bào)，2012，41（5）：769－776.）

［9］ WANNING P，MULLER J C.A Dynamic Decision Tree Structure Supporting Urban Road Network Automated［J］.The Cartographic Journal，1996，33（1）：5－10.

［10］ 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.

［11］ 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.

［12］ DENG Hongyan，WU Fang，WANG Huilian，et al.A Generalization of Road Networks Based on Topological Similarity［J］.Journal of Geomatics Science and Technology，2008，25（3）：183－187.（鄧紅艷，武芳，王輝連，等.基于拓?fù)湎嗨菩缘牡缆肪W(wǎng)綜合模型［J］.測(cè)繪科學(xué)技術(shù)學(xué)報(bào)，2008，25（3）：183－187.）

［13］ DENG Yajuan，YANG Yunfeng，MA Rongguo.Highway Network Structure Characteristics Based on Complex Network Theory［J］.China Journal of Highway and Transport，2010，23（1）：98－104.（鄧亞娟，楊云峰，馬榮國(guó).基于復(fù)雜網(wǎng)絡(luò)理論的公路網(wǎng)結(jié)構(gòu)特征［J］.中國(guó)公路學(xué)報(bào)，2010，23（1）：98－104.）

［14］ BARTHéLEMY M.Spatial Networks［J］.Physics Reports，2011（499）：1－101.

［15］ LI Qingquan，ZENG Zhe，YANG Bisheng，et al.Betweenness Centrality Analysis for Urban Road Networks［J］.Geomatics and Information Science of Wuhan University，2010，35（1）：37－41.（李清泉，曾喆，楊必勝，等.城市道路網(wǎng)絡(luò)的中介中心性分析［J］，武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2010，35（1）：37－41.）

［16］ WEST D B.Introduction to Graph Theory［M］.Upper Saddle River：Prentice Hall，2001.

［17］ WASHIO T，MOTODA H.State of the Art of Graphbased Data Mining［J］.SIGKDD Explore News，2003，5（1）：59－68.

［18］ HE Nan，LI Deyi，GAN Wenyan，et al.Mining Vital Nodes in Complex Networks［J］.Computer Science，2007，34（12）：1－5.（赫南，李德毅，淦文燕，等.復(fù)雜網(wǎng)絡(luò)中重要性節(jié)點(diǎn)發(fā)掘綜述［J］.計(jì)算機(jī)科學(xué)，2007，34（12）：1－5.）

［19］ CRUCITTI P，LATORA V，PORTA S.Centrality in Networks of Urban Streets［J］.Chaos，2006，16（1）：15113－15122.

［20］ LIU Gang，LI Yongshu.Routing Strategy for Complex Networks Based on Gravitation Field Theory［J］.Acta Physica Sinica，2012，61（24）：248901.（劉剛，李永樹(shù).基于引力場(chǎng)理論的復(fù)雜網(wǎng)絡(luò)路由選擇策略研究［J］.物理學(xué)報(bào)，2012，61（24）：248901.）

［21］ WANG Lin，DAI Guanzhong.On Degree Distribution of Complex Network ［J］.Journal of Northwestern Polytechnical University，2006，24（4）：405－409.（王林，戴冠中.復(fù)雜網(wǎng)絡(luò)的度分布研究［J］.西北工業(yè)大學(xué)學(xué)報(bào)，2006，24（4）：405－409.）