張志然，劉紀平，仇阿根，錢新林，張福浩

1. 武漢大學資源與環(huán)境科學學院，湖北 武漢 430079； 2. 中國測繪科學研究院，北京 100830； 3. 河南省科學院地理研究所，河南 鄭州 450052

隨著社會經(jīng)濟和城市建設的發(fā)展，城市道路網(wǎng)規(guī)模逐漸擴大，并逐漸表現(xiàn)出復雜網(wǎng)絡的特性。對大規(guī)模路網(wǎng)來說，采用經(jīng)典算法計算精確的最短路徑普遍存在時間復雜度過高、存儲消耗過大等問題[1-2]。在大部分實際應用中，可以使用良好的近似路徑來代替精確路徑，同時考慮計算時間和精度間的平衡[3]。多年來，研究學者提出多種預處理技術，包括啟發(fā)策略[4-5]、分層策略[2,6]、地標點策略[7-11]等，通過預處理保留網(wǎng)絡部分重要信息，達到提高計算效率的目的。

地標點策略被廣泛地應用于兩節(jié)點間的距離估計，通過選擇一定數(shù)量的中心節(jié)點，并預計算所有中心點間的最短路徑來提高計算效率，選擇的節(jié)點也稱為landmarks[7-8]、reference nodes[9]、beacons[10]、tracers[11]等。文獻[7]提出了滿足誤差限制條件的基于覆蓋和分割的地標選擇方法；文獻[8]對地標點選擇策略進行總結，對比分析了基本策略、限制策略和劃分策略在地標點選擇上的效率，并結合三角測量原理在社交網(wǎng)絡上進行最短路徑估計；文獻[10]在隨機選擇參考點的基礎上，通過可以進行一定比例調整的距離來保證性能。上述研究表明，最短路徑估計可以利用地標點提升計算效率。然而，這些方法不能同時實現(xiàn)地標點的規(guī)模控制和均衡分布，當?shù)貥它c規(guī)模較大時，預計算所有地標點間的距離也具有較高的空間復雜度。

地標點可以充分利用節(jié)點的重要性提高選取質量。同時，在大規(guī)模道路網(wǎng)中，兩節(jié)點間的最短路徑較大可能地經(jīng)過較為重要的節(jié)點，交通發(fā)達的地方，節(jié)點分布往往比較密集，大部分節(jié)點通常經(jīng)過中心性較大的節(jié)點連接在一起。節(jié)點重要性對最短路徑的計算具有一定的啟發(fā)性。復雜網(wǎng)絡中的節(jié)點重要性評價的方法很多，多采用單一指標或多指標的形式[12-13]。度中心性[14]、中介中心性[15]、接近中心性[16]等方法均分別從不同的方面刻畫了節(jié)點在特定網(wǎng)絡中的重要性。但現(xiàn)實道路網(wǎng)結構類型多樣，很難用單一指標來說明節(jié)點在網(wǎng)絡中的重要程度[13]。

本文針對大規(guī)模道路網(wǎng)的結構特點，結合地標點策略和層次策略，提出一種顧及節(jié)點重要性的最短路徑估計方法。該方法應用復雜網(wǎng)絡理論和Critic賦權法分析節(jié)點的重要性，通過限制參數(shù)和節(jié)點重要性序列使中心節(jié)點均衡的分布于網(wǎng)絡中，同時，制定層次網(wǎng)絡構建方案將原網(wǎng)絡中的部分搜索問題轉移到高層網(wǎng)絡中，尋找一條實際存在的近似路徑作為可能的最短路徑，從而提高運算效率并保持較高的有效性。

1 節(jié)點重要性評價方法

1.1 評價指標

利用復雜網(wǎng)絡理論分析道路節(jié)點在網(wǎng)絡中的幾何或屬性特性，能夠準確地定位網(wǎng)絡的重要節(jié)點，對網(wǎng)絡中重要基礎設施和交通樞紐的協(xié)調管理，增強城市交通管理和服務質量，提高路徑分析和交通擁堵分析的效率具有重要的現(xiàn)實意義。度中心性、集聚系數(shù)[17]、接近中心性、中介中心性、特征向量中心性[18]等是當前節(jié)點重要性評價中主要的量化指標[19-22]。這些重要性度量指標最初應用在社會網(wǎng)絡中，隨后被推廣到其他類型網(wǎng)絡的研究中。在現(xiàn)實道路網(wǎng)中，節(jié)點常用來表示道路口、交叉路口、交通樞紐等，節(jié)點之間的連邊表示實際道路線，邊的權重表示該條道路的實際長度、歐氏距離、旅行時間距離等。

