Robustness Analysis and Optimization of Urban Public Transport Network Based on Complex Network Theory

doi:10.3778/j.issn.1002-8331.2011-0121

Abstract

Abstract: In the past, the research on urban public transport network mainly focused on the nature of network topology, but less on the optimization of network robustness. After getting the real-time bus routes from the bus route website, the topology model of urban public transport network is constructed based on Python software. The connectivity, the relative size of the largest connected subgraph and the network efficiency are used as the robustness evaluation indexes of the public transport network. The network is attacked by degree attack and random attack mode. The results show that the urban public transport network has good robustness under random attack mode, and the robustness of urban public transport network is poor under degree attack mode. After optimizing the network by using high degree, high betweenness, low degree, low betweenness and random addition, it is concluded that the low degree and low betweenness strategies have a great improvement on the network robustness, while the high betweenness and high degree strategies have no improvement on the network robustness.

Key words: public transport network, robustness, border addition strategy, connectivity

摘要： 以往对城市公交网络的研究多集中在网络拓扑结构的性质上，关于优化网络鲁棒性的研究较少。从公交路线网站上获取某市实时公交路线后，基于Python软件构建了该市公交网络拓扑结构模型。采用连通度、最大连通子图的相对大小、网络效率作为公交网络鲁棒性评价指标，以节点度攻击与随机攻击模式对网络进行攻击，结果表明随机攻击模式下该市公交网络鲁棒性较好，节点度攻击模式下该市公交网络鲁棒性较差。在采用高度数加边、高介数加边、低度数加边、低介数加边和随机加边策略对网络进行鲁棒优化后对比得出，低度数和低介数加边策略对网络鲁棒性提升效果好，高介数和高度数加边策略不能提升网络鲁棒性。

关键词: 公交网络, 鲁棒性, 加边策略, 连通度

LAI Qiang, ZHANG Honghao, WANG Xuxu. Robustness Analysis and Optimization of Urban Public Transport Network Based on Complex Network Theory[J]. Computer Engineering and Applications, 2022, 58(10): 249-254.

赖强, 张宏昊, 王徐盱. 基于复杂网络理论的城市公交网络鲁棒性分析与优化[J]. 计算机工程与应用, 2022, 58(10): 249-254.

References

[1] TRAN V H，CHEONG S A，BUI N D.Complex network analysis of the robustness of the Hanoi，Vietnam bus network[J].Journal of Systems Science and Complexity，2019，32：1251-1263.
[2] LU M，ZHANG Z L，QU Z H et al.LPANNI：overlapping community detection using?label?propagation?in large-scale complex networks[J].IEEE Transactions on Knowledge and Data Engineering，2019，31（9）：1736-1749.
[3] ZHU X，YANG Q，TIAN H et al.Contagion of information on two-layered weighted complex network[J].IEEE Access，2019，7：155064-155074.
[4] QIAO S.A fast parallel community discovery model on complex networks through approximate optimization[J].IEEE Transactions on Knowledge and Data Engineering，2018，30（9）：1638-1651.
[5] CHEN G R，LOU Y，WANG L.A comparative study on controllability robustness of complex networks[J].IEEE Transactions on Circuits and Systems II：Express Briefs，2019，66（5）：828-832.
[6] CLEMENTE G P，CORNARO A.A novel measure of edge and vertex centrality for assessing robustness in complex networks[J].Soft Computing，2020，24：13687-13704.
[7] SAFAEI F，YEGANLOO H，AKBAR R.Robustness on topology reconfiguration of complex networks：an entropic approach[J].Mathematics and Computers in Simulation，2020，170：379-409.
[8] SHANG Y L.Subgraph robustness of complex networks under attacks[J].IEEE Transactions on Systems，Man，and Cybernetics：Systems，2019，49（4）：821-832.
[9] LIANG M，JIN S Q，WANG D J，et al.Optimization of controllability and robustness of complex networks by edge[J].European Physical Journal B，2016，89：186.
[10] 齐立磊，赵丹丹.基于复杂网络的城市公交系统优化研究[J].西南师范大学学报（自然科学版），2014，39（7）：102-107.
QI L L，ZHAO D D.Urban bus transport network optimization form complex network[J].Journal of Southwest China Normal University（Natural Science Edition），2014，39（7）：102-107.
[11] ALVINSYAH，HADIAN E.A demand and capacity analysis on bus semirapid transit network[J].MATEC Web of Conferences，2018，181（1）：10001.
[12] TIAN Z W，ZHANG Z，WANG H F et al.Complexity analysis on public transport networks of 97 large-and medium-sized cities in China[J].International Journal of Modern Physics B，2018，32（9）：1850108.
[13] JIN H T，JIN F J，ZHU H.Measuring spatial mismatch between public transit services and regular riders：a case study of Beijing[J].ISPRS International Journal of Geo-Information，2019，8（4）：186.
[14] ZHANG H.Structural analysis of bus networks using indicators of graph theory and complex network theory[J].The Open Civil Engineering Journal，2017，11：92-100.
[15] DE BONA A A，FONSECA K V O，ROSA M O，et al.Analysis of public bus transportation of a Brazilian city based on the theory of complex networks using the P-Space[J].Mathematical Problems in Engineering，2016（3）：1-12.
[16] CHEN H H，LIN A M.Complex network characteristics and invulnerability simulating analysis of supply chain[J].Journal of Networks，2012，7（3）：591-597.
[17] YI C Q，BAO Y Y，JIANG J C et al.Mitigation strategy against cascading failures on social networks[J].China Communications，2014，11（8）：37-46.
[18] 丁涛，高双，花泽春.基于复杂网络的人道物流网络鲁棒性分析[J].物流技术，2016，35（3）：82-86.
DING T，GAO S，HUA Z C，et al.Analysis of robustness of humanitarian logistics networks based on complex network[J].Logistics Technology，2016，35（3）：82-86.
[19] 党亚茹，丁飞雅，史丽媛，等.基于航线失效模式下的航班流网络抗毁性分析[J].中国民航大学学报，2014，32（1）：64-69.
DANG Y R，DING F Y，SHI L Y，et al.Analysis of flight flow network survivability based on failure of flight mode[J].Journal of Civil Aviation University of China，2014，32（1）：64-69.
[20] 刘涤尘，冀星沛，陈果，等.基于复杂网络理论的电力通信网加边保护策略[J].电力自动化设备，2016，36（10）：121-126.
LIU D C，JI X P，CHEN G，et al.Link addition strategy based on complex network theory for power communication network[J].Electric Power Automation Equipment，2016，36（10）：121-126.