兰州市公交网络的社团结构与脆弱性分析

马宇红，李 宪，陈 闪，张 琴

(1.西北师范大学学报编辑部，甘肃兰州 730070；2.西北师范大学数学与统计学院，甘肃兰州 730070)



兰州市公交网络的社团结构与脆弱性分析

马宇红1,2，李 宪2，陈 闪2，张 琴2

(1.西北师范大学学报编辑部，甘肃兰州 730070；2.西北师范大学数学与统计学院，甘肃兰州 730070)

基于复杂网络理论，研究兰州市公交网络的社团结构及其脆弱性.根据实证数据建立了兰州市公交网络的结构模型，并应用Fast Newman算法分析公交网络的社团结构，给出了最优的社团划分；从获得的社团结构出发，分析了兰州市公交网络社团结构的脆弱性，给出了各个社团的脆弱集及脆弱性指标.研究结果表明，兰州市公交网络具有明显的社团结构特性，社团划分受到城市独特地形特性的影响；许多社团在网络中表现异常脆弱，社团之间联系稀疏，极易因为随机故障或蓄意攻击而形成多个独立的连通分支.

公交网络；社团结构；社团划分；脆弱性

0 引言

交通问题是21世纪城市发展必须面对的重大问题，许多国家和地区通过大力发展公共交通运输体系来解决这一问题，一个稳定高效的公交网络对于人们的日常生活和城市的发展至关重要，所以分析城市公交网络的脆弱性，确定相对脆弱部分，并在公交线路设计和结构优化过程中进行有针对性的改善与防护是非常必要的.

随着计算机技术的飞速发展，网络科学在20世纪末取得了突破性进展，相关理论已经渗透到了数学、物理学、生物学、社会学等诸多学科，成为一个跨学科的新兴领域.复杂网络理论[1]可以为许多实际问题的研究提供了新的视角和方法，运用计算机技术和复杂网络理论对各种实际网络进行模拟分析开始受到学者的广泛关注，例如城市公交网络性能分析[2]、电力系统安全评估[3]、通讯网络故障检测[4]等.

复杂网络的脆弱性研究源于Albert等[5]，此后，各种网络模型和实际网络的脆弱性问题引起了研究者的极大兴趣[6-9]，相关研究致力于分析随机故障或蓄意攻击对网络连通性的影响，即按照某种规则从网络中删除部分节点对网络连通性及巨片规模的影响.同时，为了多角度衡量网络中节点的重要性，除了度、介数等传统的度量外，一些新的中心性度量指标，例如modal[10]、pagerank[11]等相继被提出.但是，现有文献多着重于节点故障对网络鲁棒性的影响，事实上，边的脆弱性对网络鲁棒性的影响同样重要，因此，本文从社团结构角度出发，分析兰州市公交网络的最优社团划分，并确定各个社团的脆弱集及脆弱性指标，为交通部门优化线路设计、增强网络鲁棒性提供参考.

1 社团结构分析与脆弱性评价方法

社团结构作为复杂网络的一项重要性质得到了广泛关注，许多真实世界的网络都已经被证实具有社团结构[12-13].网络的社团结构指的是网络中的节点可以被划分为若干组，组内节点之间连接紧密而不同组节点之间连接较为稀疏.对于公交网络而言，分析它的社团结构可以帮助我们发现网络中连通性较好的区域以及区域与区域之间连通性较差的部分，从而有针对性地改进和防护那些脆弱部分，增强整个公交体系的鲁棒性.

1.1 Fast Newman算法

网络的社团结构与计算机科学中的图分割和社会学中的分级聚类有着密切关系，早在20世纪70年代初就已经引起了研究者的兴趣，一系列发掘社团结构的算法相继被提出，如基于贪婪算法的Kernighan-Lin算法[14]、基于Laplace图特征值的谱分解法[15]、基于分级聚类的Concor算法[16]和基于分裂方法的GN算法[12]等，而目前应用最广泛的是基于优化模块度的算法，如Fast Newman算法(简称FN算法)[17]等.在社团划分算法中，模块度函数被用来评价社团划分的质量，对于一个已知网络，具有最大模块度的社团划分即为最优划分.2004年，Newman和Girvan定义了模块度函数[18]：