(1) 度中心性，是指網(wǎng)絡中與節(jié)點直接連接的邊數(shù)[14]

(1)

式中，δij表示與節(jié)點i是否與節(jié)點j相交，若相交，則δij=1，否則為0。度中心性是研究節(jié)點中心性最直接的度量指標，其值越大，表明節(jié)點越重要，連接的道路越多。

(2) 局部集聚系數(shù)，是指節(jié)點的相鄰節(jié)點之間的連接數(shù)與它們所有可能存在的連接數(shù)的比值[17]。無向圖中節(jié)點i的集聚系數(shù)為

Clc(i)=2ei/kiki-1

(2)

式中，ki為i的鄰接節(jié)點數(shù)，i與其鄰接節(jié)點之間最多可能存在2/kiki-1條連接，ei為鄰接節(jié)點間的邊的數(shù)量。集聚系數(shù)表示節(jié)點的聚集程度，其值越大，表明節(jié)點與鄰接節(jié)點間存在模塊結構的可能性越大。

(3) 接近中心性，是指節(jié)點到其他所有節(jié)點的最短路徑長度之和的倒數(shù)[16]

(3)

式中，dist(v,s)為節(jié)點i與j之間的最短路徑長度。接近中心性反映道路節(jié)點與其他節(jié)點之間的接近程度，用來度量節(jié)點在網(wǎng)絡中是否處于核心位置，其值越大，表明節(jié)點越重要，節(jié)點的影響及服務范圍越廣。

(4) 中介中心性，是指經(jīng)過該節(jié)點的最短路徑數(shù)目與所有最短路徑數(shù)目的比值[15,22]

(4)

式中，σst為任意節(jié)點s到t的最短路徑數(shù)目，σst(i)為節(jié)點s到t的最短路徑中經(jīng)過節(jié)點i的最短路徑數(shù)目。中介中心性反映了節(jié)點作為“橋梁”的重要程度，其值越大，表明最短路徑經(jīng)過的次數(shù)越多，在整個網(wǎng)絡中的影響力和控制力越強。

(5) 特征向量中心性，通過鄰接節(jié)點的重要性來衡量本節(jié)點的重要性[18]

(5)

式中，A=ai,j為鄰接矩陣，如果節(jié)點i與j相連，則ai,j=1，否則為0；λ為常數(shù)，M(i)為節(jié)點i的鄰接節(jié)點。特征向量中心性反映了節(jié)點在網(wǎng)絡中的價值，相比于接近中心性，其考慮了鄰點的重要性。

1.2 基于Critic的多指標集成

單一指標僅能從單一層面反映節(jié)點的重要性，且節(jié)點重要性不僅取決于自身屬性，在一定程度上受其相鄰節(jié)點甚至更遠節(jié)點的影響[19]。為了綜合考慮節(jié)點在網(wǎng)絡中起到的局部及全局影響，以上述指標綜合評價網(wǎng)絡節(jié)點的重要性，更準確有效地發(fā)掘出復雜網(wǎng)絡中的重要節(jié)點，節(jié)點重要性評價模型定義如下

Ii=α1Cd(i)+α2Clc(i)+α3Ccc(i)+

α4Cb(i)+α5Ce(i)

(6)

式中，Ii為節(jié)點i的重要度；α1、α2、…、α5為系數(shù)；Cd(i)、Clc(i)、…、Ce(i)分別表示離差標準化后的度中心性、集聚系數(shù)、接近中心性、中介中心性和特征向量中心性。

由于指標系數(shù)的確定缺少專家經(jīng)驗和可靠的網(wǎng)絡信息，本文對指標參數(shù)α1、α2、…、α5進行多重共線性分析，采用客觀賦權法Critic方法[23]實現(xiàn)模型信息量的最大化。指標Cj,0

(7)

