孫 琳，郭進利 （上海理工大學(xué)，上海200093）

SUN Lin, GUO Jin-li (University of Shanghai for Science and Technology, Shanghai 200093, China)

0 引 言

18 世紀數(shù)學(xué)家歐拉對七橋問題的建模和分析開創(chuàng)了數(shù)學(xué)中圖論這一分支，此后就有很多學(xué)者利用圖論和復(fù)雜網(wǎng)來研究實際問題，來分析網(wǎng)絡(luò)中存在的問題。復(fù)雜網(wǎng)絡(luò)應(yīng)用于對軌道交通的研究更成為熱點問題，惠偉等[1]采用復(fù)雜網(wǎng)絡(luò)以上海和北京公交線路為例通過計算復(fù)雜網(wǎng)絡(luò)的靜態(tài)特征值顯示北京和上海的公交網(wǎng)絡(luò)具有小世界特性。Latora 等[2]用復(fù)雜網(wǎng)絡(luò)對波士頓地鐵的網(wǎng)絡(luò)特性進行初探。汪濤[3]等對北京、上海、廣州三個城市地鐵網(wǎng)絡(luò)特征進行比較。楊楊[4]等對北京公共交通網(wǎng)絡(luò)進行建模實證分析和對蓄意攻擊做了有效的分析，有些學(xué)者對上海地鐵當前網(wǎng)絡(luò)和規(guī)劃網(wǎng)絡(luò)做了特性分析，得出重要節(jié)點不斷向外部轉(zhuǎn)移。以前的研究方式多限于研究節(jié)點與邊同質(zhì)的網(wǎng)絡(luò)，無法完全刻畫現(xiàn)實網(wǎng)絡(luò)復(fù)雜性的特征，如生態(tài)網(wǎng)絡(luò)和電力網(wǎng)絡(luò)，前者節(jié)點不同質(zhì)，后者邊不同質(zhì)。隨著交通網(wǎng)絡(luò)的發(fā)展，出現(xiàn)了鐵路網(wǎng)、公路網(wǎng)、航空網(wǎng)等許多復(fù)雜的網(wǎng)絡(luò)，這些網(wǎng)絡(luò)節(jié)點和邊的數(shù)量眾多，結(jié)構(gòu)復(fù)雜，我們已經(jīng)不能用傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)去研究軌道交通網(wǎng)絡(luò)。

超網(wǎng)絡(luò)也是一種特殊的復(fù)雜網(wǎng)網(wǎng)絡(luò)，它既可完美刻畫現(xiàn)實網(wǎng)絡(luò)特征，本身又為綜合網(wǎng)絡(luò)，故超網(wǎng)絡(luò)研究必將成為網(wǎng)絡(luò)研究新潮流。大量學(xué)者對復(fù)雜網(wǎng)絡(luò)進行研究，有些人擺脫了還原論的局限性，開始研究網(wǎng)絡(luò)與網(wǎng)絡(luò)之間的影響，超網(wǎng)絡(luò)概念就被提出。對超網(wǎng)絡(luò)的研究不僅有實際意義，也為研究系統(tǒng)的復(fù)雜性提出一種新的想法。最早使用超網(wǎng)絡(luò)概念與運輸系統(tǒng)的是Y.Sheffi[5]，而美國科學(xué)家A. Nagurney[6]在處理上述交織的網(wǎng)絡(luò)，把高于而又超于現(xiàn)存網(wǎng)絡(luò)的網(wǎng)絡(luò)稱為超網(wǎng)絡(luò)，使超網(wǎng)絡(luò)的定義開始明確。后來Berge[7-8]在1970 年提出了什么是超圖的概念，并描述了無向超圖理論，隨后研究者對超圖的超回路、著色和t-設(shè)計[9]等問題進行研究。21 世紀，大量研究者將超圖理論以超網(wǎng)絡(luò)的形式用于現(xiàn)實問題研究，如Bretto[10]用超網(wǎng)絡(luò)于研究圖像的處理，李曉強[11]用超網(wǎng)絡(luò)對基于變分不等式的電子商務(wù)進行研究，Wang Z P[12]等用超網(wǎng)絡(luò)來研究供應(yīng)鏈，并且構(gòu)建由兩個制造商、兩個分銷商和兩個需求市場組成的供應(yīng)鏈超網(wǎng)絡(luò)模型從而解決了各層次多標準優(yōu)化的問題。

