高 勃，秦 勇,肖雪梅，祝凌曦

(北京交通大學(xué) a.信息中心；b.交通運(yùn)輸學(xué)院，北京100044)

基于K-means的北京地鐵路網(wǎng)重要度聚類分析

高 勃*a,b，秦 勇b,肖雪梅b，祝凌曦b

(北京交通大學(xué) a.信息中心；b.交通運(yùn)輸學(xué)院，北京100044)

以圖論為基礎(chǔ)，以北京地鐵為研究對(duì)象，結(jié)合地鐵運(yùn)營(yíng)客流時(shí)空分布的特點(diǎn)，構(gòu)建北京地鐵有向加權(quán)路網(wǎng)模型；采用K-means聚類分析方法，根據(jù)地鐵路網(wǎng)中車站和區(qū)間的兩個(gè)基本的物理拓?fù)鋵傩裕ǘ取⒔閿?shù)），以及客運(yùn)量對(duì)其進(jìn)行分類，確定關(guān)鍵車站和區(qū)間.其中，度反映的是節(jié)點(diǎn)的局部聚集能力，介數(shù)反映的是節(jié)點(diǎn)和邊對(duì)全局的影響能力，而客運(yùn)量則反映了不同時(shí)間段節(jié)點(diǎn)和邊在運(yùn)輸中的重要性.實(shí)證分析表明，該方法可以從系統(tǒng)網(wǎng)絡(luò)的角度動(dòng)態(tài)辨識(shí)系統(tǒng)中的關(guān)鍵車站和區(qū)間.

城市交通；重要度；K-means；地鐵路網(wǎng)；異質(zhì)性

1 引 言

地鐵因其運(yùn)量大、速度快、安全可靠等特點(diǎn)成為緩解城市交通需求矛盾的重要工具.隨著地鐵新線的不斷規(guī)劃、建設(shè)和投入運(yùn)營(yíng)，我國(guó)部分特大城市的地鐵線路已進(jìn)入網(wǎng)絡(luò)化運(yùn)營(yíng)階段.在地鐵網(wǎng)絡(luò)不斷擴(kuò)大的同時(shí)，路網(wǎng)客流量與日俱增，站與站之間關(guān)聯(lián)性增強(qiáng)，局部問(wèn)題對(duì)整個(gè)路網(wǎng)的波及效應(yīng)和聯(lián)動(dòng)性更加突出.Sybil對(duì)世界上33個(gè)國(guó)家的地鐵路網(wǎng)研究證明，地鐵路網(wǎng)屬于無(wú)標(biāo)度網(wǎng)絡(luò)[1].在蓄意攻擊條件下，無(wú)標(biāo)度網(wǎng)絡(luò)非常脆弱.1%的“核心節(jié)點(diǎn)”一旦受到攻擊失效，網(wǎng)絡(luò)性能將下降50%左右[2].因此，研究地鐵路網(wǎng)運(yùn)營(yíng)中的“核心節(jié)點(diǎn)”具有重要意義.

網(wǎng)絡(luò)節(jié)點(diǎn)（邊）重要度研究最早來(lái)源于圖論中MVNP（最關(guān)鍵節(jié)點(diǎn)問(wèn)題）和MVEP（最關(guān)鍵邊問(wèn)題）的研究.評(píng)估方法主要包括度、接近度、中心性、刪除法和綜合評(píng)估法等，目前已經(jīng)在通訊網(wǎng)絡(luò)、公路網(wǎng)等多個(gè)領(lǐng)域得到了應(yīng)用[3,4].對(duì)于地鐵路網(wǎng)而言，在對(duì)其關(guān)鍵車站和關(guān)鍵區(qū)間進(jìn)行評(píng)估時(shí)，一方面要從物理拓?fù)浣Y(jié)構(gòu)的角度考慮車站、區(qū)間在路網(wǎng)中的作用和影響力；另一方面要考慮車站、區(qū)間在運(yùn)營(yíng)中所承載的客運(yùn)量對(duì)路網(wǎng)的影響.

