公路交通網(wǎng)絡(luò)的區(qū)塊劃分

朱 霞，宋偉東

（遼寧工程技術(shù)大學(xué) 測(cè)繪與地理科學(xué)學(xué)院，遼寧 阜新 123000）

0 引言

公路交通網(wǎng)絡(luò)是服務(wù)經(jīng)濟(jì)、服務(wù)社會(huì)、服務(wù)公眾的重要基礎(chǔ)設(shè)施，是綜合交通運(yùn)輸體系的骨干，如何評(píng)價(jià)交通網(wǎng)絡(luò)規(guī)劃的合理性、公路網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)的合理性、交通網(wǎng)絡(luò)維護(hù)和養(yǎng)護(hù)情況等是亟待解決的理論問(wèn)題和現(xiàn)實(shí)問(wèn)題.目前國(guó)內(nèi)外有很多對(duì)網(wǎng)絡(luò)結(jié)構(gòu)分析的研究?jī)?nèi)容.

近年來(lái)，許多研究利用各種模型的分析理論對(duì)交通網(wǎng)絡(luò)進(jìn)行了探索.網(wǎng)絡(luò)研究人員引入了大量的中心度指標(biāo)，這些指標(biāo)根據(jù)一定的標(biāo)準(zhǔn)賦予網(wǎng)絡(luò)中頂點(diǎn)的重要性[1].這些指標(biāo)已被證明在分析和理解社交網(wǎng)絡(luò)[2-3]、引文網(wǎng)絡(luò)[4]、計(jì)算機(jī)網(wǎng)絡(luò)[5-6]、城市網(wǎng)絡(luò)[7-9]等網(wǎng)絡(luò)所扮演的角色方面具有重要價(jià)值.SUN D[10]等基于復(fù)雜網(wǎng)絡(luò)和圖論，對(duì)城市軌道交通系統(tǒng)的網(wǎng)絡(luò)和站點(diǎn)脆弱性進(jìn)行了分析.AGRYZKOV 等[11]人提出一種適應(yīng)PageRank 算法（APA）來(lái)建立城市網(wǎng)絡(luò)節(jié)點(diǎn)排名，從城市網(wǎng)絡(luò)的主要特征獲得的數(shù)據(jù)計(jì)算每個(gè)節(jié)點(diǎn)的重要性. CHOPRA S S[12]等人提出一個(gè)全面的多管架構(gòu)，分析網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、空間組織和客流信息，以了解倫敦地鐵系統(tǒng)的彈性. WAGNER M 等[13]提出了一種使用功能主成分分析來(lái)創(chuàng)建高質(zhì)量的在線(xiàn)流量預(yù)測(cè)方法. YANG Y[14-16]等將社區(qū)檢測(cè)的概念引入到城市交通狀態(tài)關(guān)聯(lián)網(wǎng)絡(luò)中，提出了一種識(shí)別交通狀態(tài)空間關(guān)聯(lián)模式的新視角. ZHOU Y[17]等通過(guò)統(tǒng)一的指標(biāo)和模型定量分析大型復(fù)雜地鐵網(wǎng)絡(luò)的脆弱性和恢復(fù)性，提出了一個(gè)評(píng)估大型復(fù)雜地鐵網(wǎng)絡(luò)彈性的總體框架. TANG F[18]等從兩個(gè)角度定義鏈接的臨界性，提出一種新的城市交通網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法.

因此，從一個(gè)新的角度來(lái)解釋大規(guī)模網(wǎng)絡(luò)中交通狀態(tài)空間分布的復(fù)雜性.提出一種同時(shí)考慮結(jié)構(gòu)相似性和屬性相似性的區(qū)塊劃分準(zhǔn)則.利用原始節(jié)點(diǎn)映射方法應(yīng)用于公路交通網(wǎng)絡(luò)分析中，構(gòu)建公路交通網(wǎng)絡(luò)的數(shù)學(xué)模型.調(diào)整PageRank 算法，添加公路交通網(wǎng)絡(luò)地理空間結(jié)構(gòu)影響因子計(jì)算公路交通網(wǎng)絡(luò)關(guān)鍵性節(jié)點(diǎn)排序結(jié)果，定義為公路交通網(wǎng)絡(luò)關(guān)鍵性節(jié)點(diǎn)分析方法（簡(jiǎn)稱(chēng)FWLPA）.利用關(guān)鍵性節(jié)點(diǎn)分析方法的排序結(jié)果值和最短路徑距離值繪制決策圖，來(lái)選擇區(qū)塊劃分的初始聚類(lèi)中心點(diǎn)的位置和個(gè)數(shù).最后以沈陽(yáng)市公路交通網(wǎng)絡(luò)為實(shí)驗(yàn)數(shù)據(jù)，通過(guò)公路交通網(wǎng)絡(luò)區(qū)塊劃分方法識(shí)別出網(wǎng)絡(luò)結(jié)構(gòu)相似度和屬性相似度模塊，并分析出區(qū)塊劃分的適宜性評(píng)價(jià).