基于軌道交通網(wǎng)絡(luò)的復(fù)雜性，本文從超網(wǎng)絡(luò)視角對上海軌道交通進行研究，得到用超網(wǎng)絡(luò)的度分布和聚類系數(shù)，分析軌道交通網(wǎng)絡(luò)的特性，并提出一些規(guī)劃建議。

1 超網(wǎng)絡(luò)的定義

目前對超網(wǎng)絡(luò)的研究還處于起步階段，有一些概念還沒有得到公認。但是已經(jīng)有人從不同的視角來定義超網(wǎng)絡(luò)。目前對超網(wǎng)絡(luò)的定義有兩種。

1.1 H. Frank 等在文獻[13]中給出的定義

超網(wǎng)絡(luò)里的節(jié)點表示給定集合的網(wǎng)絡(luò)，而邊和弧表示在給定集合中的結(jié)合移動和結(jié)合偏好，超網(wǎng)絡(luò)唯一地表示由規(guī)則支配的所有結(jié)合移動和偏好。

1.2 用超圖來定義超網(wǎng)絡(luò)

超圖[14]定義：設(shè)V=｛v1,v2,…,vn｝是一個有限集。若：（1）

則稱二元關(guān)系H=（E,V）為一個超圖。V的元素v1,v2,…,vn稱為超圖頂點，E=｛e1,e2,e3,…,en｝是超圖的邊集合，集合e的元素eI=｛Vi1,Vi2,…,Vij｝（i=1,2,3,…,m）稱為超圖的邊。如果兩個頂點屬于同一條超邊，則稱這兩個頂點鄰接；如果兩條超邊的交集不空，稱為兩條超邊鄰接。如果一個超圖H的任意兩條超邊至多有一個公共點，則稱H為簡單超圖。

1.3 超網(wǎng)絡(luò)相關(guān)定義

1.3.1 關(guān)聯(lián)矩陣[14]定義

一個圖G= V,（）E的關(guān)聯(lián)矩陣B滿足下面條件：（1）B的每一行與G的頂點相關(guān)； （2）B的每一列與G的邊相關(guān)聯(lián)；（3） 如果第j個邊與第i個頂點相關(guān)聯(lián)，那么bij=1。

有n個頂點的聯(lián)通圖G的關(guān)聯(lián)矩陣的秩是n-1。在上海軌道交通中，每一行與軌道交通站點有關(guān)，每一列與軌道交通線路有關(guān)，如果行中的站點在列中的線路中則在關(guān)聯(lián)矩陣中寫1 否則寫0。

1.3.2 鄰接矩陣[14]

一個圖G= V,（）E的鄰域矩陣S，滿足下列條件：（1）S的每一行與G的頂點相關(guān)；（2）S的每一列與G的頂點相關(guān)；（3） 如果頂點vi與vj之間存在一個關(guān)系，即存在一個弧，鏈接著頂點vi與vj，那么sij=1；存在兩個弧sij=2；否則，sij=0。

在上海軌道交通超網(wǎng)絡(luò)中，鄰接矩陣的每行和每列都與站點有關(guān)，在站點與站點之間由地鐵形成的線路相連，當行中的站點與列中的站點在同一條線（一條弧） 中，則Aij=1。當行中站點與列中站點在共同的兩條線路（兩條?。?中則Aij=2，如果兩個站點沒有在共同的線路中，則Aij=0。上海軌道交通的鄰接矩陣A如下。

當A22=0 表示兩個站點是同一個站點；

當A23=2 表示第2 個站點和第3 個站點有兩條共有的線路；

當A2811=0 表明第281 個站點和第1 個站點沒有在共同的線路中。

2 超網(wǎng)絡(luò)度

對上海軌道交通286 個站點14 條線路進行統(tǒng)計，得到其度分布。

2.1 節(jié)點度

節(jié)點度[15]（Node Hyperdegrees） 節(jié)點連接的頂點數(shù)計為d（）i，在軌道交通網(wǎng)絡(luò)中節(jié)點是每個站點，超邊是每條地鐵線路，節(jié)點度描述的是一個站點與其他站點的連接程度。上海市軌道交通超網(wǎng)絡(luò)的節(jié)點度分布和累計度分布如圖1、圖2 所示。

由圖1 可以看出節(jié)點度大部分在20 到40 之間，說明上海軌道交通網(wǎng)絡(luò)站點之間的連通程度還是很小，可以計算出上海軌道交通所有節(jié)點度的平均值為31.51049，可以參考這個數(shù)值對包含站點少的線路進行調(diào)整和改造。由圖2y=2.1408e-0.0577x可知節(jié)點度的累計分布符合指數(shù)分布。