本文以北京地鐵為研究對(duì)象，采用聚類分析方法，根據(jù)地鐵路網(wǎng)中車站和區(qū)間的兩個(gè)基本物理拓?fù)鋵傩裕ǘ?、介?shù)），以及客運(yùn)量對(duì)其進(jìn)行分類，確定關(guān)鍵車站和區(qū)間.

2 北京地鐵加權(quán)路網(wǎng)模型

2.1 模型構(gòu)建

隨著北京地鐵路網(wǎng)規(guī)模的不斷擴(kuò)大，客流量持續(xù)增長(zhǎng)，部分車站和區(qū)間的承載能力已達(dá)到飽和，路網(wǎng)運(yùn)營(yíng)風(fēng)險(xiǎn)增大.為確保路網(wǎng)安全、高效運(yùn)營(yíng)，需要對(duì)地鐵路網(wǎng)中的關(guān)鍵車站和區(qū)間進(jìn)行辨

2.2 節(jié)點(diǎn)屬性

節(jié)點(diǎn)度是圖論中最基本的測(cè)度指標(biāo)之一，能夠衡量節(jié)點(diǎn)在路網(wǎng)中的局部凝聚能力.節(jié)點(diǎn)度di表示G中與節(jié)點(diǎn)vi相關(guān)聯(lián)的邊的個(gè)數(shù).節(jié)點(diǎn)vi連接的識(shí)、分析和管理監(jiān)控，以便針對(duì)性地制定應(yīng)急預(yù)案.

圖1 2013年北京地鐵路網(wǎng)圖Fig.1 Beijing urban rail transit network in 2013

本文以2013年4月北京地鐵路網(wǎng)（如圖1所示，共15條線路、225個(gè)車站）為例，對(duì)其關(guān)鍵車站和區(qū)間進(jìn)行聚類分析.基于網(wǎng)絡(luò)理論和方法，以車站為節(jié)點(diǎn)，相鄰車站的區(qū)間為邊，區(qū)間斷面客流量為邊權(quán)重構(gòu)建地鐵加權(quán)路網(wǎng)模型.

地鐵加權(quán)路網(wǎng)模型由集合G=(V，E)表示，其中：

（1）V代表節(jié)點(diǎn)（車站）的集合，V={vi}，i=1,2, ···，N，N表示路網(wǎng)中車站的數(shù)目；vi代表G中第i個(gè)節(jié)點(diǎn)，是拓?fù)浣Y(jié)構(gòu)和功能屬性的集合，vi={di,bi, ci(Δt)}，其中：di表示第i個(gè)節(jié)點(diǎn)的度，bi表示第i個(gè)節(jié)點(diǎn)的介數(shù)，ci(Δt)表示單位時(shí)間內(nèi)第i個(gè)節(jié)點(diǎn)的客運(yùn)量.

（2）E代表有向邊（區(qū)間）的集合，E={eij}，i, j=1,2,···，N，i≠j，N表示路網(wǎng)中車站的數(shù)目；邊eij是由相鄰節(jié)點(diǎn)vi和vj構(gòu)成的有序?qū)?vi,vj)、結(jié)構(gòu)屬性和權(quán)重構(gòu)成的集合，eij={(vi,vj),bij,ωij(Δ t)}，其中：bij表示邊eij的介數(shù)，ωij(Δt)表示單位時(shí)間內(nèi)邊的eij權(quán)重.邊越多，節(jié)點(diǎn)vi度越大，其局部拓?fù)渲匾仍酱?

對(duì)圖1建模，得到全部225個(gè)車站節(jié)點(diǎn)度分布.其中，約13%的車站節(jié)點(diǎn)度值較大，西直門車站的節(jié)點(diǎn)度值最大（d=10），東單、呼家樓、崇文門、國(guó)貿(mào)等29個(gè)車站節(jié)點(diǎn)度值其次（d=8），均為換乘車站.車站連接的線路越多，車站節(jié)點(diǎn)度越大，節(jié)點(diǎn)度值較大的車站，在地鐵網(wǎng)絡(luò)中的重要度會(huì)較高.