式中，δj為第j個指標的標準差，rjk為指標j與k間的相關系數(shù)?？梢钥闯?，指標j的信息量包含兩部分：①單指標內部信息量，即指標標準差δj；②不同指標間的信息量，即指標與其他指標的沖突性rjk，rjk越大，沖突性越低。Ej越大，指標所包含的信息量越大，該指標的相對重要性越強。那么，指標Cj的系數(shù)αj表示為

(8)

2 顧及節(jié)點重要性的最短路徑估計方法

2.1 方法流程

本文的研究思路可概括為：首先，根據(jù)原始網(wǎng)絡計算單項評價指標，利用Critic方法實現(xiàn)節(jié)點重要性的多指標集成；其次，依據(jù)節(jié)點序列及限制條件，選擇中心節(jié)點并實現(xiàn)網(wǎng)絡劃分；然后，根據(jù)中心節(jié)點集合和中心節(jié)點間的連接關系構建層次結構網(wǎng)絡；最后，在層次結構網(wǎng)絡上實現(xiàn)最短路徑值的估計。方法流程如圖1所示，主要步驟描述如下：

(1) 節(jié)點重要性評價。從原始網(wǎng)絡中提取節(jié)點重要性的評價指標，采用客觀賦權法Critic方法探究節(jié)點重要程度，生成節(jié)點重要性序列。

(2) 中心節(jié)點選擇與網(wǎng)絡劃分。依據(jù)節(jié)點重要性序列，以優(yōu)先重要性強的節(jié)點、排除被標記的節(jié)點為原則生成中心節(jié)點集，通過限制參數(shù)將原始網(wǎng)絡劃分為若干個子網(wǎng)絡(見2.2節(jié))。

(3) 層次結構網(wǎng)絡構建。中心節(jié)點集構成層次結構網(wǎng)絡的節(jié)點，對具有連接關系的中心節(jié)點間進行輔助邊構建，構成層次結構網(wǎng)絡的邊。

(4) 最短路徑估計。依據(jù)所構建的層次結構網(wǎng)絡，實時計算得到任意兩個節(jié)點間的近似最短路徑(見2.3節(jié))。

圖1 方法流程Fig.1 Analysis process

2.2 網(wǎng)絡劃分策略

影響最短路徑計算精度的一個核心因素是網(wǎng)絡劃分，而中心節(jié)點作為子網(wǎng)絡的核心，其選擇很大程度上影響了劃分的效率和劃分后網(wǎng)絡的拓撲結構?，F(xiàn)有研究中提出和使用的中心點選擇的基本策略，主要包括隨機法與基于度中心性、中介中心性、接近中心性等帶有啟發(fā)思想的度量方法?；静呗砸云渲心骋环N方法作為中心節(jié)點的選擇策略，指定選取數(shù)量控制節(jié)點規(guī)模。但是，基本策略可能會使中心節(jié)點分布較為集中，部分中心節(jié)點的覆蓋貢獻較小，因此，本文在此基礎上，引入多指標評價模型將網(wǎng)絡節(jié)點的相對重要性進行量化，通過限制性的網(wǎng)絡劃分策略，使中心節(jié)點較為均勻的分布于整個網(wǎng)絡。

不妨假設某一中心節(jié)點li的覆蓋范圍為β，被li所覆蓋的節(jié)點不納入選擇范圍，在能夠有效減小中心節(jié)點規(guī)模的同時，提高算法執(zhí)行效率。為此，從空間角度引入規(guī)模參數(shù)m和深度參數(shù)h，分別用于調節(jié)中心節(jié)點的覆蓋范圍。對于無向圖GV,E,W，網(wǎng)絡劃分包括以下幾個步驟：

(1) 依據(jù)節(jié)點重要性由高到低排序得到序列T。

(2) 從序列T中依次選取節(jié)點s。

(3) 若s未被標記，將s加入到中心點集S，將以s為中心節(jié)點的子網(wǎng)絡記為Gs，并執(zhí)行步驟(4)，否則執(zhí)行步驟(2)。

(4) 從節(jié)點s開始執(zhí)行寬度優(yōu)先遍歷，若搜索到的節(jié)點t滿足覆蓋條件βm,h，則對t進行標記，并劃分到子網(wǎng)絡Gs中，記錄s到t的最短路徑。

(5) 循環(huán)執(zhí)行步驟(2)—(4)，直到序列T為空。