2.2 節(jié)點超度

節(jié)點超度[15]（Node Hyperdegrees） 節(jié)點的超度定義為包含該節(jié)點的超邊個數(shù), 記為dH（）i。在軌道交通網(wǎng)絡(luò)中，每個站點是節(jié)點，節(jié)點超度指的是有多少條超邊經(jīng)過同個站點。上海市軌道交通超網(wǎng)絡(luò)的節(jié)點超度的分布和累計超度分布如圖3、圖4 所示。

由圖3 可知，軌道交通網(wǎng)大部分站點的節(jié)點超度值為1，占整個網(wǎng)絡(luò)的80%以上，表明大部分站點只有一條軌交線路經(jīng)過。經(jīng)計算，該網(wǎng)絡(luò)的平均節(jié)點超度為1.188811，說明可換成的站點還是比較少。圖4 雙對數(shù)坐標中對散點圖的擬合表明，節(jié)點度的累計概率分布p（k）服從冪律分布。網(wǎng)絡(luò)的擬合結(jié)果為y=1.3885x-3.8216，可見從節(jié)點超度分析可得上海軌道交通網(wǎng)絡(luò)具有無標度網(wǎng)絡(luò)的特性。

計算軌道交通超網(wǎng)絡(luò)節(jié)點超度和節(jié)點度按照節(jié)點超度的前11 個站點列表如表1 所示。

從表1 可知，按節(jié)點超度從大到小排列，前11 個站點相應(yīng)的節(jié)點度如表1 所示。經(jīng)統(tǒng)計，節(jié)點度和節(jié)點超度排名前10 的站點相同，金沙江站節(jié)點超度是第11，但節(jié)點度不是排名前11，說明13 號線路可以增加站點。由表1 可知前10 個站點節(jié)點度和節(jié)點超度都很大，所以這幾個站點是上海軌道交通的重要站點，應(yīng)該加強對這幾個站點的保護，從而使整個交通網(wǎng)絡(luò)高效率運行。

圖1 軌道交通超網(wǎng)絡(luò)節(jié)點度分布

圖2 軌道交通超網(wǎng)絡(luò)節(jié)點度的累計概率分布

圖3 超網(wǎng)絡(luò)節(jié)點超度的概率分布

圖4 超網(wǎng)絡(luò)節(jié)點超度的累計概率分布

表1 站點節(jié)點度和節(jié)點超度對比表

2.3 邊超度

邊超度[15]（Hyperedge Degrees） 如果兩條超邊有相同節(jié)點，則這兩條超邊通過該節(jié)點相連。邊超度為與該超邊相連的其它超邊的數(shù)。上海市軌道交通超網(wǎng)絡(luò)的邊超度的分布和累計超度分布如圖5、圖6 所示。

由圖5 可知邊超度是9 的線路占的比例最大，其次是邊超度為7 的線路。說明有些線路與其他線路之間的聯(lián)系很少，比如5 號線和16 號線。像邊超度比較小的線路可以成為以后規(guī)劃的重點線路。經(jīng)計算網(wǎng)絡(luò)的平均邊超度為6.571429，可以看出邊與邊之間的聯(lián)系還比較少，對小于平均邊超度的線路應(yīng)進行調(diào)整和改造。對于邊超度較大的線路進行重點保護，以免被蓄意攻擊，導(dǎo)致整個交通的癱瘓。

3 軌道交通超網(wǎng)絡(luò)的聚集系數(shù)

H=（V,E）表示一個簡單超圖，節(jié)點集V=｛v1,v2,…,vN｝，超邊集E=｛E1,E2,…,Em｝，鄰接矩陣A（H）是對稱方陣，元素aij為連接節(jié)點vi和vj的超邊條數(shù)，主對角線上的元素為零。假設(shè)H是有N個節(jié)點的簡單超圖，它的鄰接矩陣A是一個是對稱矩陣，因此存在一個正交矩陣U=uij，使得A=UDUT，其中：D=diag（λ1,λ2,…,λn），U的列向量是與A的特征值相對應(yīng)的正交向量。

設(shè)vi和vj是超圖H的兩個節(jié)點，A是H的鄰接矩陣，那么H中長度為k的從vi到vj的路徑（對應(yīng)于復(fù)雜網(wǎng)絡(luò)，也稱為vi-vj鏈） 的個數(shù)就可以用矩陣Ak第i行第j列的元素值來表示。