乘客在選擇公共交通出行時(shí)，總是期望乘坐最少的區(qū)間到達(dá)目的地.定義地鐵加權(quán)路網(wǎng)模型中區(qū)間的距離為1，地鐵加權(quán)路網(wǎng)模型中任意兩點(diǎn)間的最短距離即為節(jié)點(diǎn)vs和節(jié)點(diǎn)vt間的最短路徑中的邊的個(gè)數(shù).

節(jié)點(diǎn)介數(shù)(Betweenness Centrality)用來(lái)衡量節(jié)點(diǎn)在路網(wǎng)中的全局拓?fù)浣Y(jié)構(gòu)重要程度，反映了該節(jié)點(diǎn)在整個(gè)路網(wǎng)中的地位和影響力.

節(jié)點(diǎn)介數(shù)bi表示路網(wǎng)所有最短路徑中經(jīng)過(guò)節(jié)點(diǎn)vi的比例，即

式中 bi——節(jié)點(diǎn)vi的介數(shù)；

σst——節(jié)點(diǎn)s到t的最短路徑數(shù)量；

σst(vi)——節(jié)點(diǎn)s到t經(jīng)過(guò)節(jié)點(diǎn)vi的最短路徑的數(shù)量.

經(jīng)計(jì)算，節(jié)點(diǎn)介數(shù)排名前15的車站如表1所示，其中西直門車站依然排在首位，部分換乘站如軍事博物館、建國(guó)門、宣武門、崇文門、知春路、白石橋南等在節(jié)點(diǎn)度、節(jié)點(diǎn)介數(shù)的指標(biāo)上都排名居前；車公莊、朝陽(yáng)門、大鐘寺等非換乘站雖然在節(jié)點(diǎn)度的排名居后，但從節(jié)點(diǎn)介數(shù)分析，其重要程度甚至超過(guò)很多換乘車站；這表明車公莊、朝陽(yáng)門等非換乘車站在路網(wǎng)中同樣起到重要作用.

表1 不同車站節(jié)點(diǎn)介數(shù)Table1 Stations ranking by node betweenness

節(jié)點(diǎn)客運(yùn)量ci(Δt)，單位時(shí)間內(nèi)節(jié)點(diǎn)進(jìn)站客流量、出站客流量和換乘客流量的總和：

式中 ci(Δt)——節(jié)點(diǎn)客運(yùn)量，單位：人次/小時(shí)；

cin(Δt)——單位時(shí)間內(nèi)進(jìn)站客流量；

cout(Δt)——單位時(shí)間內(nèi)出站客流量；

ctr(Δt)——單位時(shí)間內(nèi)換乘客流量.

表2列出了在早、晚高峰和平峰三個(gè)時(shí)間，段客運(yùn)量排名前6的車站.

表2 不同時(shí)間車站節(jié)點(diǎn)客運(yùn)量Table2 The stations ranking by volume

北京地鐵客流具有典型的“潮汐”特點(diǎn)，早晚高峰期間客運(yùn)量遠(yuǎn)大于其它平峰時(shí)段.拓?fù)鋵傩韵嗤瑮l件下，客運(yùn)量越大，運(yùn)輸?shù)匚辉街匾?不同時(shí)段，由于客流的走向和需求不同，車站客運(yùn)量排序是不相同的.西直門、國(guó)貿(mào)、建國(guó)門、東直門等換乘站，在全天都是節(jié)點(diǎn)客運(yùn)量較大的車站.

2.3 邊屬性

邊介數(shù)bij反映了該邊在整個(gè)路網(wǎng)中的地位和影響力，表示路網(wǎng)所有的最短路徑中經(jīng)過(guò)邊eij的比例，即

式中 bij——邊eij的介數(shù)；