1 公路交通網(wǎng)絡(luò)構(gòu)建

公路交通網(wǎng)絡(luò)（RTN）是由道路節(jié)點(diǎn)與節(jié)點(diǎn)和節(jié)點(diǎn)之間的連邊構(gòu)成的，可以通過(guò)一組數(shù)學(xué)實(shí)體來(lái)定義，其中N為道路節(jié)點(diǎn)，E為道路節(jié)點(diǎn)與節(jié)點(diǎn)之間的連邊

2 公路交通網(wǎng)絡(luò)區(qū)塊劃分

地理空間角度交通網(wǎng)絡(luò)區(qū)塊結(jié)構(gòu)劃分概念（Regional Patch Detection）：在不同層次劃分公路交通網(wǎng)絡(luò)的范圍內(nèi)，區(qū)塊是一個(gè)公路交通網(wǎng)絡(luò)的子集，包含一定的節(jié)點(diǎn)和節(jié)點(diǎn)與節(jié)點(diǎn)之間的路段，區(qū)塊內(nèi)的節(jié)點(diǎn)與節(jié)點(diǎn)之間關(guān)系緊密，具有較強(qiáng)的拓?fù)浣Y(jié)構(gòu)相似性和地物設(shè)施屬性相似性；而區(qū)塊與區(qū)塊之間的關(guān)系比較稀疏，區(qū)塊與區(qū)塊之間的相似性可以類(lèi)似但距離較遠(yuǎn)，區(qū)塊與區(qū)塊之間的差異較大但距離較近的分布特征.

公路交通網(wǎng)絡(luò)由國(guó)道、省道、縣道、鄉(xiāng)道和村道五個(gè)等級(jí)路網(wǎng)構(gòu)成，深入分析公路交通網(wǎng)絡(luò)的特性模塊聚集情況，分析相同屬性路網(wǎng)的分布情況.通過(guò)初始聚類(lèi)中心的選取，然后基于K-Means 聚類(lèi)方法識(shí)別出公路交通網(wǎng)絡(luò)的特性區(qū)域.

2.1 聚類(lèi)中心選取

為聚類(lèi)算法的設(shè)計(jì)提供一種新的思路.聚類(lèi)算法的核心思想在于對(duì)聚類(lèi)中心（Cluster Centers）的刻畫(huà)上，認(rèn)為聚類(lèi)中心同時(shí)具有以下屬性：

（1）聚類(lèi)中心是被低影響鄰居包圍的重要節(jié)點(diǎn)；

（2）初始聚類(lèi)中心均勻的分布在物理網(wǎng)絡(luò)中，并且中心點(diǎn)之間的“距離”相對(duì)更大.

對(duì)于每個(gè)節(jié)點(diǎn)i，計(jì)算兩個(gè)值：FWLPA 計(jì)算值iρ和從較高中心度節(jié)點(diǎn)出發(fā)的最短路徑長(zhǎng)度iδ.FWLPA 的計(jì)算值iρ是向量*1x的第i個(gè)分量，它評(píng)估節(jié)點(diǎn)i的重要性.利用以上結(jié)果繪制一個(gè)二維決策圖，其中橫軸表示節(jié)點(diǎn)的FWLPA 值，縱軸表示最短路徑長(zhǎng)度.所以，可以在決策圖中選擇分布在圖右上方的K個(gè)節(jié)點(diǎn)選作為初始聚類(lèi)中心.然后利用聚類(lèi)算法K-Means 將交通網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為不同的區(qū)塊群體.由此將ρ值和δ值綜合考慮的量來(lái)確定聚類(lèi)中心的個(gè)數(shù)為

2.2 區(qū)塊劃分方法

在獲得K個(gè)初始聚類(lèi)中心后，應(yīng)用K-means 算法將關(guān)聯(lián)較強(qiáng)的節(jié)點(diǎn)(或路段)分配到同一個(gè)模塊中.區(qū)塊劃分方法需要兩個(gè)步驟進(jìn)行迭代.

步驟1節(jié)點(diǎn)分配

假設(shè)C是一組質(zhì)心，每個(gè)質(zhì)心定義一個(gè)簇.最初K個(gè)初始簇中心構(gòu)成了中心的初始集合，每個(gè)節(jié)點(diǎn)都被分配到最近的質(zhì)心為

如果一個(gè)節(jié)點(diǎn)與兩個(gè)簇心之間的距離相等，則將該節(jié)點(diǎn)分配給簇索引數(shù)較小的簇.

步驟2質(zhì)心迭代更新

