張 玲， 郭進(jìn)利

(上海理工大學(xué) 管理學(xué)院， 上海 200093)

地鐵是城市公共交通中最重要的一環(huán)，與其他交通方式相比有著快速便捷、載客量大、準(zhǔn)時(shí)等優(yōu)越性，成為可以解決大城市區(qū)域交通需求的關(guān)鍵方案[1]。隨著城市地鐵的發(fā)展，世界上的許多城市對(duì)地鐵系統(tǒng)的依賴日益增長。截至2019年6月，上海已有17路線、415座車站、累計(jì)705 km地鐵運(yùn)營線投入使用，運(yùn)營線網(wǎng)規(guī)模位居世界前列(含磁懸浮)。

城市地鐵網(wǎng)絡(luò)中的節(jié)點(diǎn)因其重要度不同，遭受攻擊后失效導(dǎo)致的網(wǎng)絡(luò)運(yùn)行效率的降低程度有所不同。已有研究表明，交通網(wǎng)絡(luò)的網(wǎng)絡(luò)抗毀性是由關(guān)鍵節(jié)點(diǎn)決定的[2]。因此識(shí)別地鐵網(wǎng)絡(luò)中對(duì)網(wǎng)絡(luò)運(yùn)行效率起著重要作用的關(guān)鍵節(jié)點(diǎn)，加強(qiáng)對(duì)關(guān)鍵節(jié)點(diǎn)的保護(hù)和管控，增強(qiáng)其抗風(fēng)險(xiǎn)能力，對(duì)于提高地鐵網(wǎng)絡(luò)的抗風(fēng)險(xiǎn)能力有重要意義。目前，已有許多學(xué)者對(duì)地鐵網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)價(jià)進(jìn)行了深入研究。在對(duì)波士頓地鐵網(wǎng)初步的研究中，Latora等[3]發(fā)現(xiàn)其具有小世界特性。Sienkiewicz等[4]研究了22個(gè)所在波蘭的城市軌道交通的網(wǎng)絡(luò)特性，從而分析得出波蘭軌道交通網(wǎng)絡(luò)呈現(xiàn)出小世界特性和分層組織的結(jié)論。Meng等[5]用Space-L和Space-P兩種模型建立深圳市地鐵網(wǎng)絡(luò)，構(gòu)建兩種模型的節(jié)點(diǎn)重要度評(píng)價(jià)模型，對(duì)兩種模型的抗毀性進(jìn)行對(duì)比，結(jié)果表明P模型比L模型具有更強(qiáng)的整體抗攻擊能力，更有利于網(wǎng)絡(luò)的彈性。郭曉玲等[6]運(yùn)用二次約束二次規(guī)劃模型，針對(duì)賦權(quán)網(wǎng)絡(luò)，綜合考慮節(jié)點(diǎn)移除后對(duì)網(wǎng)絡(luò)的整體結(jié)構(gòu)和功能的影響，給出了計(jì)算網(wǎng)絡(luò)連通性的新測(cè)度，即一步連續(xù)和兩步連續(xù)。韓紀(jì)彬等[7]采用了空間 L 方法系統(tǒng)分析其網(wǎng)絡(luò)特征參量，從最大連通子圖的相對(duì)大小、網(wǎng)絡(luò)全局效率和網(wǎng)絡(luò)局部效率等指標(biāo)分析網(wǎng)絡(luò)的可靠性。許海霖等[8]結(jié)合垂面距離和灰色關(guān)聯(lián)度綜合評(píng)價(jià)方案，用局部熵代替整體熵改進(jìn)TOPSIS算法，測(cè)算了地鐵網(wǎng)絡(luò)的節(jié)點(diǎn)重要度。王梓行等[9]創(chuàng)新性地重新定義了復(fù)雜網(wǎng)絡(luò)的冗余度，并重新定義的冗余度量化了網(wǎng)絡(luò)抗毀性，利用節(jié)點(diǎn)刪除法對(duì)節(jié)點(diǎn)重要度進(jìn)行了評(píng)估。