σst(eij)——節(jié)點(diǎn)s到t經(jīng)過(guò)邊eij的最短路徑的數(shù)量.

邊介數(shù)排名前15的區(qū)間如表3所示.

表3 不同車站區(qū)間邊介數(shù)Table3 Intervals ranking by edge betweenness

邊介數(shù)排名靠前的區(qū)間，都至少連接了一個(gè)換乘站.這說(shuō)明，與換乘站相連的區(qū)間，在路網(wǎng)結(jié)構(gòu)中具有較高的地位和影響力.

邊權(quán)重ωij(Δt)表示單位時(shí)間內(nèi)，單向通過(guò)運(yùn)營(yíng)線路特定方向的區(qū)間斷面客流量，單位：人次/小時(shí).單位時(shí)間內(nèi)通過(guò)區(qū)間的斷面客流量越大，區(qū)間權(quán)重越大，在路網(wǎng)運(yùn)輸中的地位越重要.

地鐵的一個(gè)典型特點(diǎn)就是運(yùn)輸?shù)姆较蛐?，同一時(shí)間同一區(qū)間上、下行區(qū)間斷面客流量是不相同的，即ωij(Δt)≠ωji(Δt).圖2為北京地鐵某區(qū)間2013年3月某天不同時(shí)間段上下行的客運(yùn)量，早晚高峰期間客運(yùn)量大于平峰時(shí)段.雖然二者拓?fù)浣Y(jié)構(gòu)相同，但在客流運(yùn)輸中的重要程度是不同的，且隨著時(shí)間的不同而變化.

圖2 某一區(qū)間上、下行全天不同時(shí)間段客運(yùn)量Fig.2 The passenger volume of interval at different times

通過(guò)分析可知，考慮到客運(yùn)量后，結(jié)構(gòu)拓?fù)鋵傩韵嗤墓?jié)點(diǎn)和邊，由于其承載的客運(yùn)量不同，其功能屬性及在路網(wǎng)運(yùn)營(yíng)中的地位是不同的.

3 車站和區(qū)間重要度聚類分析

3.1 關(guān)鍵節(jié)點(diǎn)（邊）重要度定義

關(guān)鍵節(jié)點(diǎn)（邊）是指對(duì)維持地鐵加權(quán)路網(wǎng)正常運(yùn)輸起到重要作用的車站（區(qū)間）.路網(wǎng)中關(guān)鍵節(jié)點(diǎn)和邊一旦失效，會(huì)導(dǎo)致路網(wǎng)連通性、路網(wǎng)運(yùn)能大幅度下降；在極端情況下，部分關(guān)鍵節(jié)點(diǎn)和邊失效，會(huì)導(dǎo)致路網(wǎng)結(jié)構(gòu)和功能的整體失效.

K-means聚類算法，具有簡(jiǎn)單、高效等優(yōu)點(diǎn)[5-7].本文應(yīng)用K-means聚類算法，根據(jù)表征地鐵路網(wǎng)中車站和區(qū)間的局部拓?fù)渲匾灾笜?biāo)（度）、全局拓?fù)渲匾灾笜?biāo)（介數(shù)），以及運(yùn)輸功能（客運(yùn)量）進(jìn)行聚類分析，確定關(guān)鍵節(jié)點(diǎn)和邊.

3.2 基于K-means的重要度聚類分析算法

路網(wǎng)模型中各節(jié)點(diǎn)（或者邊）構(gòu)成樣本集Y= {y1,y2,···,yi,···,yn}，其中，n是節(jié)點(diǎn)（或者邊）的數(shù)量；每個(gè)樣本yi={yi1,yi2,···,yid}，yid表示第i個(gè)節(jié)點(diǎn)（或邊）的第d個(gè)屬性值.

基于K-means的車站和區(qū)間重要度聚類分析基本步驟：

Step1確定分類數(shù)K.從整體樣本Y中，隨機(jī)選取K個(gè)對(duì)象作為初始的簇中心mj(I)(j=1,2,···, K)，令I(lǐng)=1.