設(shè)分配給第k個(gè)集群的節(jié)點(diǎn)集為Zk.每個(gè)簇的質(zhì)心通過(guò)分配給該質(zhì)心簇的所有節(jié)點(diǎn)的均值來(lái)更新

該算法在第一步和第二步之間迭代，直到滿(mǎn)足條件停止，即沒(méi)有節(jié)點(diǎn)改變集群，距離之和最小化，或者達(dá)到最大迭代次數(shù).

3 區(qū)塊劃分的適宜性分析

基于公路交通網(wǎng)絡(luò)關(guān)鍵性分析（FWLPA）結(jié)果和最短路徑長(zhǎng)度兩個(gè)指標(biāo)對(duì)公路交通網(wǎng)絡(luò)進(jìn)行區(qū)塊劃分.通過(guò)標(biāo)準(zhǔn)歐氏距離計(jì)算節(jié)點(diǎn)相似性，然后利用K-Means 算法對(duì)網(wǎng)絡(luò)模塊進(jìn)行檢測(cè).運(yùn)用模塊評(píng)價(jià)指數(shù)（Q-modularity）方法[19-20]來(lái)評(píng)價(jià)公路交通網(wǎng)絡(luò)的適宜性.Q-modularity 的值一般在[-0.5，1]內(nèi).對(duì)于特定的模塊結(jié)構(gòu)，每個(gè)模塊的邊數(shù)存在差異.實(shí)際的邊連接越高，節(jié)點(diǎn)越傾向于集中在某些模塊上，即網(wǎng)絡(luò)的模塊化結(jié)構(gòu)越明顯.具體計(jì)算公式為

式中，A是由網(wǎng)絡(luò)G計(jì)算得到的鄰接矩陣，如果有一條從i到j(luò)的邊，則Aij= 1，否則Aij= 0；m為連接邊的總數(shù)；2m為節(jié)點(diǎn)度的總數(shù)；Aij/2m為兩個(gè)節(jié)點(diǎn)之間連接的實(shí)際概率；k i和kj分別是節(jié)點(diǎn)i和j的度；如果保持網(wǎng)絡(luò)的度分布，但隨機(jī)連接邊，之后任意一對(duì)節(jié)點(diǎn)連接的概率為式（6）～式（7）中表示實(shí)際節(jié)點(diǎn)連接概率高于期望值的程度，是一個(gè)具有兩個(gè)變量的函數(shù)，如果節(jié)點(diǎn)屬于同一個(gè)模塊，則值為1，否則為0，只考慮模塊內(nèi)的連接.應(yīng)用該模型對(duì)公路交通網(wǎng)絡(luò)區(qū)塊劃分的適用性進(jìn)行評(píng)價(jià)，如果實(shí)際公路交通網(wǎng)絡(luò)的道路連接邊數(shù)大于隨機(jī)網(wǎng)絡(luò)中的邊數(shù)，其值為正，并且值越大說(shuō)明區(qū)塊劃分的效果越快，越適宜.

4 實(shí)驗(yàn)

沈陽(yáng)市全面積為12 856 km2，包括國(guó)道（G）、省道（S）、縣道（X）和鄉(xiāng)道（X）4 個(gè)等級(jí)的公路交通網(wǎng)絡(luò)，有7 條國(guó)道，實(shí)際里程為746 km；有15 條省道，實(shí)際里程為1 055 km；有80 條縣道，實(shí)際里程為1 337 km，有440 條鄉(xiāng)道，實(shí)際里程為3 303 km，詳細(xì)數(shù)據(jù)見(jiàn)表1.圖1 為沈陽(yáng)市公路交通網(wǎng)絡(luò)圖.

表1 沈陽(yáng)市公路交通網(wǎng)絡(luò)數(shù)據(jù)Tab.1 Shenyang road traffic network data

采用聚類(lèi)算法識(shí)別公路交通網(wǎng)絡(luò)模塊必須考慮道路節(jié)點(diǎn)的屬性，具有共同邊緣和共同屬性的道路節(jié)點(diǎn)構(gòu)成的模塊結(jié)構(gòu)，見(jiàn)圖2，沈陽(yáng)市公路交通網(wǎng)絡(luò)道路節(jié)點(diǎn)的分布情況，運(yùn)用二維決策圖理論，分析沈陽(yáng)市公路交通網(wǎng)絡(luò)模塊個(gè)數(shù)和模塊初始中心節(jié)點(diǎn)位置，其中表示節(jié)點(diǎn)i的綜合值.

圖1 沈陽(yáng)市公路交通網(wǎng)絡(luò)Fig.1 Shenyang road traffic network