目前對(duì)地鐵網(wǎng)絡(luò)節(jié)點(diǎn)重要程度的評(píng)價(jià)主要依賴于刪除節(jié)點(diǎn)，考察節(jié)點(diǎn)失效對(duì)網(wǎng)絡(luò)整體效率的影響，且在評(píng)價(jià)節(jié)點(diǎn)時(shí)多采用重要度排序，但是在交通網(wǎng)絡(luò)中，對(duì)一個(gè)節(jié)點(diǎn)的評(píng)價(jià)大多為“關(guān)鍵”“重要”“一般”等表達(dá)，研究者難以確定關(guān)鍵節(jié)點(diǎn)的數(shù)量，選擇重要度排序前K個(gè)節(jié)點(diǎn)作為關(guān)鍵節(jié)點(diǎn)，導(dǎo)致關(guān)鍵節(jié)點(diǎn)判別不準(zhǔn)確。為準(zhǔn)確判斷軌道交通的關(guān)鍵節(jié)點(diǎn)，本文選取節(jié)點(diǎn)介數(shù)、接近中心性和特征向量中心性作為重要性評(píng)價(jià)指標(biāo)，研究一種基于特征加權(quán)的模糊聚算法的節(jié)點(diǎn)重要性評(píng)價(jià)方法，適用于地鐵網(wǎng)絡(luò)。

1 城市地鐵網(wǎng)絡(luò)構(gòu)建及指標(biāo)選取

1.1 城市地鐵網(wǎng)絡(luò)構(gòu)建

城市地鐵網(wǎng)絡(luò)建模是指將地鐵按照一定方法抽象為復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，從而方便對(duì)復(fù)雜網(wǎng)絡(luò)的各個(gè)統(tǒng)計(jì)指標(biāo)進(jìn)行分析和計(jì)算，為節(jié)點(diǎn)重要性分析提供模型基礎(chǔ)[10]。為直接反映站點(diǎn)之間的連接關(guān)系，采用Space-L方法來構(gòu)建城市地鐵網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：將站點(diǎn)抽象為節(jié)點(diǎn)，相鄰站點(diǎn)之間的軌道線路抽象為邊，構(gòu)建城市地鐵網(wǎng)絡(luò)的自然拓?fù)浣Y(jié)構(gòu)，如圖1所示。

圖1 Space-L法構(gòu)建網(wǎng)絡(luò)拓?fù)鋱D

1.2 指標(biāo)選取

從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)出發(fā)，綜合考慮了節(jié)點(diǎn)自身的性質(zhì)及其鄰居節(jié)點(diǎn)的性質(zhì)，最終選取了節(jié)點(diǎn)的介數(shù)、接近中心性和特征向量中心性作為評(píng)價(jià)節(jié)點(diǎn)重要性的依據(jù)。在描述網(wǎng)絡(luò)中某一個(gè)節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)介數(shù)描述了該節(jié)點(diǎn)進(jìn)行最短路徑傳輸信息的控制能力，接近中心性描述了網(wǎng)絡(luò)中所有節(jié)點(diǎn)到該節(jié)點(diǎn)的效率，特征向量中心性反映了與該節(jié)點(diǎn)相鄰節(jié)點(diǎn)的重要性。

1)介數(shù)：以經(jīng)過節(jié)點(diǎn)i的最短路徑數(shù)目來刻畫節(jié)點(diǎn)重要性的指標(biāo)稱為介數(shù)，它描述了節(jié)點(diǎn)i對(duì)于網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)之間沿著最短路徑傳輸信息的控制能力，即

(1)

式中：σst(i)表示節(jié)點(diǎn)s和節(jié)點(diǎn)t經(jīng)過節(jié)點(diǎn)i的最短路徑數(shù)；σst表示節(jié)點(diǎn)s和節(jié)點(diǎn)t之間的最短路徑數(shù)。在現(xiàn)實(shí)出行中，人們往往選擇最短路徑。因此，通過節(jié)點(diǎn)的最短路徑越多，節(jié)點(diǎn)越重要。