(1)

(2)

其中，ei为社团i内部边的数量；di指属于社团i的所有节点度的和；m为网络的总边数.

FN算法[17]是一种基于贪婪思想的凝聚算法，它通过寻找最大模块度Qmax对应的社团划分来确定网络的最优划分.相比其他一系列算法，它的运行速度显著提升，算法复杂度为O((m+n)n)，其中n为网络节点数，m为网络总边数.FN算法的具体步骤如下：

1)初始化网络为n个社团，即每个节点组成1个独立社团.eij和ai分别定义为

ai=ki/2m,

其中，ki为节点i的度；m为网络总边数.

2)依次合并有边相连的社团对，并计算合并之后的模块度增量ΔQ，

(3)

3)取ΔQ为最大值对应的两个社团合并为一个社团.

4)重复步骤2)和3)，直到整个网络被合并为一个社团，结束算法.

1.2 社团脆弱性方法

2011年，Claudio等[19]提出了一个度量来评价大规模网络社团结构的脆弱性.该方法根据网络的社团结构划分计算连接各社团之间的边，得到各个社团的脆弱边集，再通过计算每个社团的相对脆弱性指标来评价其脆弱性.当某个社团的脆弱边因随机故障或者蓄意攻击而中断时，该社团就会与相邻的其他社团或者网络的其余部分彻底分离，形成一个独立的连通分支.如果所有社团的脆弱边全部中断，网络会迅速分裂成若干孤立的连通分支，彼此完全失去联系.这种方法介绍如下：

给定一个具有确定社团结构的网络G=(V,E)，其中V是节点集，E是边集，Cx(x∈Λ)表示网络的社团集，且对∀x,y∈Λ,Cx∩Cy=∅.网络中社团x和社团y之间的脆弱集Vxy定义为

Vxy={(u,v)∈E,u∈Cx,v∈Cy,x≠y},

(4)

破坏Vxy中所有的边即可使社团x与社团y失去直接联系.社团x，y之间的脆弱性指标vxy定义为

(5)

(6)

移除Vx中所有的边即可使得社团x与网络的其余部分完全失去联系，变成一个孤立的连通分支.社团x的脆弱性指标vx定义为

(7)

最后，社团x的相对脆弱值定义为

(8)

2 实例分析

本节应用FN算法和Claudio脆弱性方法分析兰州市公交网络的结构社团划分及其脆弱性，并给出每个社团的脆弱集及相对脆弱性指标.

2.1 兰州市公交网络建模

在公交网络建模过程中，对公交数据的处理遵循以下原则：

1)仅考虑城关、七里河、安宁、西固区线路，不考虑红古、永登、皋兰、榆中三县一区线路.

2)一条公交线路在某些路段上下行站点不一致时，统一取上行线路站点.

3)某些线路上下行停靠站名不一致但实际为同一地点时，将它们合并为一个站点.例如城关黄河桥南与市政府、广场南路西口与广场南口等.

4)同一个站名具有多个停车点时视为同一站点，如兰州西站东、南、西、北四个方向的停车点视为同一站点.

5)不考虑兰州轨道交通施工等因素导致的临时线路调整.

图1 兰州市公交网络Fig 1Image of Lanzhou bus transport network

兰州市公交网络的拓扑结构如图1所示，节点代表公交站点，边代表公交线路上相邻两个站点之间的连边.兰州市公交网络的拓扑性质见表1.

表1 兰州市公交网络的基本拓扑性质Tab 1 Basic topological properties of Lanzhou bus transport network

2.2 社团划分

通过执行FN算法，我们得到兰州市公交网络的最优社团划分为20个社团，对应的最大模块度Qmax=0.838 8(图2)，大于许多实际网络Qmax介于0.3～0.7的范围[18]，所以兰州市公交网络具有很强社团结构特性.规模最大的社团包含65个节点，规模最小的社团仅包含8个节点.由于网络规模较大，通过图示或树状图可视化具体的社团划分比较困难，所以我们仅给出每个社团的规模及与其他社团有边相连的边界点，不给出每个社团包含哪些具体站点，详见表2.

