林 丹，羅 杰

(南京郵電大學 自動化學院，江蘇 南京 210000)

基于有權(quán)網(wǎng)絡(luò)的區(qū)域交通子網(wǎng)劃分方法研究

林 丹，羅 杰

(南京郵電大學 自動化學院，江蘇 南京 210000)

交通擁堵問題，已成為世界各國不容回避的棘手難題，引起了眾多學者的關(guān)注。動態(tài)劃分交通區(qū)域是提高區(qū)域交通系統(tǒng)整體效率的一個有效的解決方法，隨著計算機技術(shù)的快速發(fā)展，復(fù)雜網(wǎng)絡(luò)理論也有了突破性的進展。為此，在復(fù)雜網(wǎng)絡(luò)社團劃分的基礎(chǔ)上，以交通路網(wǎng)的暢通特性為權(quán)重，提出了無權(quán)網(wǎng)絡(luò)社團劃分的改進算法。該算法采用路段間的車流量和路段距離作為權(quán)重的參考因素，同時結(jié)合網(wǎng)絡(luò)中復(fù)雜度的大小，以模塊度Q作為不同劃分結(jié)果的評價標準，使得改進后的算法劃分出來的社團可靠性更強。為驗證提出算法的有效性和可行性，基于所編寫的計算機程序，對該算法進行了仿真實驗。基于仿真實驗結(jié)果的改進前后的Q值分析對比，驗證了該算法的有效性和可行性，且具有交通區(qū)域?qū)崟r動態(tài)劃分的潛力。

交通區(qū)域；社區(qū)結(jié)構(gòu)；車流量；路段距離

1 概 述

進入21世紀以來，隨著全球城市化進程的高速推進，交通流的日益增大及復(fù)雜化，城市路網(wǎng)擁堵問題越來越嚴重，現(xiàn)有的智能交通控制策略很難提高整個區(qū)域交通系統(tǒng)的效率。對區(qū)域路網(wǎng)進行合理的劃分能夠改善資源的有效配置，對提高整個路網(wǎng)的通行效率具有重要意義。近年來，隨著計算機的快速發(fā)展，以及眾多學者對大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的深入研究，推動了整個復(fù)雜網(wǎng)絡(luò)領(lǐng)域研究方法的蓬勃發(fā)展。

網(wǎng)絡(luò)在許多領(lǐng)域都扮演著至關(guān)重要的角色。在很多現(xiàn)實網(wǎng)絡(luò)中，如物聯(lián)網(wǎng)、社會關(guān)系網(wǎng)、交通路網(wǎng)等都具有一個相同的特性—社團結(jié)構(gòu)[1-2]。社團結(jié)構(gòu)是內(nèi)部連接緊密，而外部相對松散的集合，即對于大部分復(fù)雜網(wǎng)絡(luò)都存在若干個社團，雖然每個社團內(nèi)部節(jié)點之間的連接相對非常緊密，但對于各個社團之間的連接卻比較稀疏[1,3]。此現(xiàn)象揭示了網(wǎng)絡(luò)的社團特性，對深入了解網(wǎng)絡(luò)結(jié)構(gòu)以及分析網(wǎng)絡(luò)特性意義深遠。

網(wǎng)絡(luò)社團結(jié)構(gòu)的劃分與分級聚類以及圖形分割都有著密切關(guān)系。下面列舉一些經(jīng)典的社團劃分算法：

(1)Kernighan-Lin算法[4]。一種試探優(yōu)化算法，利用網(wǎng)絡(luò)鄰接矩陣的特征值和特征向量來進行社團劃分。其本質(zhì)是將網(wǎng)絡(luò)劃分為兩個大小已知的社團，是一種基于貪婪算法的二分法，所以該算法具有一定的局限性。