2)接近中心性：對(duì)于網(wǎng)絡(luò)中的任意節(jié)點(diǎn)i，可以計(jì)算該節(jié)點(diǎn)到網(wǎng)絡(luò)中所有節(jié)點(diǎn)的距離的平均值，平均距離越小，代表節(jié)點(diǎn)i更接近其他節(jié)點(diǎn)，將平均距離的倒數(shù)定義為節(jié)點(diǎn)的接近中心性，即

(2)

3)特征向量中心性：特征向量中心性的基本思想是一個(gè)節(jié)點(diǎn)的重要性既取決于其鄰居節(jié)點(diǎn)的數(shù)量，也取決于其鄰居節(jié)點(diǎn)的重要性。本文將特征向量中心性定義為節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的度值累加，即

(3)

式中：Vi為節(jié)點(diǎn)空間V的子空間，表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合；kj為節(jié)點(diǎn)j的度值。由于特征向量中心性的計(jì)算方法既考慮到了節(jié)點(diǎn)i鄰居節(jié)點(diǎn)的數(shù)量，即度值，又考慮到了鄰居節(jié)點(diǎn)的質(zhì)量，為了減少指標(biāo)之間的相關(guān)性，本文不再引入度值作為評(píng)價(jià)指標(biāo)。

2 基于k-means和熵權(quán)法加權(quán)的改進(jìn)FCM算法

不同于聚類算法的硬化分，嚴(yán)格地將個(gè)體歸劃到某一類去，模糊聚類將個(gè)體以一定的隸屬度歸于某一類，實(shí)現(xiàn)軟化分。在交通網(wǎng)絡(luò)中，對(duì)節(jié)點(diǎn)的描述多是“關(guān)鍵”“重要”等模糊性表達(dá)，研究者難以對(duì)其進(jìn)行明確的區(qū)分，因此模糊聚類更能客觀描述節(jié)點(diǎn)重要性程度。

基于上述結(jié)論，選擇采用模糊C-均值(FuzzyC-means)對(duì)節(jié)點(diǎn)進(jìn)行模糊聚類。FCM算法是利用目標(biāo)函數(shù)來反映聚類效果，利用約束條件解決非線性問題，目標(biāo)函數(shù)進(jìn)行不斷迭代，直到取得極小值。在模糊聚類的思想中，每一個(gè)樣本不是嚴(yán)格地歸為某一類，而是以一定的隸屬度屬于某一類。為了優(yōu)化FCM算法，從而進(jìn)一步提升FCM算法在地鐵網(wǎng)絡(luò)中的適用性，本文采用k-means和熵權(quán)法對(duì)FCM算法進(jìn)行改進(jìn)。

2.1 基于k-means的初始聚類中心確定方法

FCM算法對(duì)初始聚類中心十分敏感。初始聚類中心的選取直接影響算法迭代次數(shù)和計(jì)算時(shí)間，算法極容易因選擇了不恰當(dāng)?shù)某跏季垲愔行亩萑刖植孔顑?yōu)解[2]。

k-means作為動(dòng)態(tài)聚類法，具有原理簡明、熟練快速、聚類效果較優(yōu)等優(yōu)勢(shì)[12]，是一種最為廣泛使用的聚類方法，且可以得到與FCM相似的聚類中心，因此在對(duì)數(shù)據(jù)進(jìn)行模糊聚類之前，先使用k-means 聚類，確定初始聚類中心，不僅可以大大降低迭代次數(shù)，而且可以降低FCM陷入局部最優(yōu)解的可能性。

2.2 特征加權(quán)的FCM算法

為了優(yōu)化傳統(tǒng)FCM算法，除了通過k-means動(dòng)態(tài)聚類法確定初始聚類中心，減少迭代步驟之外，也重新定義了樣本與聚類中心之間的距離。

考慮到節(jié)點(diǎn)介數(shù)、接近中心性和特征向量中心性3個(gè)指標(biāo)在重要性評(píng)價(jià)上的權(quán)重有所不同，熵權(quán)法是一種客觀賦權(quán)方法，指標(biāo)的變異程度越小，其反映的信息量就越少，所對(duì)應(yīng)的權(quán)值應(yīng)該就越低，因此在傳統(tǒng)FCM算法基礎(chǔ)上使用熵權(quán)法引入權(quán)重。