以上步驟生成了一個包含d個中心節(jié)點的集合S，并將原始網(wǎng)絡G劃分為d個子網(wǎng)絡，記為G1、G2、…、Gd。本文以節(jié)點數(shù)量表示規(guī)模參數(shù)，以節(jié)點到中心節(jié)點的最短距離上限表示深度參數(shù)，即βm,h滿足dists,t≤h且numVs≤m，其中，Vs表示Gs的節(jié)點集，numVs表示Gs包含的節(jié)點數(shù)量。

如圖2所示，每兩個節(jié)點間的距離值為1，β1和β2表示節(jié)點li的覆蓋條件，其中，淺色陰影部分覆蓋的節(jié)點滿足β1:m=13,h=2，虛線范圍內的節(jié)點滿足的β2:m=25,h=3，被覆蓋的節(jié)點和邊組成以li為中心節(jié)點、以β1/β2為限制參數(shù)的子網(wǎng)絡Gli。

在對網(wǎng)絡進行劃分后，將中心節(jié)點集合抽象為層次結構網(wǎng)絡的節(jié)點，依據(jù)子網(wǎng)絡間的連接情況構建輔助邊，這些邊構成層次結構網(wǎng)絡的邊。給定無向圖G(V,E,W)，劃分后的子網(wǎng)絡為{G1,G2,…,Gd}，Gi(Vi,Ei,Wi),1≤i≤d對應中心節(jié)點li，構建思想主要包括兩步：節(jié)點收縮和輔助邊構建。節(jié)點收縮：將Gi中所有節(jié)點壓縮為一個超級節(jié)點li；輔助邊構建：在存在公共節(jié)點或連接邊的任意兩個子網(wǎng)絡Gi,Gj間的超級節(jié)點li與lj間添加輔助邊lj,k，并計算和保存li與lj的最短路徑。因此，層次結構網(wǎng)絡Gh為一個包含d個中心點的圖，實現(xiàn)了網(wǎng)絡規(guī)模的收縮。如圖3所示，黑色節(jié)點為中心節(jié)點，白色節(jié)點為普通節(jié)點。圖3(a)中灰色橢圓表示網(wǎng)絡劃分情況；圖3(b)表示具有連接關系的中心節(jié)點間的最短路徑；圖3(c)表示構建得到的層次結構網(wǎng)絡，基于層次結構網(wǎng)絡實現(xiàn)最短路徑的近似計算。

圖2 中心節(jié)點覆蓋示意圖Fig.2 Coverage of the center nodes

圖3 層次結構網(wǎng)絡構建示意圖Fig.3 Network partition

2.3 最短路徑近似估計

為了有效估計兩節(jié)點間的最短路徑，本文以通過中心節(jié)點的一條實際存在的路徑近似代表節(jié)點間的最短路徑，分別計算起始點或目標點到與其最近的中心節(jié)點間的最短距離，然后在層次網(wǎng)絡中進行最短路徑計算。因此，對于任意節(jié)點對(s,t)，其最短路徑包含三部分，即s和t分別到所屬子網(wǎng)絡中距離其最近的中心節(jié)點間的最短路徑與中心節(jié)點間的最短路徑之和。最短路徑及最短路徑的近似值表示為

dist(s,t)=dist(s,ls)+dist(ls,lt)+dist(t,lt)

(9)

path(s,t)=path(s,ls)+path(ls,lt)+path(t,lt)

(10)

式中，ls、lt表示到s、t所屬子網(wǎng)絡中距離最近的中心節(jié)點，path(s,t)表示s到t的近似最短路徑，dist(s,t)表示s到t的近似最短路徑值。dist(ls,lt)、在Gh中計算得到，為近似值；dist(s,ls)、dist(t,lt)、path(s,ls)與path(t,lt)在網(wǎng)絡劃分時已經(jīng)進行計算并存儲，為真實值，因此可以直接查詢獲得。若s為中心節(jié)點，則dist(s,ls)、path(s,ls)項為0；同理，若t為中心節(jié)點，則dist(t,lt)、path(t,lt)項為0。為了保證路徑的真實性，在計算path(ls,lt)的過程中動態(tài)讀取輔助邊計算的中間結果，即具有連接關系的中心節(jié)點間的最短路徑，最終生成一條實際存在的近似路徑。