(2)基于Laplace圖特征值的譜平分法[5]。該算法依據(jù)Laplace矩陣不為零的特征值所對應(yīng)的特征向量的各元素中，在社團內(nèi)的節(jié)點對應(yīng)的元素是近似相等的原理。但是該算法需要事先知道社團數(shù)目，對研究未知網(wǎng)絡(luò)沒有意義。

(3)GN分裂算法[6]。其算法原理是從網(wǎng)絡(luò)中移除介數(shù)最大的邊，把整個網(wǎng)絡(luò)分解為社團。雖然GN算法對于社團劃分具有較高的準確性，但是在不確定社團數(shù)目的前提下，該算法并不清楚分解到哪一步終止。針對該缺陷，一些學者提出了節(jié)點集的GN算法、自包含GN算法[7]、極值優(yōu)化算法[8]等，但是這些算法共同的缺點就是復(fù)雜度較高。

(4)Newman快速算法[9-10]。該算法是通過不斷合并節(jié)點來優(yōu)化模塊度的值，根據(jù)最優(yōu)的模塊度確定社團劃分結(jié)果。與GN算法相比，該算法能保持較好的準確性，降低算法的復(fù)雜度。

上述算法均是針對無權(quán)網(wǎng)絡(luò)提出的。由于城市交通網(wǎng)絡(luò)是一個典型的復(fù)雜網(wǎng)絡(luò)，交通路段之間并非完全是布爾關(guān)系，從而存在不同強度的耦合。為了衡量兩點間連邊的緊密程度和重要性，需要用權(quán)值來刻畫不同連邊的強度差異，以此構(gòu)成加權(quán)網(wǎng)絡(luò)。

有一些關(guān)于有權(quán)網(wǎng)絡(luò)社團劃分的研究，比如COPRA[11]和Strength[12]。COPRA是基于PAK[13]提出的方法，在標簽傳播的大部分時間中，它不會收斂到恒定狀態(tài)，而且劃分的社團具有不確定性。Strength利用點權(quán)和隸屬度來檢測重疊的社團劃分，但是隨著重疊的增加，Strength的性能顯著降低。

為此，將區(qū)域交通網(wǎng)絡(luò)視為一個有權(quán)網(wǎng)絡(luò)，提出了一種對Newman快速算法的改進方法，并將該算法應(yīng)用于選定的交通路網(wǎng)，以實現(xiàn)對交通網(wǎng)路的合理劃分。

2 改進算法

2.1參數(shù)定義

邊權(quán)[14]是網(wǎng)絡(luò)用來衡量節(jié)點i與節(jié)點j共享的邊的關(guān)聯(lián)度大小的量，記作wij。wij的值越大，表明節(jié)點i與節(jié)點j之間的關(guān)聯(lián)性越強，即兩點之間的聯(lián)系越緊密。反之，則表明節(jié)點i與節(jié)點j之間的關(guān)聯(lián)性越弱，即兩點之間的關(guān)聯(lián)性越弱。

度[1]是拓撲圖中最為基本的概念之一，某一節(jié)點i的度ki是指與該節(jié)點相接的連邊數(shù)目。節(jié)點的度是權(quán)衡一個節(jié)點重要性的指標之一。在分析網(wǎng)絡(luò)拓撲結(jié)構(gòu)時，可以基本認為某個節(jié)點的度越大，它在網(wǎng)絡(luò)中的重要性就越高。

2.2重新定義社團的模塊度

模塊度[9]是常用的一種評估社團劃分優(yōu)劣的指標。它的提出是基于協(xié)調(diào)理論，主要思想是把劃分社團后的網(wǎng)絡(luò)與相應(yīng)的零模型進行比較，以此判斷劃分的優(yōu)劣。所謂一個網(wǎng)絡(luò)對應(yīng)的零模型，就是指與該網(wǎng)絡(luò)具有某些相同的性質(zhì)而在其他方面完全隨機的隨機圖模型。在無權(quán)網(wǎng)絡(luò)中，其表達式為[16]：

(1)