特征加權(quán)后的FCM算法與傳統(tǒng)FCM算法的區(qū)別體現(xiàn)在樣本xj與聚類中心ci之間的距離變?yōu)?/p>

(4)

式中：wq為相應(yīng)指標(biāo)的權(quán)重；xjq表示第j個(gè)樣本的第q項(xiàng)指標(biāo)；ciq表示第i個(gè)聚類中心第q項(xiàng)指標(biāo)；m為模糊加權(quán)指數(shù)，取值范圍為1.5～2.5。因此，改進(jìn)FCM算法目標(biāo)函數(shù)和約束條件為

(5)

式中：c為別個(gè)數(shù)；uji表示第j個(gè)樣本屬于第i類的隸屬度，滿足0≤uji≤1且uj1+uj2+…+ujc=1。

改進(jìn)FCM算法的步驟如下：

步驟1l=0，通過k-means算法得到初始聚類中心C(0)，確定初始隸屬度矩陣U(0)，通過熵權(quán)法計(jì)算的指標(biāo)權(quán)重為W。

步驟2l=l+1，更新第l步中的聚類中心C(l)，即

(6)

步驟3修正隸屬度矩陣U(l)，計(jì)算目標(biāo)函數(shù)J(l)，即

(7)

(8)

步驟4對(duì)給定目標(biāo)函數(shù)終止容限ε或最大迭代步長Lmax，當(dāng)|J(l)-J(l-1)|<ε或l>Lmax時(shí)，終止迭代，否則l=l+1，轉(zhuǎn)步驟2。

2.3 算法檢驗(yàn)

為了判斷FCM算法的準(zhǔn)確性，采用誤差率交叉估計(jì)法進(jìn)行結(jié)果驗(yàn)證[12]。首先從N個(gè)數(shù)據(jù)中任意去掉一個(gè)，對(duì)其他數(shù)據(jù)進(jìn)行FCM聚類，然后用所得的聚類中心對(duì)刪除的樣本進(jìn)行判別。重復(fù)上述步驟，直到所有樣本均被檢驗(yàn)，與原FCM聚類結(jié)果進(jìn)行對(duì)比，求得誤判率。

3 實(shí)證分析

選取上海地鐵網(wǎng)絡(luò)作為研究對(duì)象，以截至2019年6月的地鐵站點(diǎn)及線路為例，驗(yàn)證評(píng)價(jià)方法的有效性。

3.1 方法應(yīng)用

將上海地鐵實(shí)際網(wǎng)絡(luò)抽象為以站點(diǎn)為節(jié)點(diǎn)、站點(diǎn)之間的軌道為連邊的Space-L網(wǎng)絡(luò)模型，由于地鐵相鄰兩站之間的出行時(shí)間多為2～3 min，故不考慮站點(diǎn)之間的距離，建立無向無權(quán)復(fù)雜網(wǎng)絡(luò)模型，如圖2所示。

圖2 上海地鐵Space-L模型

由Gephi軟件的結(jié)果可知，節(jié)點(diǎn)度最大的點(diǎn)為世紀(jì)大道，度值為8，上海地鐵網(wǎng)絡(luò)平均度為2.329，大多數(shù)站點(diǎn)的度值為2，即與同一條線路上的相鄰兩站構(gòu)成鄰居關(guān)系，網(wǎng)絡(luò)直徑為44。平均路徑長度為15.893，網(wǎng)絡(luò)平均聚類系數(shù)為0.026，上海地鐵Space-L網(wǎng)絡(luò)不構(gòu)成小世界網(wǎng)絡(luò)。

通過MATLAB計(jì)算出節(jié)點(diǎn)介數(shù)、接近中心性和特征向量中心性3個(gè)指標(biāo)，并對(duì)所有的數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理。

