0 引言
交通運輸體系是國家發展社會進步的基礎，城市繁榮的先決條件之一變取決于城市的交通條件�，F在城市快速發展，導致日益嚴重的交通問題，成為影響城市發展的道路的瓶頸。
城市外部交通，對城市經濟發展，資源與原材料的運輸等有為重要，城市所在怎樣的社團中，便應該采取相應的經濟發展戰略。為了解決上述問題，各界學者使用數據挖掘理論、圖論、交通工程科學、現代控制理論與方法等，對于交通網絡從不同的角度來研究。本文將分析城市間交通網絡結構，找到網絡中的社團結構，可以為城市發展提供一定的理論依據，為城市發展進行定位。
社團結構是一個網絡概念，在網絡中存在著一定數量的團和群，在其內部結點聯系相對緊密，但是在他們之間結點聯系相對稀疏。這個聯系相對緊密的結點就構成了我們所說的社團。在大量的關于社團的研究中發現社會網絡都存在社團，于社團結構的深入研究有助于分析和了解實際系統的結構和特性，便于對網絡進行優化和管理。在城市間交通網絡中，將城市和連通城市的道路（公路，鐵路等）看成是有向圖，城市就被看成了圖中的結點，將連接城市的各種級別的道路看作為邊(EDGE)。于是我們便建立了城市交通網絡，以此為基礎，分析城市的交通網絡的社團結構
1 準備工作
為了便于算法的介紹，對已生成的網絡圖以及相關概念進行數學描述和說明。在圖論中，網絡圖一般表示為圖G=(V,E)， 其中集合V表示為所有頂點vi的集合，集合E為連接頂點邊eij的集合。若Aij為圖G的鄰接矩陣，對于G中的結點Vi，其度值（Degree） 
�？紤]一個子圖，若
，則節點i的度值可以兩個部分，一部分是節點i與屬于W的節點相連的邊數：
；另一部分是節點i與W以外的節點相連的邊數
。如果下面的公式成立，我們則說W是G中的一個社團。
，
其中如果
越大則說明社團結構越明顯。
圖1 社團結構示意圖
2 社團劃分算法
對于社團目前存在的社團劃分算法有很多，但是部分社團劃分的準確性還有待提高，而且大部分社團劃分算法都是針對無權圖。對于本文對城市間交通的社團劃分其模型應該為有權圖。所以本文采用是社團劃分中一種分裂算法。其基本思想是在網絡中不斷的除去邊介數（edge Betweenness）值最大的邊，直到網絡分解成一定社團。所謂邊介數，就是通過該邊的最短路徑的條數, 它表示該邊在網絡中通過的路段的邊介數越大, 其對整個交通網絡的越重要，說明此邊在網絡中起到中樞的作用越明顯，在網絡中的活躍狀態越高。
邊介數的數學定義可以表示為：在圖G=(V,E)中，設σst(e)代表從節點s到節點t的最短路徑經過邊e∈E 的數目，邊e的兩個端點分別為u、v。計算各邊的介數，是挖掘社團的重要準備工作之一，對此的算法描述如下：
1． 初始化全部M條邊的邊介數B=(b1,b2,b3…bm),bi=0;
2． 依次遍歷網絡中圖G中的節點，對遍歷過的節點V[j]做標記，設當前遍歷節點為中心節點；
3． 利用最短路徑算法計算此時的中心節點與全部其他節點的之間最短路徑數，將每條邊的最短路徑數量記錄到數組B中。
4． 繼續遍歷節點
5． 判斷是否全部遍歷節點，如果是則將B’=B/2，如果不是則回到步驟2
最終計算出的每條邊的數值嚴格等于此邊中介度確切值的兩倍，因為上述算法將一對端點之間的路徑重復計算了兩次。
在計算出邊介數后，我們依次除去邊介數最大的邊，然后重新計算邊介數。本算法的時間復雜度為 O( n 3)，在中型網絡（節點數小于10000）的時候可以得到較好的計算效果。
在使用該算法分割的時候，在事先不知道社團的準確數量的時候，該算法會反復去邊，直到沒有邊為止。但是這顯然不是我們想得到的結果，如何才能得到我們想要的符合真實情況的社團，我們必須確定社團劃分可以自動停止的條件。為此我們引進模塊度來判斷社團的劃分情況。
假設我們將網絡劃分為k個社團。定義一個k*k的矩陣，其元素表示在網絡中連接兩個不同社團間節點的邊在所有邊中所占的比例；例如元素eij表示社團i與社團j此時相連的邊數與所有邊的比例。
我們將矩陣中對角線上各元素加和為定
。它給出了網絡中連接某一個社團內部各節點的邊在所有邊的數目中所占比例。定義每行（ 或者列）中各元素之和為
，它表示與第i個社團中的節點相連的邊在所有邊中所占的比例。在此基礎上，用下式來定義模塊性的衡量標準：
Q =
= Tre - ||e2||
其中|x| 表示矩陣|x|中所有的元素之和。上式的物理意義可以解釋為：網絡中連接兩個同種類型的節點的邊（即社團內部邊）的比例減去在同樣的社團結構下任意連接這兩個節點的邊的比例的期望值。如果社團內部邊的比例不大于任意連接時的期望值，則有Q = 0，Q 的上限為Q = 1，而Q 越接近這個值，就說明社團結構越明顯。有了社團劃分的模塊度，我們便可以得到相對準確的社團劃分。
3 系統的設計與實現
本設計是基于下一代互聯網的智能交通監控管理系統的一個子功能（見圖2）。由于已獲得的全國地圖數據相對比較粗略，連接城市間的道路只有高速公路、國家一級公路、國家二級公路和國家三級公路。但這幾級公路承擔了城市間的絕大部分的運輸功能，所以分析這幾種道路仍然十分具有意義。
在具體的設計中我們選取長江三角洲的江蘇，浙江，上海，這三個省市作為分析目標，這塊區域經濟發達，城市密集，交通距離較近，相互之間經濟交往密切，分析此處可以為城市發展提供建議，有利于城市經濟發展定位。
圖2 分析地區圖示
我們將江浙滬等三地的所有縣市抽象為圖中的節點，將連接他們的道路看作邊，但是在道路中存在各種等級，不同等級的道路其運輸能力也大不相同，按使用任務功能和適應交通量劃分分為高速公路、一級公路、二級公路、三級公路、四級公路5個等級。一般六車道高速公路可適應各種汽車合成小客車的年平均日交通量45000-80000輛，一級公路可適應各種汽車折合小客車的年平均交通量為25000-55000輛，二級公路可適應年日平均量為3000~7500輛，三級公路可適應日平均1000-3000輛的交通量，由上述數據表明得出，在不同道路間，交通運輸量存在很大的差別，也就是說如果想要得到比較真實地社團劃分結構，我們的模型應該變成有權網絡。
對有權網絡進行分析，其實對原有算法并不需要做太大的改動，在有權圖G(V,E,W)中其中集合V表示為所有頂點vi的集合，集合E為連接頂點的邊eij的集合，集合W為邊上的權值wij的集合，首先我們利用前面提到的計算無權網絡邊介的算法計算出無權網絡bij ，然后計算加權網中邊介數值，即Bij= bij/wij ，最后刪除邊介數最大的邊。接著要為各級公路確定權值，經過對各級道路的交通流量的分析得到權值比例，由于數據資料有限，還無法得到準確的交通道路流量，我們只能根據具體的道路級別來對道路交通量權值進行約分后的粗略賦值（見表[1]）。
|
道路級別 約分后交通流量權值 |
|
八車道高速公路 320
六車道高速公路 250
一級公路 125
二級公路 21
三級公路 8 |
表1 道路權值表
由于連接城市的道路可能存在不同的級別的道路，如前半段為一級公路，后半段為二級公路，所以連接行政區域節點的道路的權值取其中的最小值，這也代表的整個道路的運輸能力。
具體實現過程見圖3，我們的地圖數據是從文件中讀取得，經過一定的預處理，去除地圖數據中一些重復的道路和一些無用的關聯，抽象出城市區域，將道路與道路級別信息存入數據庫，根據上述信息抽象出城市區域交通網絡，進行社團分析，最后得到分析結果。
結果：Q值達到峰值時存在4個社團，長三角地區，圍繞上海周圍出現了一個較明顯的社團。在蘇北地區有兩個比較松散的社團，浙江南部出現了一個相對緊密的社團
圖3 系統流程圖
4 下一步工作
在整個的設計與實現的過程中，只是對公路網絡進行了分析，并沒有結合在交通運輸中占有很大比例的鐵路運輸和航空運輸進行分析，其原因是沒有找到足夠的數據。下一步工作我們將三者結合起來分析，同時增加對具體城市分析的功能，例如如果增加哪幾條公路，可以使某城市劃歸為某社團，或是如果新建某一級別的公路，可否將某城市回歸為一個新的社團。此類功能將有助于為政府決策，明確城市的定位，優化交通的資源配置 ，提高資源利用率。
結束語
本文提出將社團劃分與城市間公路運輸網絡結合起來，使用社團劃分算法，對有權網絡進行社團劃分，并以長江三角流域為例，進行了設計與應用，下一步我們將在城市運輸網絡中加入鐵路運輸，航空運輸。同時還將增加對具體城市的分析，提供如何加入其它優質社團的建議。
參考文獻:
［1］ M. Girvan, M E J Newman. Community structure in social and biological networks[J]. Proc Natl Acad Sci,001,9 (12)
［2］M.E.J. Newman, M. Girvan, Finding and evaluating community structure in networks[J]. Physical Review, E 69(026113), 2004.
［3］ 解㑇,汪小帆.復雜網絡中的社團結構分析算法研究綜述[J].復雜系統與復雜性科學,2005,2 (8):4-6.
［4］ 王喆,彭其淵.成都市公交復雜網絡拓撲特性研究[J]. 交通與計算機.2007, 2:4-6.
［5］ 汪小帆,李翔,陳關榮.復雜網絡理論及其應用[M].清華大學出版社. 2006 年4月