Step2采用歐式距離作為相似度的衡量標(biāo)準(zhǔn)，計(jì)算Y中每個(gè)樣本yi到K個(gè)簇中心的歐式距離d(yi,mj(I))，找到每個(gè)樣本yi的最小d(yi,mj(I))，將yi歸入到與mj(I)相同的簇中.

Step3遍歷完所有對(duì)象之后，重新計(jì)算mj(I)的值，以簇中所有點(diǎn)均值作為新的簇中心.

Step4計(jì)算誤差平方和E(I).

nj——第 j個(gè)簇中樣本的個(gè)數(shù).

若|E(I)-E(I-1)|<ξ則算法結(jié)束；否則I=I+1，返回Step2.

3.3 重要度分布異質(zhì)性

研究表明，網(wǎng)絡(luò)的異質(zhì)性和脆弱性相關(guān)[7].信息熵用來(lái)衡量地鐵加權(quán)路網(wǎng)模型的節(jié)點(diǎn)（邊）重要度分布的異質(zhì)性.地鐵加權(quán)路網(wǎng)中節(jié)點(diǎn)和邊的重要度分布越不均勻，熵值越大，重要度分布的異質(zhì)性越大，整個(gè)路網(wǎng)的風(fēng)險(xiǎn)越高.

通過(guò)可靠性理論中的分組經(jīng)驗(yàn)公式[8]確定節(jié)點(diǎn)和邊重要度的分類數(shù)K：

式中 n——路網(wǎng)中節(jié)點(diǎn)或者邊的總數(shù).

重要度分布熵H代表網(wǎng)絡(luò)中節(jié)點(diǎn)（邊）重要度分布的不均勻程度.

式中 pj——路網(wǎng)中重要度等級(jí)為j節(jié)點(diǎn)（或者邊）的比例；

num(j)——重要度等級(jí)為j的節(jié)點(diǎn)（或者邊）的數(shù)量.

4 聚類分析

選取北京地鐵路網(wǎng)3月某一工作日三個(gè)時(shí)間段，分別是早高峰（8:00-9:00）、平峰（11:00-12:00）和晚高峰（18:00-19:00），對(duì)于車站以節(jié)點(diǎn)度、節(jié)點(diǎn)介數(shù)和節(jié)點(diǎn)客運(yùn)量為變量，對(duì)于區(qū)間以區(qū)間介數(shù)、區(qū)間客運(yùn)量為變量，進(jìn)行重要度聚類分析.

為觀察重要度的分布情況，根據(jù)分組經(jīng)驗(yàn)公式K=1+3.3lgn，同時(shí)考慮到分組數(shù)一般是5或者10的倍數(shù)，將車站和區(qū)間分為10組.通過(guò)SPSS軟件，分類數(shù)K=10，最大迭代數(shù)NC=10，收斂標(biāo)準(zhǔn)取0，聚類結(jié)果如表4和表5所示.

表4 不同時(shí)間車站聚類結(jié)果分析Table4 Clustering center at different times

表5 不同時(shí)間區(qū)間聚類結(jié)果分析Table5 Clustering center at different times

由表4、表5可知，由于不同時(shí)間段各車站和區(qū)間客運(yùn)量的不同，不同時(shí)間段聚類中心各指標(biāo)分類標(biāo)準(zhǔn)（均值）是不一樣的.從而證明，結(jié)合物理拓?fù)浜瓦\(yùn)輸功能屬性，采用K-means方法可以實(shí)現(xiàn)地鐵路網(wǎng)車站和區(qū)間重要度的動(dòng)態(tài)聚類分析.同一聚類中的車站和區(qū)間在物理拓?fù)鋵傩院瓦\(yùn)輸功能屬性上具有較高的相似度，物理拓?fù)浜涂瓦\(yùn)量值均較大的聚類中的車站和區(qū)間對(duì)路網(wǎng)的正常運(yùn)營(yíng)起到關(guān)鍵作用.

