基于有權網絡的區域交通子網劃分方法研究

林 丹，羅 杰

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

基于有權網絡的區域交通子網劃分方法研究

林 丹，羅 杰

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

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

交通區域；社區結構；車流量；路段距離

1 概 述

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

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

網絡社團結構的劃分與分級聚類以及圖形分割都有著密切關系。下面列舉一些經典的社團劃分算法：

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

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

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

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

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

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

為此，將區域交通網絡視為一個有權網絡，提出了一種對Newman快速算法的改進方法，并將該算法應用于選定的交通路網，以實現對交通網路的合理劃分。

2 改進算法

2.1參數定義

邊權[14]是網絡用來衡量節點i與節點j共享的邊的關聯度大小的量，記作wij。wij的值越大，表明節點i與節點j之間的關聯性越強，即兩點之間的聯系越緊密。反之，則表明節點i與節點j之間的關聯性越弱，即兩點之間的關聯性越弱。

度[1]是拓撲圖中最為基本的概念之一，某一節點i的度ki是指與該節點相接的連邊數目。節點的度是權衡一個節點重要性的指標之一。在分析網絡拓撲結構時，可以基本認為某個節點的度越大，它在網絡中的重要性就越高。

2.2重新定義社團的模塊度

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

(1)

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

(2)

式(2)有一定的物理意義，即網絡中社團內部的邊權比例減去社團外部邊權比例的期望值。Qweight的最大值是1，其值越大，表示社團劃分結果越優。

2.3基于Newman快速算法的改進

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

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

(3)

(4)

其中，ki為節點i的度。

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

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

(5)

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

(3)重復步驟(2)，不停地將社團合并，直到整個網絡都合并成一個社團。基于此方法，最多要合并n-1次。

最初的Newman快速算法是針對無權網絡提出的，為了使其適用于加權網絡，對原有算法進行改進，重新定義eij和ai。邊權代表兩節點間的關聯性，故

(6)

其中，rij為節點i和節點j間邊的權值。

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

(7)

其中，ki為節點i的度；m為整片區域網絡的連邊數；0.7和0.3為經驗值。

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

3 區域交通子網劃分

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

(8)

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

該關聯度表示：相鄰路口間的距離越小，路口間的關聯性越強；相鄰路口的流量越大，路口間的聯系越強。

3.1路網描述

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

圖1 南京仙林某塊區域地圖

圖2 南京仙林某區域點線圖

3.2算法驗證

在無權網絡中，應用Newman快速算法對圖2所示的區域路網進行社團劃分，結果如圖3所示。

圖3 Newman快速算法的劃分結果

求得Q的最大值為0.397 0。此時最優的劃分結果為：1、2、5、6為一個社團，3、4、9、13、7、8為一個社團，10、14、11、12、15、16為一個社團。通過這樣的劃分結果，發現無權網絡不能很好地表現路段間的關聯性。

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

圖4 改進算法的劃分結果

運算過程中，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為一個社團時，得到了最好的社團劃分效果。

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

4 結束語

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

[1] 汪小帆,李 翔,陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社,2006.

[2] 王 浩，李國歡，姚宏亮，等.基于影響力計算模型的股票網絡社團劃分方法[J].計算機研究與發展，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，Fan 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] 王天成,劉真真,李天明，等.復雜網絡社團結構劃分方法及其應用[J].信息通信,2015(8)：43-45.

[16] 陳寧寧.信號控制子區動態劃分及區域自適應協調控制研究[D].廣州:中山大學,2010.

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

[18] 劉傳建.復雜網絡中的社團結構劃分及分析應用[D].濟南:山東大學,2014.

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

[20] 安 娜,謝福鼎,張 永,等.一種基于GN算法的文本概念聚類新方法[J].計算機工程與應用,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">網絡出版時間

時間：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