圖5 邊超度的概率分布

圖6 邊超度的累計概率分布

H中長度為k的vi-vj鏈的條數(shù)為因此，H中長度為k的所有鏈的條數(shù)為：

H中從vi開始最后又回到vi的長度為k的閉合鏈的條數(shù)則由給出，是Ak的第i個對角線元素的值：

那么H中長度為K的閉合鏈的總條數(shù)就是：

聚類系數(shù)的理論來源是社會學(xué)文獻中的傳遞系數(shù)：

其中分子中的6 表示一個三角形可以形成6 條長度為2 的路徑，從而保證當圖KN是完全連通圖時C2（G）=1。由于上面的結(jié)論只適合沒有重邊的簡單圖，因此當所研究的網(wǎng)絡(luò)中有重邊時就將其化為簡單圖再計算聚類系數(shù)，所以將（4） 式推廣到超網(wǎng)絡(luò)中可以得到超網(wǎng)絡(luò)的聚類系數(shù)[16]如下：

其中超三角形是由三個不同的節(jié)點和三條不同的超邊組成的一個序列其中這三個點彼此相連而長度為2 的路徑則形如vi,Ep,vj,Eq,vk的序列。

我們可以用長度為3 的閉合鏈的個數(shù)來計算超網(wǎng)絡(luò)中超三角形的個數(shù)，但是必須減去不能形成超三角形的長度為3 的閉合鏈（假超三角形） 的個數(shù)。

假超三角形形成的原理：假超三角形三個頂點在同一條超邊里。所有三條邊都是同一條超邊Ei的假超三角形個數(shù)為ti其中為超邊Ei1,Ei2,…,Eij交的基數(shù)用ai1,ai2,…,aij表示。因此假超三角形個數(shù)：

同理在計算長度為2 的路徑時，需要計算兩個節(jié)點在同一條超邊Ei的長度為2 的假的路徑數(shù)，p=6t所以超網(wǎng)絡(luò)的聚集系數(shù)由（1）、（3）、（5）、（6） 式可以得：

整理上式可得：

在地鐵網(wǎng)絡(luò)中超網(wǎng)絡(luò)的鄰接矩陣是286 行286 列的矩陣，由鄰接矩陣A通過Matlab 編程計算可以得到正交矩陣u=u286,286和其相對應(yīng)的特征值和特征向量，從而得到：

把式（9）、（10）、（11）、（12） 代入公式（8） 中可以得到：

式（13） 中C2（H）為整個網(wǎng)絡(luò)的聚類系數(shù)，可以反映整個超網(wǎng)絡(luò)中節(jié)點的緊密性網(wǎng)絡(luò)的聚類一般在[0,1]之間，相對于中間值0.5 是比較小的，另外我們用超網(wǎng)絡(luò)來計算2020 地鐵規(guī)劃網(wǎng)絡(luò)的聚類系數(shù)得到0.4763668932，相對來說目前網(wǎng)絡(luò)的聚類系數(shù)比較小，表明目前網(wǎng)絡(luò)的密集度比較差，這也與我國軌道交通建設(shè)處于初級階段的情況相符。還需要更多的發(fā)展過程。

4 結(jié)論和展望

基于超網(wǎng)絡(luò)方法研究上海市軌道交通網(wǎng)絡(luò)，通過分析和研究得到以下結(jié)論:

（1） 從節(jié)點度分布和節(jié)點超度分布可以看出，上海軌道交通網(wǎng)絡(luò)節(jié)點超度為前10 的站點，節(jié)點度的大小也是前10，從超網(wǎng)絡(luò)的節(jié)點度和節(jié)點超度都可以得到世紀大道、東方體育館、曹楊路、徐家匯、鎮(zhèn)平路、人民廣場、虹橋路、金沙江路、中山公園、宜山路站點的節(jié)點度和節(jié)點超度都很大，說明這幾個站點是關(guān)鍵節(jié)點。但是兩種度的值又不是相同的。其中節(jié)點超度的累計度分布跟復(fù)雜網(wǎng)絡(luò)中的累計度分布都符合冪律分布。節(jié)點超度度大的站點是關(guān)鍵節(jié)點，如果對度大的這些站點進行蓄意攻擊，整個網(wǎng)絡(luò)會癱瘓。目前對超網(wǎng)絡(luò)的蓄意攻擊還沒有深入的研究，在后續(xù)的文章中會對超網(wǎng)絡(luò)的蓄意攻擊做出解釋。