以早高峰為例，車站K1聚類中的西直門站，以及區(qū)間K7聚類中的菜市口→陶然亭方向，無(wú)論其拓?fù)浣Y(jié)構(gòu)屬性或者客運(yùn)量都較大，其在路網(wǎng)運(yùn)營(yíng)中的地位非常重要.而車站K4聚類中的國(guó)貿(mào)站和K7聚類中的朝陽(yáng)門、雍和宮和崇文門等站，以及區(qū)間K1聚類中的西直門→動(dòng)物園方向和K5聚類中的北京西站→軍事博物館方向，雖然它們的拓?fù)浣Y(jié)構(gòu)屬性相近，但是由于國(guó)貿(mào)站和西直門→動(dòng)物園方向客運(yùn)量較大，它們的重要性并不屬于同一類，從而證明在對(duì)車站和區(qū)間重要度進(jìn)行聚類分析時(shí)需要考慮客運(yùn)量.通過(guò)對(duì)不同時(shí)間段路網(wǎng)中車站和區(qū)間重要度聚類發(fā)現(xiàn)，隨著時(shí)間變化，客運(yùn)量不斷變化，路網(wǎng)中車站和區(qū)間的重要度異質(zhì)性也是隨之變化.如表4和表5所示，在早晚高峰期間重要度的分布異質(zhì)性大于平峰時(shí)間，風(fēng)險(xiǎn)增加.

圖3給出了，在不同時(shí)間段，度、介數(shù)和客運(yùn)量都較大的聚類中的車站和區(qū)間名稱，這些聚類中的車站和區(qū)間在路網(wǎng)拓?fù)浣Y(jié)構(gòu)，以及路網(wǎng)運(yùn)輸功能方面都發(fā)揮著重要作用.

圖3 不同時(shí)段關(guān)鍵車站和區(qū)間Fig.3 The key stations and intervals at different times

由圖3可知，在不同時(shí)間段，基于物理拓?fù)浜涂瓦\(yùn)量屬性的各聚類中的車站和區(qū)間是動(dòng)態(tài)變化的.例如：國(guó)貿(mào)站位于北京的中央商務(wù)區(qū)，西直門站處于2號(hào)線、4號(hào)線和13號(hào)線的交匯點(diǎn)，不論早晚高峰還是平峰時(shí)間，其在路網(wǎng)運(yùn)營(yíng)中的地位都極其重要；西單站位于北京的重要商業(yè)圈，平峰和晚高峰期間，在路網(wǎng)運(yùn)營(yíng)中的地位非常重要；西二旗站作為13號(hào)線和昌平線的換乘站，同時(shí)周邊聚集了聯(lián)想、百度、軟件園等大型公司企業(yè)以及一系列居民住宅區(qū)，在早晚高峰期間運(yùn)營(yíng)地位同樣很重要；區(qū)間西單至東單方向，由于其途徑天安門西和王府井等旅游地點(diǎn)，在平峰時(shí)間段地位很重要.因此，在不同時(shí)間，運(yùn)營(yíng)管理部門應(yīng)針對(duì)不同重點(diǎn)車站加強(qiáng)管理和監(jiān)控，從而確保路網(wǎng)正常運(yùn)營(yíng).

5 研究結(jié)論

本文在構(gòu)建北京地鐵加權(quán)路網(wǎng)模型的基礎(chǔ)上，根據(jù)地鐵路網(wǎng)中車站和區(qū)間的物理拓?fù)鋵傩裕ǘ?、介?shù)）以及運(yùn)輸功能（客流量），應(yīng)用基于K-means的節(jié)點(diǎn)（邊）重要度動(dòng)態(tài)聚類方法分析地鐵網(wǎng)絡(luò)，并從信息熵的角度分析其異質(zhì)性.