與常見的隨機方法、度中心性等基本策略不同，在最短路徑計算時，考慮了大規(guī)模道路網(wǎng)中最短路徑較大可能經(jīng)過重要性較大的節(jié)點，算法依據(jù)網(wǎng)絡中的節(jié)點重要性來構建中心節(jié)點集合、劃分區(qū)域，充分考慮了網(wǎng)絡的拓撲結構。同時，常見的基于地標點的最短路徑估計方法，通過預處理所有地標點間的最短路徑，以求在查詢時可以達到O1的時間復雜度，但對于大規(guī)模道路網(wǎng)數(shù)據(jù)，往往需要較高的空間復雜度。本文在充分簡化后的層次網(wǎng)絡上實時計算最短路徑，在滿足一定的精度要求情況下，降低了空間復雜度，有效提高了計算效率。

3 試 驗

3.1 數(shù)據(jù)集

本文使用大規(guī)模道路網(wǎng)數(shù)據(jù)——紐約城市道路網(wǎng)作為測試數(shù)據(jù)。紐約城市道路網(wǎng)為無向平面圖，有264 346個節(jié)點和730 100條邊，99%的節(jié)點度分布在[1,4]之間。道路交叉口和道路分別抽象為網(wǎng)絡的節(jié)點和邊，邊權重為相應的路段的長度。本文采用復雜網(wǎng)絡分析軟件計算生成節(jié)點的度中心性、集聚系數(shù)、接近中心性、中介中心性和特征向量中心性，指標的描述性統(tǒng)計信息見表1。

表1 評價指標的描述性統(tǒng)計

首先，對指標進行標準化，計算各指標的標準差和相關性，根據(jù)Critic方法計算各指標的綜合權重(見表1)。從表中可以看出，對于該道路網(wǎng)來說，接近中心性和度中心性在5項指標中具有較大的權值，占總比重的60%，而中介中心性的權值最小，為0.070 7。節(jié)點重要性的綜合統(tǒng)計結果顯示，節(jié)點重要值呈正態(tài)分布特征。其中，88%的節(jié)點的重要性值介于[0.1,0.4]之間，表明絕大部分節(jié)點具有相似的重要性；僅有9%的節(jié)點重要性值介于[0.5,1.0]之間，說明網(wǎng)絡中存在少量的占支配地位的節(jié)點。

3.2 層次網(wǎng)絡構建結果分析

為了比較單指標與綜合指標計算得到的節(jié)點重要性，以及限制條件等因素對層次網(wǎng)絡和最短路徑計算結果的影響，本文分別采用隨機法、度中心性和多指標集成法，基于約束條件進行網(wǎng)絡劃分與層次結構網(wǎng)絡構建，分別記為RANDOM/β、DEGREE/β和SYNTHESIS/β。同時，將上述方法同兩種現(xiàn)有選取思想進行比較：①文獻[24]中區(qū)域中心點的選擇策略，考慮復雜網(wǎng)絡的無標度特性，依據(jù)節(jié)點度中心性序列，選取的中心節(jié)點集合滿足度數(shù)之和不大于全部節(jié)點度數(shù)之和的50%，或數(shù)量不超過節(jié)點總數(shù)的10%，記為DEGREE/CDZ；②文獻[7]中帶有限制條件的地標點選擇策略，通過深度參數(shù)h降低覆蓋的重疊度，本文以綜合節(jié)點重要性定義節(jié)點序列，記為SYNTHESIS/h。

為了進一步探討限制參數(shù)β對層次網(wǎng)絡規(guī)模的影響，分別設置參數(shù)β1(5,200)、β2(10,400)、β3(15,600)、β4(25,800)、β5(40,1000)、β6(55,1200)、β7(75,1400)、β8(95,1600)、β9(120,1800)、β10(150,2000)、β11(185,2200)、β12(220,2400)，前者規(guī)模參數(shù)m以節(jié)點數(shù)量表示；后者深度參數(shù)h表示節(jié)點到中心節(jié)點的最短距離上限，單位為米。從中心節(jié)點的數(shù)量占節(jié)點總數(shù)的比例(見圖4)、輔助邊數(shù)量與原始網(wǎng)絡邊總數(shù)的比值(見圖5)兩個方面來衡量層次網(wǎng)絡的規(guī)模。

圖4 不同選取方法下中心節(jié)點數(shù)量占比Fig.4 The percentage of center nodes in different methods