（2） 從邊超度分布可以看出1、2、4、8、11 號線邊超度較大，應(yīng)重點保護這幾條線，保證這幾條線路的可靠性。對于邊超度較小的線路應(yīng)該進行改造和擴展，來使整個網(wǎng)絡(luò)的輻射半徑增大。

（3） 從聚類系數(shù)可以看出目前上海軌道交通的密集程度比較小，隨著城鎮(zhèn)人口的增加應(yīng)加強對我國軌道交通的建設(shè)。

用超網(wǎng)絡(luò)研究軌道交通還處于起步階段，對于一些超網(wǎng)絡(luò)的靜態(tài)特征還沒有確切的定義。隨著線路的增加用超網(wǎng)絡(luò)的節(jié)點超度來研究交通網(wǎng)絡(luò)更加方便?？梢詫⒊W(wǎng)絡(luò)應(yīng)用于全國鐵路網(wǎng)絡(luò)，同樣比用復(fù)雜網(wǎng)絡(luò)來研究全國鐵路網(wǎng)絡(luò)方便。當然也可以用超網(wǎng)絡(luò)來研究公交網(wǎng)絡(luò)甚至航空網(wǎng)絡(luò)。對于公交和地鐵網(wǎng)絡(luò)的換乘也提供了很好的思路。

[1] 惠偉，王紅. 復(fù)雜網(wǎng)絡(luò)在城市公交網(wǎng)絡(luò)中的實證分析[J]. 計算機技術(shù)與發(fā)展，2008(18):217-222.

[2] Latora V, Massimo M. Is the Boston Subway a small-world network[J]. Physica A, 2002,314:109-113.

[3] 汪濤，方志耕,等. 城市地鐵網(wǎng)絡(luò)的復(fù)雜性分析[J]. 軍事交通學(xué)院學(xué)報，2008,10(2):24-27.

[4] 楊楊，關(guān)偉. 北京市公共交通網(wǎng)絡(luò)復(fù)雜性分析[D]. 北京：北京交通大學(xué)（碩士學(xué)位論文），2011:59-63.

[5] Sheffi Y. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods[M]. Printice-Hall,1985:33-89.

[6] Anna Nagurney, J. Dong. Supernetworks: Decision-Making for the Information Age[M]. Cheltenham Edward Elgar Publishing,2002:1-368.

[7] BERGE C. Graphs and hypergraphs[M]. New York: Elsevier, 1973:389-391.

[8] BERGE C. Hypergraphs: The theoryoffinite sets[M]. Amsterdam: Elsevier Science, 1989:1-2.

[9] TUANND. Hypergraphical t-designs[J]. Discrete Mathematics, 2006,306:1189-1197.

[10] BRETTOA, GILLIBERYL. Hypergraph-based image representation[J]. Lecture Notes in Computer Science, 2005,35:1-11.

[11] 李曉強. 基于變分不等式的電子商務(wù)超網(wǎng)絡(luò)研究[D]. 大連：大連海事大學(xué)（碩士學(xué)位論文），2006:8-50.

[12] Wang. Zhang FM, Wang Z T. Research on return supply chain supernetwork model based on variationalinequalities[C]//Proceeding of 2007 IEEE international conference on automation and logistics. Jinan, China, 2007:25-30.

[13] Frank H, Page J, Myrna H, et al. Networks and farsighted stability[J]. Journal of Economics Theory, 2005,120(2):257-269.

[14] 貝爾熱C，卜月華，張克民. 超圖—有限集的組合學(xué)[M]. 南京：東華大學(xué)出版社，2002:1-40.

[15] 胡楓，趙海興. 一種超網(wǎng)絡(luò)演化模型構(gòu)建及特性分析[J]. 中國科學(xué)，2013,43(1):16-22.

[16] Estrada E, Rodrigues V R. Subgraph centrality and clustering in complex hyper-networks[J]. Phsical A, 2006,364(1):581-594.

[17] 王志平，王眾托. 超網(wǎng)絡(luò)理論及其應(yīng)用[M]. 北京：北京科學(xué)出版社，2008:5-30.

[18] 漆玉虎，郭進利,等. 超網(wǎng)絡(luò)度參數(shù)研究[J]. 科技與管理，2013,15(1):34-38.