通過熵權(quán)法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)重要性指標(biāo)進(jìn)行加權(quán)，得到3個(gè)指標(biāo)(節(jié)點(diǎn)介數(shù)、接近中心性、特征向量中心性)的權(quán)重矩陣為W={0.425 7 0.165 8 0.408 5}。

3.2 改進(jìn)FCM算法的應(yīng)用結(jié)果

將節(jié)點(diǎn)重要性分為5個(gè)級(jí)別，分別為“關(guān)鍵”“次關(guān)鍵”“重要”“較為重要”“一般”。在應(yīng)用算法的過程中，取聚類類別數(shù)c=5，終止容限ε=0.001，模糊聚類指數(shù)m=2，最大迭代次數(shù)Lmax=1 000，通過改進(jìn)FCM算法得出的聚類結(jié)果如圖3所示。

圖3 改進(jìn)FCM聚類結(jié)果可視化

由于節(jié)點(diǎn)介數(shù)、接近中心性和特征向量中心性均為正向指標(biāo)，即指標(biāo)數(shù)值越大，節(jié)點(diǎn)越重要，因此將最終聚類中心的3項(xiàng)指標(biāo)加權(quán)和進(jìn)行降序排列，將類別依次記為“關(guān)鍵”“次關(guān)鍵”“重要”“較為重要”“一般”，改進(jìn)FCM算法結(jié)果統(tǒng)計(jì)如圖4所示。

圖4 上海地鐵站點(diǎn)重要性匯總

由圖4可知，用改進(jìn)FCM算法得出了上海地鐵的24個(gè)關(guān)鍵節(jié)點(diǎn)、52個(gè)次關(guān)鍵節(jié)點(diǎn)、62個(gè)重要節(jié)點(diǎn)、167個(gè)較為重要節(jié)點(diǎn)和41個(gè)一般節(jié)點(diǎn)。對(duì)比站點(diǎn)信息得出關(guān)鍵節(jié)點(diǎn)分別為上海體育館、徐家匯、常熟路、陜西南路、人民廣場、漢中路、江蘇路、靜安寺、南京西路、世紀(jì)大道、宜山路、金沙江路、曹楊路、大木橋路、東安路、肇嘉浜路、成山路、陸家浜路、曲阜路、嘉善路、馬當(dāng)路、交通大學(xué)、新天地、隆德路。由站點(diǎn)信息可知，關(guān)鍵節(jié)點(diǎn)均為換乘站點(diǎn)，且地理位置集中于市區(qū)中心區(qū)域。

表1所示為改進(jìn)FCM算法各個(gè)聚類中心在3個(gè)評(píng)價(jià)指標(biāo)上的得分。從表1可知，關(guān)鍵節(jié)點(diǎn)在介數(shù)、接近中心性和特征向量中心性上的評(píng)分均為最高，其中特征向量中心性的得分為2.705 6，說明相鄰節(jié)點(diǎn)的重要性對(duì)節(jié)點(diǎn)自身的重要性有一定影響。次關(guān)鍵節(jié)點(diǎn)的聚類中心在3個(gè)評(píng)價(jià)指標(biāo)上的得分僅次于關(guān)鍵節(jié)點(diǎn)，且依然是在特征向量中心性這一指標(biāo)上得分最高。重要節(jié)點(diǎn)在接近中心性上的得分較高，說明此類節(jié)點(diǎn)與網(wǎng)絡(luò)中節(jié)點(diǎn)的距離較小。圖4 表明，較為重要站點(diǎn)個(gè)數(shù)為167個(gè)，這些站點(diǎn)大多居于線路的中間部分，且不為換乘站，經(jīng)過此類站點(diǎn)的最短路線較多。

表1 聚類中心

而在重要性為一般的節(jié)點(diǎn)中，大多數(shù)節(jié)點(diǎn)為地鐵線路的首末站點(diǎn)或與首末站點(diǎn)相鄰的站點(diǎn)。在地鐵網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，這些站點(diǎn)一般不與其他站點(diǎn)相鄰，度值較??；通過它們的最短路線較少，因此介數(shù)較??；而其他站點(diǎn)到它們的距離較大，因此接近中心性較??；由于在模型中考慮到了一個(gè)節(jié)點(diǎn)的重要性也取決于其鄰居節(jié)點(diǎn)的重要性，因此與首末站點(diǎn)相鄰的站點(diǎn)在評(píng)價(jià)體系中重要性也相對(duì)較小。