參考γ值越大，越有可能是模塊初始中心點(diǎn).因此，只需對(duì)進(jìn)行降序排列，然后從前往后截取若干個(gè)數(shù)據(jù)點(diǎn)作為初始模塊中心點(diǎn).圖2 中，圖2（a）為出沈陽(yáng)市公路交通網(wǎng)絡(luò)道路節(jié)點(diǎn)的分布情況，圖2（b）為出沈陽(yáng)市公路交通網(wǎng)絡(luò)二維決策值結(jié)果，圖2（c）為橙色方塊圈出的點(diǎn)就是沈陽(yáng)市公路交通網(wǎng)絡(luò)區(qū)塊劃分的個(gè)數(shù)以及模塊初始中心點(diǎn)的位置，圖2（d）為圈出的結(jié)果點(diǎn)的個(gè)數(shù).

圖2 沈陽(yáng)市公路交通網(wǎng)絡(luò)區(qū)塊劃分初始中心點(diǎn)決策Fig.2 Shenyang road traffic network regional patch detection initial center points decision graph

由上述決策圖結(jié)果可知，先計(jì)算出所需區(qū)塊結(jié)構(gòu)的數(shù)量，沈陽(yáng)市公路交通網(wǎng)絡(luò)的區(qū)塊結(jié)構(gòu)數(shù)量為十塊.見(jiàn)圖3，淡黃橘色區(qū)域?yàn)闃?biāo)簽1 區(qū)塊結(jié)構(gòu)；黃色區(qū)域?yàn)闃?biāo)簽2 區(qū)塊結(jié)構(gòu)等10 個(gè)標(biāo)簽區(qū)塊.

圖3 沈陽(yáng)市公路交通網(wǎng)絡(luò)區(qū)塊劃分分布Fig.3 Shenyang road traffic network regional patch detection

如圖3，藍(lán)色邊框繪制出了沈陽(yáng)市公路交通網(wǎng)絡(luò)的區(qū)塊結(jié)構(gòu)，將整個(gè)沈陽(yáng)市分為10 個(gè)區(qū)塊結(jié)構(gòu)，跨越了原有的行政區(qū)劃界限的限制，從公路交通網(wǎng)絡(luò)結(jié)構(gòu)的特征深層次的分析出全新的公路交通網(wǎng)絡(luò)結(jié)構(gòu)狀態(tài).從圖中可以明確的看出10 個(gè)模塊的中心點(diǎn)位，從地理空間結(jié)構(gòu)的角度去理解，提高這10個(gè)模塊結(jié)構(gòu)的連通性能以及便利程度就能很大程度地提高沈陽(yáng)市的公路交通狀況.評(píng)價(jià)沈陽(yáng)市的模塊指數(shù)值為0.062 6，區(qū)塊劃分結(jié)果值較小，適宜性一般.在實(shí)際中，當(dāng)這類(lèi)網(wǎng)絡(luò)的值一般在0.3 到0.7之間時(shí)，聚類(lèi)效果非常好.較高的值是罕見(jiàn)的.將網(wǎng)絡(luò)中的每條邊作為對(duì)矩陣A各元素貢獻(xiàn)的獨(dú)立度量，可以計(jì)算出Q的期望誤差.網(wǎng)絡(luò)模塊劃分結(jié)果一般，說(shuō)明沈陽(yáng)市公路交通網(wǎng)絡(luò)的分布特征較弱.

5 結(jié)論

結(jié)合公路交通網(wǎng)絡(luò)的建設(shè)和結(jié)構(gòu)分析方法，從區(qū)塊劃分的新視角分析了公路交通網(wǎng)絡(luò)的地理空間結(jié)構(gòu)功能，并對(duì)模塊進(jìn)行了自適應(yīng)分析.

（1）在RTN 中，公路交通網(wǎng)絡(luò)系統(tǒng)的模塊劃分結(jié)果取決于地物設(shè)施的屬性、路段之間的距離以及路網(wǎng)的平面分布.

（2）一個(gè)節(jié)點(diǎn)的關(guān)鍵度量不僅取決于它與其他節(jié)點(diǎn)的連接，還取決于它的地理空間特性.運(yùn)用交通網(wǎng)絡(luò)區(qū)塊劃分算法識(shí)別聚類(lèi)性強(qiáng)的路段集.

（3）將該模型和分析方法應(yīng)用于沈陽(yáng)市公路交通網(wǎng)絡(luò)中.結(jié)果表明：該方法在檢測(cè)模塊和模塊結(jié)構(gòu)分析方面表現(xiàn)良好，在識(shí)別公路交通網(wǎng)絡(luò)的地理空間依賴(lài)模式方面具有很大的潛力，為交通運(yùn)營(yíng)和管理分析提供理論依據(jù)；根據(jù)模塊的分布趨勢(shì)對(duì)公路交通網(wǎng)絡(luò)系統(tǒng)進(jìn)行研究，為今后交通網(wǎng)絡(luò)的維護(hù)和改造提供了理論依據(jù).