對于特定網(wǎng)絡(luò)，不一樣的社團劃分結(jié)果對應(yīng)的模塊度值基本是不同的。一個特定網(wǎng)絡(luò)劃分社團，當社團的模塊度最大時，表明此劃分結(jié)果最優(yōu)。此時的模塊度為Qmax，并且有0≤Qmax≤1。實際網(wǎng)絡(luò)的模塊度值一般都在0.3～0.7之間。

(2)

式(2)有一定的物理意義，即網(wǎng)絡(luò)中社團內(nèi)部的邊權(quán)比例減去社團外部邊權(quán)比例的期望值。Qweight的最大值是1，其值越大，表示社團劃分結(jié)果越優(yōu)。

2.3基于Newman快速算法的改進

Newman快速算法是一種自底向上進行的聚合算法，簡稱FN算法，主要步驟如下[8]：

(1)初始化原始網(wǎng)絡(luò)，每個節(jié)點代表一個獨立社團；最初的eij和ai滿足：

(3)

(4)

其中，ki為節(jié)點i的度。

(2)對有邊相連的社團依次合并，同時計算合并后模塊度增量：

ΔQ=eij+eji-2aiaj=2(eij-aiaj)

(5)

依照貪婪算法原理，每次社團合并盡量沿著使Q增大最多或者減少最小的方向進行。每次合并后，更新對應(yīng)元素eij，把與i、j社團相關(guān)的行和列相加。

(3)重復(fù)步驟(2)，不停地將社團合并，直到整個網(wǎng)絡(luò)都合并成一個社團?；诖朔椒?，最多要合并n-1次。

最初的Newman快速算法是針對無權(quán)網(wǎng)絡(luò)提出的，為了使其適用于加權(quán)網(wǎng)絡(luò)，對原有算法進行改進，重新定義eij和ai。邊權(quán)代表兩節(jié)點間的關(guān)聯(lián)性，故

(6)

其中，rij為節(jié)點i和節(jié)點j間邊的權(quán)值。

考慮到點權(quán)、節(jié)點的度都是衡量節(jié)點的重要指標，僅用一個作為節(jié)點重要性的評估過于片面，故由點權(quán)和度一起衡量：

(7)

其中，ki為節(jié)點i的度；m為整片區(qū)域網(wǎng)絡(luò)的連邊數(shù)；0.7和0.3為經(jīng)驗值。

在合并有邊相連的社團的同時，需不停計算ΔQ=eij+eji-2aiaj=2(eij-aiaj)，每一次的合并都要沿著使Q增大最多或減少最小的方向。在合并后都需要更新對應(yīng)元素eij、ai，同時把與i、j社團有關(guān)的行和列相加。根據(jù)以上步驟不斷合并社團，直到整個網(wǎng)絡(luò)都成為一個社團。找到Q值最大時對應(yīng)的社團劃分結(jié)果，即為社團劃分的最優(yōu)解。

3 區(qū)域交通子網(wǎng)劃分

區(qū)域交通的子區(qū)劃分，對研究交通網(wǎng)絡(luò)、提高路網(wǎng)的整體通行效率具有現(xiàn)實意義[17-18]。為了考察改進算法在加權(quán)網(wǎng)絡(luò)[19-20]社團結(jié)構(gòu)劃分的有效性，選取南京仙林地區(qū)的一塊交通區(qū)域，運用改進算法對其進行劃分。為了表征相鄰路口間的關(guān)聯(lián)性，在路口i和路口j之間引入關(guān)聯(lián)度rij。關(guān)聯(lián)度借用牛頓萬有引力定律的形式，定義把兩個路口間的吸引力正比于兩路口間的車流量，反比于兩路口間距離的平方。表達如下：

(8)

式(8)中，V為兩路口間的車流量，單位為1 000輛/時；D為兩路口間路段的距離，單位為km。