圖5 不同選取方法下輔助邊數(shù)量占比Fig.5 The percentage of auxiliary edges in different methods

圖4和圖5所示：①5種方法均有效降低了原始網(wǎng)絡的規(guī)模，除DEGREE/CDZ方法指定了中心節(jié)點數(shù)量外，其他方法得到的中心節(jié)點數(shù)量和輔助邊數(shù)量均隨參數(shù)變化呈指數(shù)型降低；②SYNTHESIS/β、DEGREE/β和RANDOM/β方法在數(shù)量上沒有明顯的差異，β1(5,0.2)時，SYNTHESIS/β方法得到的層次網(wǎng)絡規(guī)模最大，但其中心節(jié)點數(shù)量和輔助邊數(shù)量也僅占原始網(wǎng)絡節(jié)點數(shù)量和邊的36%和64%，β12(220,2.4)時，3種方法的中心節(jié)點數(shù)量和輔助邊數(shù)量均僅占原始網(wǎng)絡節(jié)點和邊的1.3%和4.8%；③SYNTHESIS/h方法只采用深度參數(shù)h作為限制條件，因此增大了中心節(jié)點的覆蓋范圍，在數(shù)量上明顯小于上述3種方法。

3.3 最短路徑近似結果分析

在構建的5種層次結構網(wǎng)絡上，本文采用點對點Dijkstra算法[25]近似計算任意兩點間的最短路徑，使用二叉堆實現(xiàn)優(yōu)先隊列，算法復雜度為O(mlogn)[26]。在大規(guī)模網(wǎng)絡上估計所有節(jié)點的最短路徑是非常昂貴的，因此，從原始網(wǎng)絡中隨機選取500個節(jié)點對，根據(jù)不同層次網(wǎng)絡上最短路徑值的平均路徑比，測評計算的準確性。路徑比是指若干節(jié)點對的最短路徑近似值與精確值比值，比值越接近1，表示方法的準確率越高。

為了比較不同方法構建的層次網(wǎng)絡對計算精度的影響，圖6顯示了最短路徑比與限制參數(shù)的變化趨勢。結果顯示，DEGREE/CDZ方法的平均路徑比為1.128，其他方法均隨參數(shù)的增大而增大；在一定參數(shù)范圍內，SYNTHESIS/β方法最為精確，β1時路徑比達到1.026，DEGREE/β略高于SYNTHESIS/β方法；RANDOM/β方法隨機選擇中心節(jié)點，通用性較好，但是沒有考慮網(wǎng)絡的拓撲結構特性，準確性最低。SYNTHESIS/β與DEGREE/β方法考慮了網(wǎng)絡的中心性特征，優(yōu)先考慮具有較大重要性的節(jié)點，說明重要性越大的節(jié)點在最短路徑計算中起越重要的作用。

圖6 不同方法下的平均路徑比Fig.6 Average path ration in different methods

圖7表示中心節(jié)點規(guī)模同平均路徑比的關系，從4種方法的趨勢線可以看出，平均路徑比隨著中心節(jié)點數(shù)量的降低而增加。對于相同數(shù)量的中心節(jié)點，SYNTHESIS/β和SYNTHESIS/h方法表現(xiàn)出較高的準確性，且變化趨勢基本吻合，而RANDOM/β方法的準確性最低。由本文算法的原理可知，節(jié)點重要性評價模型和限制參數(shù)的取值直接影響了中心節(jié)點的選取結果，并最終影響了最短路徑的計算精度。隨著限制參數(shù)的增大，中心節(jié)點的數(shù)量也增大，子網(wǎng)絡規(guī)模越來越大。本文的中心節(jié)點選擇方法與網(wǎng)絡劃分方法SYNTHESIS/β與SYNTHESIS/h的試驗結果表明，相對于單一指標，對多指標集成方法能夠更好地保留重要節(jié)點，有效降低了中心節(jié)點的數(shù)目，且估算結果較為精確，同時滿足了距離的性能與準確性的要求。

圖7 平均路徑比與中心節(jié)點數(shù)量關系Fig.7 The relationship between average path ration and number of center nodes

