An improved betweenness for importance assessment of network nodes and links

doi:10.16265/j.cnki.issn1003-3033.2022.03.005

Abstract

Abstract:

In order to accurately evaluate importance of nodes and links in the network system, three kinds of situations concerning anti-attack capability of network system were analyzed, and based on the definition of traditional betweenness, an improved definition of network node and link betweenness was proposed, which was the number of times that all OD pairs passed through a node or link to meet the given constraint condition. Then, a new RSA was proposed to solve the improved betweenness of nodes and links. Finally, the traditional and improved betweenness of each node and link in Beijing subway network were calculated to evaluate their importance, and calculation results of traditional and improved betweenness were compared. The results show that the improved betweenness is a universal definition, while the traditional one is only one of its special cases, and it can evaluate importance of nodes and links from a more comprehensive perspective.

Key words: nodes and links, improved betweenness, network system, origin-destination (OD) pairs, ripple-spreading algorithm(RSA), Beijing subway network

HU Xiaobing, LI Jiaru, LIU Chengyue, LI Hang, ZHOU Hang. An improved betweenness for importance assessment of network nodes and links[J]. China Safety Science Journal, 2022, 32(3): 33-40.

Figures/Tables 6

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Tab.1

References 13

[1]	ALBERT R, BARABASI A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002, 74(1): 47-97. doi: 10.1103/RevModPhys.74.47
[2]	PALLETI V R, ADEPU S, MISHRA V K, et al. Cascading effects of cyber-attacks on interconnected critical infrastructure[J]. Cybersecurity, 2021, 4(1):1-19. doi: 10.1186/s42400-020-00065-3
[3]	MAZZOCCHI M, HANSSTEIN F, RAGONA M. The 2010 volcanic ash cloud and its financial impact on the european airline industry[J]. Cesifo Forum, 2010, 11(2):92-100.
[4]	BOCCALETTI S, LATORA V, MORENO Y, et al. Complex networks: structure and dynamics[J]. Physics Reports, 2006, 424(4/5): 175-308. doi: 10.1016/j.physrep.2005.10.009
[5]	李航, 胡小兵, 郭晓梅, 等. 空间脆弱性与传统网络属性的关系[J]. 复杂系统与复杂性科学, 2017, 14(1):1-7,65.
	LI Hang, HU Xiaobing, GUO Xiaomei, et al. Relationship between spatial vulnerability and traditional network properties[J]. Complex Systems and Complexity Science, 2017, 14(1): 1-7,65.
[6]	王志强, 李欣, 李岩, 等. 基于复杂网络与风险的电网综合脆弱性评估[J]. 现代电力, 2014, 31(3):49-55.
	WANG Zhiqiang, LI Xin, LI Yan, et al. Comprehensive vulnerability evaluation of power grid based on complex network and risk theory[J]. Modern Electric Power, 2014, 31(3):49-55.
[7]	周庚. 复杂网络节点中心性度量算法的研究及应用[D]. 兰州: 兰州理工大学,2020.
	ZHOU Geng. Research ang application of node cebtrality measurement algorithm in complex networks[D]. Lanzhou: Lanzhou University of Technology,2020.
[8]	HU Xiaobing, WANG Ming, LEESON M S, et al. Deterministic agent-based path optimization by mimicking the spreading of ripples[J]. Evolutionary Computation, 2016, 24(2):319-346. doi: 10.1162/EVCO_a_00156 pmid: 26066805
[9]	MOHANTA K. Comprehensive study on computational methods for k-shortest paths problem[J]. International Journal of Computer Applications, 2013, 40(14):22-26.
[10]	HU Xiaobing, ZHANG Chi, ZHANG Gongpeng, et al. Finding the k shortest paths by ripple-spreading algorithms[J]. Engineering Applications of Artificial Intelligence, 2020,87:1-21.
[11]	李亚飞, 梁琛, 戴福青. 航路网关键节点识别及抗毁性分析[J]. 中国安全科学学报, 2020, 30(5):115-121. doi: 10.16265/j.cnki.issn1003-3033.2020.05.018
	LI Yafei, LIANG Chen, DAI Fuqing. Key node identification and invulnerability analysis of China's air route network[J]. China Safety Science Journal, 2020, 30(5):115-121. doi: 10.16265/j.cnki.issn1003-3033.2020.05.018
[12]	王敏. 复杂网络中关键节点挖掘与社区发现算法研究[D]. 成都: 电子科技大学,2020.
	WANG Min. Key nodes identification and community detection in complex networks.[D]. Chengdu: University of Electronic Science and Technology of China,2020.
[13]	郭文亚, 周志鹏. 地铁工程建设安全事故致因网络模型构建与解析[J]. 中国安全科学学报, 2020, 30(1):155-161. doi: 10.16265/j.cnki.issn1003-3033.2020.01.024
	GUO Wenya, ZHOU Zhipeng. Subway construction accident causation network modeling and analysis[J]. China Safety Science Journal, 2020, 30(1): 155-161. doi: 10.16265/j.cnki.issn1003-3033.2020.01.024

k	结点排序								链接排序
k	排序		车站名称	车站编号	车站线路			改进介数	区间对应车站	区间编号		改进介数
1	1		朝阳门	21	2,6			1	南锣鼓巷—东四	56-45		1
	2		建国门	9	1,2			0.919	朝阳门—建国门	21-9		0.907
	3		东四	45	5,6			0.908	望京—望京西	103-100		0.893
	4		东单	8	1,5			0.746	磁器口—崇文门	44-23		0.788
	5		崇文门	23	2,5			0.745	北京西站—军事博物馆	62-4		0.786
1.05	1		西直门	16	2,4,13			1	望京—望京西	103-100		1
	2		军事博物馆	4	1,9			0.977	南锣鼓巷—东四	56-45		0.902
	3		东四	45	5,6			0.974	军事博物馆—复兴门	4-5		0.902
	4		车公庄	26	2,6			0.915	车公庄—西直门	26-16		0.876
	5		朝阳门	21	2,6			0.905	六里桥—北京西站	84-62		0.853
1.1	1	军事博物馆		4		1,9	1		军事博物馆—复兴门		4-5	1
	2	东四		45		5,6	0.915		郭公庄—七里庄		82-83	0.935
	3	六里桥		84		9,10	0.902		六里桥—北京西站		84-62	0.886
	4	东单		8		1,5	0.881		建国门—国贸		9-10	0.879
	5	朝阳门		21		2,6	0.865		平安里—南锣鼓巷		33-56	0.809
1.15	1	军事博物馆		4		1,9	1		军事博物馆—复兴门		4-5	1
	2	东单		8		1,5	0.915		建国门—国贸		9-10	0.925
	3	建国门		9		1,2	0.938		郭公庄—七里庄		82-83	0.826
	4	东四		45		5,6	0.937		六里桥—北京西站		84-62	0.824
	5	朝阳门		21		2,6	0.927		东单—东四		8-45	0.783
1.2	1	军事博物馆		4		1,9	1		军事博物馆—复兴门		4-5	1
	2	东单		8		1,5	0.996		建国门—国贸		9-10	0.925
	3	建国门		9		1,2	0.975		东单—东四		8-45	0.835
	4	朝阳门		21		2,6	0.962		南锣鼓巷—东四		56-45	0.786
	5	东四		45		5,6	0.962		朝阳门—建国门		21-9	0.782