图2 FN算法节点合并过程中的模块度Q值Fig 2 The value of modular Q in the process of node merging by FN algorithm

从表2可知，社团1,18,15,17,20是规模最大的5个社团，分别包含65,58,43,42,42个公交站点.结合具体的公交网络可知，社团1和社团18在地理位置上彼此相邻，社团内的公交站点占据了城关区的主要区域；社团15位于西固区的主要区域，社团17和社团20分别位于安宁区和七里河区的主要区域.这些规模较大社团的形成与兰州市各区内部公交线路相对密集的特性有着较大关系，自然容易形成联系紧密的社团.

表2 兰州市公交网络各社团的边界站点Tab 2 The boundary nodes for communities of Lanzhou bus transport network

从各社团的分布区域看，社团4位于黄河北岸与白塔山之间的狭窄地段，社团6,9,13,17分别位于黄河北岸九州、大砂坪、庙滩子、安宁地区；社团5,7,12,14位于铁路南侧与南山之间的狭窄区域，而其余社团则位于黄河南岸与铁路北侧的主城区.这说明兰州市公交网络的社团划分明显受到了兰州市河谷型地形特性以及黄河与陇海、兰新铁路穿城而过对城市区域两次切割的影响.

2.3 社团脆弱性分析

通过计算得到各个社团的脆弱集Vx及相对脆弱性指标Rx的值见表3.

分析脆弱集Vx(x=1,2,…,20)中的站点，我们发现他们相当一部分位于黄河两岸以及铁路两侧.由于黄河两岸仅能通过黄河桥相连，而铁路两侧仅能通过下穿道路连通，所以黄河北岸和铁路南侧区域与主城区联系通道较少，并且这些区段又是兰州市交通流量最密集的路段，例如西站双洞子、城关黄河大桥等，这些站点在兰州市公交体系中极其重要，一旦遭遇道路维修、交通事故、车辆限行等突发性交通状况，很容易造成交通拥堵，甚至交通中断.

从上述分析可以看出，兰州市公交网络不同社团之间联系较为稀疏，许多社团表现异常脆弱，很容易因为几条边受到攻击而被隔离于网络之外.在日常运营中，交通拥堵、道路维修等随机事件很容易破坏公交网络的连通性，如果以此为策略蓄意攻击这些脆弱边，那么网络会迅速分裂成若干个孤立的连通分支.因此，在后续的公交线路设计与优化过程中，应该适当增加公交线路串联那些脆弱社团之间的节点，增加社团之间的连边，从而提高网络的抗毁性.另一方面，在城市建设中应该考虑增加连接黄河南北两岸和铁路南北两侧之间的通道，使得公交线路设计更灵活，运营更稳健.

表3 兰州市公交网络各社团脆弱集和相对脆弱值Tab 3 Vulnerability sets and relative vulnerability ofcommunities of Lanzhou bus transport network

3 结论

基于复杂网络理论，从社团结构角度分析了兰州市公交网络的社团划分及社团脆弱性.结果表明，兰州市公交网络具有典型的社团结构特性，大致可以被划分为20个社团，结构划分很大程度上受到兰州市特有的河谷型城市地形特性以及黄河、铁路对城市区域分割的影响；许多社团在网络中表现异常脆弱，社团间的联系极为稀疏，很容易因为随机故障或蓄意攻击而成为孤立的连通分支.下一步，我们将在公交线路优化设计中研究如何强化网络的脆弱部分，从而提高其稳健性，更好地服务于乘客出行和城市发展.

[1] NEWMAN M E J.Networks:AnIntroduction[M].New York:Oxford University Press,2010.

[2] YANG X H,CHEN G,CHEN S Y,et al.Study on some bus transport networks in China with considering spatial characteristics[J].TransportationResearchPartA,2014,69:1.

[3] SEKSAR P,MOHANTY S.An online power system static security assessment module using multi-layer perception and radial basis function network[J].ElectricalPowerandEnergySystems,2016,76:165.