3.3 改進(jìn)FCM算法評(píng)價(jià)

3.3.1 目標(biāo)函數(shù)及迭代次數(shù)

與傳統(tǒng)FCM算法相比，由于改進(jìn)FCM算法在迭代之前通過k-means確定了初始聚類中心，故初次計(jì)算的目標(biāo)函數(shù)值和迭代次數(shù)均遠(yuǎn)低于傳統(tǒng)FCM算法。傳統(tǒng)FCM算法迭代次數(shù)為62次，改進(jìn)后迭代了26次，迭代次數(shù)降低了58.06%，縮短了運(yùn)行時(shí)間。傳統(tǒng)FCM的目標(biāo)函數(shù)值為5.554 9，改進(jìn)FCM算法最終得出的目標(biāo)函數(shù)值為5.259 1，目標(biāo)函數(shù)值降低了5.33%，如圖5所示。

圖5 目標(biāo)函數(shù)和迭代次數(shù)對(duì)比

3.3.2 誤判率評(píng)價(jià)

采用誤判率交叉估計(jì)法，分別驗(yàn)證傳統(tǒng)FCM算法與改進(jìn)FCM算法的誤判率。觀察表2可知，使用傳統(tǒng)FCM算法進(jìn)行模糊聚類，在“重要”“較為重要”“一般”3種類別中出現(xiàn)分別出現(xiàn)了6、9、4個(gè)誤判，整體誤判率為5.49%。而使用k-means和熵權(quán)法對(duì)FCM算法進(jìn)行改進(jìn)后，誤判率為0，大大提高了FCM算法的準(zhǔn)確性。

表2 改進(jìn)FCM算法與傳統(tǒng)FCM算法誤判率對(duì)比

4 結(jié)語

研究了城市地鐵網(wǎng)絡(luò)節(jié)點(diǎn)重要性：選取節(jié)點(diǎn)介數(shù)、接近中心性和特征向量中心性3個(gè)指標(biāo)，通過基于k-means和熵權(quán)法改進(jìn)的FCM算法進(jìn)行模糊聚類分析，并由模糊聚類中心3項(xiàng)指標(biāo)的加權(quán)和將地鐵網(wǎng)絡(luò)節(jié)點(diǎn)分類為“關(guān)鍵”“次關(guān)鍵”“重要”“較為重要”“一般”5個(gè)重量級(jí)類別。以上海地鐵網(wǎng)絡(luò)為例，通過模糊聚類得出了24個(gè)關(guān)鍵節(jié)點(diǎn)，均在4號(hào)線環(huán)線及以內(nèi)區(qū)域，因此在以后的站點(diǎn)維護(hù)中，要加強(qiáng)對(duì)城市中心區(qū)域地鐵站的維護(hù)，增強(qiáng)其抗干擾能力。對(duì)比改進(jìn)FCM算法和傳統(tǒng)FCM算法的聚類效果，發(fā)現(xiàn)改進(jìn)后的FCM算法降低了目標(biāo)函數(shù)值、減少了迭代次數(shù)、降低了誤判率，更能客觀刻畫地鐵網(wǎng)絡(luò)的節(jié)點(diǎn)重要性，適用于城市地鐵網(wǎng)絡(luò)。

提出了一種改進(jìn)的FCM模型，但仍存在許多方面期待進(jìn)一步研究，例如本文僅從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上綜合考慮了節(jié)點(diǎn)本身及其相鄰節(jié)點(diǎn)的重要性指標(biāo)，但并未考慮實(shí)際交通需求量，以后的研究可以將實(shí)際客流量考慮進(jìn)去，建立帶有權(quán)重的網(wǎng)絡(luò)模型，計(jì)算各個(gè)節(jié)點(diǎn)的強(qiáng)度作為指標(biāo)之一。