該關(guān)聯(lián)度表示：相鄰路口間的距離越小，路口間的關(guān)聯(lián)性越強；相鄰路口的流量越大，路口間的聯(lián)系越強。

3.1路網(wǎng)描述

對圖1中的主干線進行研究，即玄武大道、文瀾路、文苑路、仙林大道、學海路、仙境路、九鄉(xiāng)和西路等路段，該區(qū)域路網(wǎng)中共有16個信號控制路口和23條路段。為了便于分析和對比，對該區(qū)域路網(wǎng)中的各信號路口進行編號，見圖2。

圖1 南京仙林某塊區(qū)域地圖

圖2 南京仙林某區(qū)域點線圖

3.2算法驗證

在無權(quán)網(wǎng)絡(luò)中，應(yīng)用Newman快速算法對圖2所示的區(qū)域路網(wǎng)進行社團劃分，結(jié)果如圖3所示。

圖3 Newman快速算法的劃分結(jié)果

求得Q的最大值為0.397 0。此時最優(yōu)的劃分結(jié)果為：1、2、5、6為一個社團，3、4、9、13、7、8為一個社團，10、14、11、12、15、16為一個社團。通過這樣的劃分結(jié)果，發(fā)現(xiàn)無權(quán)網(wǎng)絡(luò)不能很好地表現(xiàn)路段間的關(guān)聯(lián)性。

通過百度地圖得到每條路段的距離，在互聯(lián)網(wǎng)上查詢到某一天16：00-17：00時段的車流量，運用改進算法對該交通路網(wǎng)進行區(qū)域劃分，結(jié)果如圖4所示。

圖4 改進算法的劃分結(jié)果

運算過程中，Q的值依次為：-0.072 6，0.010 6，0.075 6，0.137 2，0.184 6，0.219 9，0.262 8，0296 4，0.326 4，0.354 4，0.380 2，0.406 5，0.414 9，0.408 5，0.353 8。在Q值達到峰值0.414 9后開始呈下降趨勢。由此可見，當8、9、12、13為一個社團，1、2、3、7、4為一個社團，5、10、11、6為一個社團，14、15、16為一個社團時，得到了最好的社團劃分效果。

這樣的社團劃分結(jié)合了復(fù)雜網(wǎng)絡(luò)度的特性以及路網(wǎng)特有的距離、流通量特性，通過構(gòu)建出邊權(quán)和點權(quán)物理模型，使得劃分出來的結(jié)果可信度更高、更合理。由于車流量隨著時間的變化而不斷改變，可以獲取不同時段的車流量對交通路網(wǎng)進行動態(tài)劃分。根據(jù)新的劃分結(jié)果重新分配路網(wǎng)資源，以此解決同一時段有的路口擁堵、有的路口空閑等資源分配不合理的問題。

4 結(jié)束語

對區(qū)域路網(wǎng)的合理劃分可以提高交通資源的利用率。由于交通路網(wǎng)間點與點的連接并非單純的布爾關(guān)系，基于現(xiàn)有的Newman快速算法對無權(quán)網(wǎng)絡(luò)的劃分方法，提出一種改進算法，并驗證了該算法的有效性及可行性。由于網(wǎng)絡(luò)結(jié)構(gòu)是由網(wǎng)絡(luò)中的各種屬性共同決定，故研究某個網(wǎng)絡(luò)功能與某種網(wǎng)絡(luò)結(jié)構(gòu)之間的關(guān)系，只能得到一個更為合理的結(jié)論，而很難得出一個完全充分的結(jié)果。計算機對大量數(shù)據(jù)處理能力的提升，促進了復(fù)雜網(wǎng)絡(luò)研究的蓬勃發(fā)展，而對社團結(jié)構(gòu)的深入探究也推進了計算機圖形學的發(fā)展。

[1] 汪小帆,李 翔,陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學出版社,2006.