由算法復雜性可知，最短路徑的計算時間隨網(wǎng)絡規(guī)模的減小而減小，所以在相同的限制參數(shù)下，SYNTHESIS/h計算時間最優(yōu)，但其計算精度低于SYNTHESIS/β、DEGREE/β。原始網(wǎng)絡中最短路徑的平均計算時間為3.76 s，圖8可以看出，SYNTHESIS/β、DEGREE/β和RANDOM/β方法在計算時間上基本吻合，對計算精度最為精確的SYNTHESIS/β方法來說，在參數(shù)β1到β12，計算時間呈指數(shù)型降低，從1.412 s到0.039 s，計算效率提高了2.7到94倍。通過以上分析，SYNTHESIS/β方法不僅能保證較高的計算精度，也能夠有效提高最短路徑的計算效率。

為了更好地顯示近似最短路徑的估計效果，在不同參數(shù)下選取任意節(jié)點對進行近似最短路徑計算。圖9給出了參數(shù)為β1、β3、β5、β7、β9、β11等6種取值下的計算結果，灰色粗線表示節(jié)點間的精確路徑，黑色粗線表示相應參數(shù)下的近似最短路徑?？梢钥闯?，在不同參數(shù)下，β1、β3和β5得到的近似最短路徑均能較好地分布于精確路徑的周邊，隨著參數(shù)的增大，差距越大。因此，在實際的最短路徑計算中，本文方法顧及了節(jié)點的重要性和限制范圍，降低了網(wǎng)絡規(guī)模，通過調整選取參數(shù)，可以根據(jù)誤差要求選取一定的參數(shù)進行最短路徑的近似估計，滿足了道路網(wǎng)下最短路徑近似計算的基本要求。

圖8 最短路徑平均計算時間Fig.8 Mean time of shortest paths

圖9 不同參數(shù)下最短路徑近似結果Fig.9 Approximation results of shortest path in different parameters

4 結 論

本文在分析節(jié)點重要性評價指標的基礎上，基于Critic方法與復雜網(wǎng)絡理論實現(xiàn)節(jié)點重要性的綜合評價。基于此，提出了顧及節(jié)點重要性的最短路徑估計方法，引入規(guī)模參數(shù)和深度參數(shù)實現(xiàn)網(wǎng)絡劃分，制定層次結構網(wǎng)絡的構建方案，實現(xiàn)大規(guī)模道路網(wǎng)數(shù)據(jù)的有效化簡和最短路徑的快速有效估計。本文以大規(guī)模道路網(wǎng)數(shù)據(jù)進行測試，試驗結果說明，顧及節(jié)點重要性的最短路徑估計方法能夠更好地均衡劃分后子網(wǎng)絡的規(guī)模，提高最短路徑的計算效率的同時保持了較高的計算精度，適用于大規(guī)模的道路網(wǎng)的最短路徑快速計算。

以復雜網(wǎng)絡理論為基礎，本文方法能夠為面向較大規(guī)模的交通運輸網(wǎng)絡、社會關系網(wǎng)絡、通訊網(wǎng)絡等現(xiàn)實網(wǎng)絡的節(jié)點重要性分析、網(wǎng)絡簡化和最短路徑分析等提供思路。本文方法僅從網(wǎng)絡本身的拓撲與空間特征出發(fā)進行處理，未對道路網(wǎng)的屬性特征和城市結構特征等因素進行考慮。后續(xù)需要擴展研究的內容有以下3點：①目前試驗表明該方法對于單中心特征明顯的紐約市數(shù)據(jù)具有較好的適用性，今后將在不同類型城市道路網(wǎng)(如多中心、放射狀、環(huán)狀道路等)上考察該方法的適用性與應用特點，進行更全面的評估和改進；②節(jié)點重要性分析、限制參數(shù)的界定與道路網(wǎng)節(jié)點的實際輻射范圍存在關聯(lián)，結合現(xiàn)實道路網(wǎng)中節(jié)點或邊的屬性信息，實現(xiàn)不同類型道路網(wǎng)的最短路徑特征研究與動態(tài)分析；③實際道路網(wǎng)絡多為有向圖且具有轉向限制，基于有向圖計算得到評價指標，在計算過程中考慮邊的方向性，將該方法拓展到有向交通網(wǎng)絡中；結合混合邊-節(jié)點算法[27]進一步研究具有轉向限制的大規(guī)模道路網(wǎng)絡的最短路徑近似計算。