[4] HONG S,YANG Y,ZIO E,et al.A novel dynamics model of fault propagation and equilibrium analysis in complex dynamical communication network[J].AppliedMathematicsandComputation,2014,247:1021.

[5] ALBERT R,JEONG H,BARABASI A L.Attack and error tolerance of complex networks[J].Nature,2000,406(6794):387.

[6] LORDAN O,SALLAN J M,SIMO P,et al.Robustness of the air transport network[J].TransportationResearchPartE,2014,68(9):155.

[7] CALLAWAY D S,NEWMAN M E J,STROGATZ S H,et al.Network robustness and fragility:percolation on random graphs[J].PhysicalReviewLetters,2000,85(25):5468.

[8] CRUCITTI P,LATORA V,MARCHIORI M,et al.Efficiency of scale-free networks:error and attack tolerance[J].PhysicaA,2003,320(C):622.

[9] ALBERT R,ALBERT I,NAKARADO G L.Structural vulnerability of the North American power grid[J].PhysicalReviewE,2004,69(2):292.

[10] PETRESKA I,TOMOVSKI I,GUTIERREZ E,et al.Application of modal analysis in assessing attack vulnerability of complex networks[J].CommunicationsinNonlinearScience&NumericalSimulation,2010,15(4):1008.

[11] BRIN S,PAGE L.The anatomy of a large-scale hypertextual web search engine[J].ComputerNetworksandISDNSystem,1998,30(98):107.

[12] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].ProceedingsoftheNationalAcademyofSciences,2002,99(12):7821.

[13] FLAKE G W,LAWRENCE S R,GILES C L,et al.Self-organization and identification of Web communities[J].IEEEComputer,2002,35:66.

[14] KERNIGHAN B W,LIN S.A efficient heuristic procedure for partitioning graphs[J].BellSystemTechnicalJournal,1970,49:291.

[15] POTHEN A,SIMON H,LIOU K P.Partitioning sparse matrices with eigenvectors of graphs[J].SIAMJMatrixAnalAppl,1990,11:430.

[16] BREIGER R L,BOORMAN S A,ARABIE P.An algorithm for clustering relations data with applications to social network analysis and comparison with multidimensional scaling[J].JournalofMathematicalPsychology,1975,12:328.

[17] NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].PhysicalReviewEStatisticalNonlinear&SoftMatterPhysics,2004,69(6):279.

[18] NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in network[J].PhysRevE,2004,69:026113.

[19] CLAUDIO M R S,RAMIREZ M J E.Vulnerability metrics and analysis for communities in complex networks[J].ReliabilityEngineering&SystemSafety,2011,96(10):1360.

(责任编辑 马宇鸿)

Analysis on community structure and vulnerability for Lanzhou bus transport network

MA Yu-hong1,2,LI Xian2,CHEN Shan2,ZHANG Qin2

(1.Editorial Department of the University Journal,Northwest Normal University,Lanzhou 730070,Gansu,China;2.College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,Gansu,China)

The community structure and its vulnerability are investigated for Lanzhou bus transport network based on complex network theory.Firstly,the bus transport network model of Lanzhou City is established based on empirical data，and then its community structure is discussed by use of Fast Newman algorithm,the optimal community division is given.Finally,the vulnerability of Lanzhou bus transport network is analysed from the perspective of the community structure,and the vulnerable set and vulnerability index of every community are determined in detail.The results demonstrate that Lanzhou bus transport network has obvious community structure characteristics,and the community division is influenced by its distinctive urban terrain features;a lot of communities are very weak in the network and the connection between different communities is rather sparse.So the network is fragile under random failures and deliberate attacks,it is very easy to form several independent connected branches.

bus transport network;community structure;community division;vulnerability

10.16783/j.cnki.nwnuz.2016.01.006

2015-07-07;修改稿收到日期:2015-10-22

国家自然科学基金资助项目(51368055)

马宇红(1971—)，男，甘肃天水人，副编审，博士.主要研究方向为网络设计与优化.

E-mail:mayh@nwnu.edu.cn

O 221.2；U 491.1+7

A

1001-988Ⅹ(2016)01-0025-06