[2] 王 浩，李國歡，姚宏亮，等.基于影響力計算模型的股票網(wǎng)絡(luò)社團劃分方法[J].計算機研究與發(fā)展，2014，51(10)：2137-2147.

[3] Karrer B,Newman M E J.Stochastic block models and community structure in networks[J].Physical Review E，2011，83(1)：016107.

[4] Kernighan B W， Lin S. An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal，1970，49(1)：291-307.

[5] Pothen A，Simon H D，Liou K P.Partitioning sparse materices with eigenvectors of graphs[J].SIAM Journal on Matrix Analysis Applications，1990，11(3)：430-452.

[6] Givran M，Newman M E J.Community structure in social and biological networks[EB/OL].[2008-12-07].http://www.biomedsearch.com/nih/Community-structure-in-social-biological/12060727.html.

[7] Radicchi F,Castellano C,Cecconi F,et al.Defining and identifying communities in networks[J]. Eur. Phys. J. B，2004,101(9):2658-2663.

[8] Duch J,Arenas A.Community detection in complex networks using extremal optimization[J].Physical Review E,2005,72(2):027104.

[9] Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.

[10] Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):066133.

[11] Gregory S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):103018.

[12] Chen D,Shang M,Lv Z,et al.Detecting overlapping communities of weighted networks via a local algorithm[J].Physica A Statistical Mechanics & Its Applications,2010,389(19):4177-4187.

[13] Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E,2007,76(3):036106.

[14] Li M，F(xiàn)an Y，Chen J，et al.Weighted networks of scientific communication:the measurement and topological role of weight[J].Physica A Statistical Mechanics & Its Applications，2005，350(2-4)：643-656.

[15] 王天成,劉真真,李天明，等.復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)劃分方法及其應(yīng)用[J].信息通信,2015(8)：43-45.

[16] 陳寧寧.信號控制子區(qū)動態(tài)劃分及區(qū)域自適應(yīng)協(xié)調(diào)控制研究[D].廣州:中山大學,2010.

[17] 王秀風,馬英紅.基于加權(quán)網(wǎng)絡(luò)模塊強度的社團劃分[J].計算機應(yīng)用研究，2013,30(3):695-698.

[18] 劉傳建.復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)劃分及分析應(yīng)用[D].濟南:山東大學,2014.

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

[20] 安 娜,謝福鼎,張 永,等.一種基于GN算法的文本概念聚類新方法[J].計算機工程與應(yīng)用,2008,44(14):142-144.

Research on Regional Transportation Sub-netting Method withWeighted Network

LIN Dan，LUO Jie

(College of Automation，Nanjing University of Posts and Telecommunications，Nanjing 210000,China)

Traffic jam has become an inevitable problem in the world and caused a lot of attentions from scholars.Dynamic partition of traffic area is an effective solution to improve the efficiency for entire area traffic system.With the rapid development of the computer technology,the theory of complex networks has made a breakthrough.Therefore,on the basis of community structure partition on complex network,by taken the flow characteristics of traffic network as weight,an improved algorithm for no-weighted network community division is proposed.It refers to traffic flow and distance of the highway as reference factors for weight and combined with complexity of network,has enhanced the reliability of community structures by taken ModularityQas evaluation standard for different partition result.To verify its effectiveness and feasibility,the simulation experiments are carried out based on the computer program self-compiled,which indicate that it is effective and feasible according to the contrast analysis onQvalue before and after modification and has the potential of real-time dynamic division of traffic area.

traffic area;community structure;traffic flow;distance of highway

2016-08-27

：2016-12-01 < class="emphasis_bold">網(wǎng)絡(luò)出版時間

時間：2017-07-05

江蘇省自然科學基金項目(BK2011758)

林 丹(1990-),女，碩士，研究方向為智能控制；羅 杰，博士，教授，研究方向為分布式智能控制、群體智能。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170705.1650.044.html

TP301

:A

:1673-629X(2017)09-0120-04

10.3969/j.issn.1673-629X.2017.09.026