地铁网络中的关键节点对其连通性有着重要的影响。在有限的资源以及人力物力下，找出其中的关键节点进行强化管理以减小随机故障对整个网络造成的损失是非常重要的。应用二次约束二次规划模型，针对赋权网络，综合考虑节点移除后对网络的整体结构和功能的影响，给出了计算网络连通性的一个新测度——一步连接和两步连接；并基于模型特点设计了遗传算法。最后，以北京市地铁网络为例进行求解，表明了该方法的有效性和优越性。
Critical nodes in the metro network have an important impact on their connectivity. Under limited manpower and material resources, it is very important to find out the critical nodes for enhanced management to reduce the damage caused by random failures to the entire network. Comprehensively considering the impact of node removal on the overall structure and function of the weighted network, this paper presents a new measure of computing network connectivity-one-step and two-step connections based on the quadratic constrained quadratic programming model. An genetic algorithm is then designed according to the characteristics of the model. Finally, the Beijing metro network is taken as an example to solve the problem. The results show the effectiveness and superiority of the proposed method.
[1] Latora V, Marchiori M. Is the Boston subway a small-world network?[J]. Physica A:Statistical Mechanics and its Applications, 2002, 314(1):109-113.
[2] 张建华. 地铁复杂网络的连通脆弱性研究[D]. 武汉:华中科技大学, 2012.
[3] 叶青. 基于复杂网络理论的轨道交通网络脆弱性分析[J]. 中国安全科学学报, 2012, 22(2):122-126.
[4] 王云琴. 基于复杂网络理论的城市轨道交通网络连通可靠性研究[D]. 北京:北京交通大学, 2008.
[5] 李鹏翔, 任玉晴, 席酉民. 网络节点(集)重要性的一种度量指标[J]. 系统工程, 2004, 22(4):13-20.
[6] Weng J, Lim E P, Jiang J, et al. TwitterRank:finding topic-sensitive influential Twitterers[C]//ACM International Conference on Web Search and Data Mining, 2010:261-270.
[7] Enns E A, Mounzer J J, Brandeau M L. Optimal link removal for epidemic mitigation:a two-way partitioning approach[J]. Mathematical Biosciences, 2012, 235(2):138-147.
[8] Latora V, Marchiori M. How the science of complex networks can help developing strategies against terrorism[J]. Chaos, Solitons and Fractals, 2004, 20:69-75.
[9] Ventresca M, Aleman D. A derandomized approximation algorithm for the critical node detection problem[J]. Computers & Operations Research, 2014, 43(4):261-270.
[10] Jiang C, Liu Z, Wang J, et al. An optimal approach for the critical node problem using semidefinite programming[J]. Physica A:Statistical Mechanics and its Applications, 2017, 471:315-324.
[11] 任晓龙, 吕琳媛. 网络重要节点排序方法综述[J]. 科学通报, 2014, 59(13):1175-1197.
[12] Jin J, Li M, Wang Y, et al. Importance analysis of urban rail transit network station based on passenger[J]. Journal of Intelligent Learning Systems and Applications, 2013, 5(4):232-236.
[13] Borgatti S P. Identifying sets of key players in a social network[J]. Computational & Mathematical Organization Theory, 2006, 12(1):21-34.
[14] Albert R, Jeong H, Barabasi A L. Error and attack tolerance of complex networks[J]. Nature, 2000, 340(1):378-382.
[15] 王海燕. 基于复杂网络的城市轨道交通网络形态分析[D]. 北京:北京交通大学, 2014.
[16] 张丽佳. 基于复杂网络的北京地铁网络结构特征与抗攻击能力研究[D]. 北京:中国地质大学(北京), 2014.
[17] 司守奎, 孙玺菁. 数学建模算法与应用[M]. 北京:国防工业出版社, 2011.
[18] 北京城市轨道交通线网图[EB/OL].[2018-10-20]. https://www.bjsubway.com/jpg.html.
