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

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

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

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

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

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

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

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

1 引 言

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

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

本文以北京地鐵為研究對象，采用聚類分析方法，根據(jù)地鐵路網(wǎng)中車站和區(qū)間的兩個基本物理拓撲屬性（度、介數(shù)），以及客運量對其進行分類，確定關鍵車站和區(qū)間.

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

2.1 模型構建

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

2.2 節(jié)點屬性

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

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

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

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

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

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

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

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

節(jié)點介數(shù)(Betweenness Centrality)用來衡量節(jié)點在路網(wǎng)中的全局拓撲結構重要程度，反映了該節(jié)點在整個路網(wǎng)中的地位和影響力.

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

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

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

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

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

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

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

式中 ci(Δt)——節(jié)點客運量，單位：人次/小時；

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

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

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

表2列出了在早、晚高峰和平峰三個時間，段客運量排名前6的車站.

表2 不同時間車站節(jié)點客運量Table2 The stations ranking by volume

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

2.3 邊屬性

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

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

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

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

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

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

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

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

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

通過分析可知，考慮到客運量后，結構拓撲屬性相同的節(jié)點和邊，由于其承載的客運量不同，其功能屬性及在路網(wǎng)運營中的地位是不同的.

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

3.1 關鍵節(jié)點（邊）重要度定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 聚類分析

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

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

表4 不同時間車站聚類結果分析Table4 Clustering center at different times

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

由表4、表5可知，由于不同時間段各車站和區(qū)間客運量的不同，不同時間段聚類中心各指標分類標準（均值）是不一樣的.從而證明，結合物理拓撲和運輸功能屬性，采用K-means方法可以實現(xiàn)地鐵路網(wǎng)車站和區(qū)間重要度的動態(tài)聚類分析.同一聚類中的車站和區(qū)間在物理拓撲屬性和運輸功能屬性上具有較高的相似度，物理拓撲和客運量值均較大的聚類中的車站和區(qū)間對路網(wǎng)的正常運營起到關鍵作用.

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

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

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

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

5 研究結論

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

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

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

[2]王延慶.基于接連失效的復雜網(wǎng)絡節(jié)點重要性評估[J].網(wǎ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]陳靜,孫林夫.復雜網(wǎng)絡中節(jié)點重要度評估[J].西南交通大學學報，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]莫春玲.復雜網(wǎng)絡中聚類方法及社團結構的研究[D].武漢：武漢理工大學,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].計算機技術與發(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].北京：北京航空航天大學出版社,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