通過(guò)對(duì)北京地鐵路網(wǎng)的實(shí)證分析，驗(yàn)證了該方法的可行性和合理性.分析發(fā)現(xiàn)，在不同時(shí)間段，北京地鐵車站和區(qū)間在路網(wǎng)中的重要度是動(dòng)態(tài)變化的，路網(wǎng)中車站（區(qū)間）的重要度異質(zhì)性也是隨時(shí)間而改變的.北京地鐵路網(wǎng)運(yùn)營(yíng)管理部門，在路網(wǎng)異質(zhì)性較大的時(shí)間段內(nèi)，對(duì)處于高聚類等級(jí)中的車站和區(qū)間應(yīng)進(jìn)行重點(diǎn)監(jiān)控、管理，保障其正常運(yùn)行.這對(duì)于確保路網(wǎng)結(jié)構(gòu)安全、可靠，以及路網(wǎng)整體性能發(fā)揮具有重要意義.

[1]Sybil D,Christopher K.The complexity and robustness of metro networks[J].Physica A,2010，389:3678～3691.

[2]王延慶.基于接連失效的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2008（03）:59-61 1[WANG Y Q.Node importance evaluation of complex network based on successive failure[J].Net Security Technolo?gies and Application,2008(3):59-61.]

[3]陳靜,孫林夫.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要度評(píng)估[J].西南交通大學(xué)學(xué)報(bào)，2009，44（03）:426-429.[CHEN J,SUN L F.Evaluation of node importance in complex networks [J].Journal of Southwest Jiaotong University,2009,44 (3):426-429.]

[4]Zhao K,Kumar A,Yen J.Achieving high robustness in supply distribution networks by rewiring[J].IEEE Transactions on Engineering Management,2011,58(2)：347-362.

[5]莫春玲.復(fù)雜網(wǎng)絡(luò)中聚類方法及社團(tuán)結(jié)構(gòu)的研究[D].武漢：武漢理工大學(xué),2007.[MO C L.The Research of clustering methods and community structure in complex networks[D].Wuhan University of Technology,2007.]

[6]黃韜,劉勝輝,譚艷娜.基于K-means聚類算法的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2011,21(7):54-57,62.[HUANG T,LIU S H,TAN Y N.Research of clustering algorithm based on K-means[J].Computer Technology and Devel?opment,2011,21(7):54-57,62.]

[7]Zhao K,Kumar A,Harrison TP,et al.Analyzing the resil?ience of complex supply network topologies against ran?dom and targeted disruptions[J].IEEE Systems Journal, 2011,5(1)：28-39.

[8]趙宇,楊軍,馬小兵.可靠性數(shù)據(jù)分析教程[M].北京：北京航空航天大學(xué)出版社,2009.[ZHAO Y,YANG J, MA X B.Reliability data analysis[M].Beijing Universi?ty of Aeronautics and Astronautics Press,2009.]

K-means Clustering Analysis of Key Nodes and Edges in Beijing Subway Network

GAO Boa,b,QIN Yongb,XIAO Xue-meib,ZHU Ling-xib
(a.Information Center；b.School of Traffic and Transportation,Beijing Jiaotong University,Beijing 100044,China)

This paper modeled a subway system as a directed and weighted network with consideration of the temporal and spatial distribution of passengers in the subway system.Based on the K-means clustering, stations(nodes)and intervals(edges)in a subway network were grouped by three metrics:two basic topological properties(degree and betweenness),and their roles in transporting people(passenger volume).Degree reflects the nodes’local accumulation ability;betweenness reflects a node or edge’s the impact on the global network topology,and passenger volume reflects a node or edge’s importance in transport people at different times.Taking the Beijing Subway network as a case study,the paper tested the effectiveness of the proposed approach.The results suggested that the method could identify key nodes and edges and provide dynamic decision support for subway network operators.

urban traffic;key edges and nodes;K-means;subway network;heterogeneity

1009-6744（2014）03-0207-07

U121

A

2013-11-05

2014-05-02錄用日期：2014-05-07

高勃（1980-），男，山東泰安人，工程師，博士生.*通訊作者：gaobo@bjtu.edu.cn