Evaluation of the Importance of Complex Network Nodes Based on VIKOR Model

doi:10.3969/j.issn.1671-1122.2022.01.011

Abstract

Abstract:

When important nodes in a complex network are deliberately attacked, they will often cause a large-scale paralysis of the network. The existing centrality criterion for evaluating important nodes is only for a certain measure and it has certain limitation. Therefore, a new method combining the existing centrality criterion to rank the importance of nodes in a complex network was proposed. This method combined the criteria of degree centrality, betweenness centrality, proximity centrality and eigenvector centrality to evaluate the importance of nodes from multiple angles and directions. In this method, the entropy method is used to obtain the weight of each criterion, which avoids the deviation caused by human factors. The multi-attribute decision-making method (VIKOR) was used to sort the importance of nodes, and the virus propagation model (SI) was used to simulate the propagation process on three classic complex networks. The results show that it is consistent with the original degree index and intermediate centrality. Compared with index, proximity centrality index and feature vector centrality index, VIKOR method ranks the importance of nodes more comprehensively and accurately.

Key words: complex network, node importance, centrality criterion, entropy weight method, VIKOR model

CLC Number:

TP309

YIN Mengmeng, WANG Lei, YAO Changhua, WU Xinrong. Evaluation of the Importance of Complex Network Nodes Based on VIKOR Model[J]. Netinfo Security, 2022, 22(1): 87-94.

Figures/Tables 11

References 25

[1]	ALBERT-LÁSZLÓ B, ERIC B. Scale-free Networks[J]. Scientific American, 2003, 288(5):60-69.
[2]	ALBERT-LÁSZLÓ B. Scale-Free Networks: A Decade and Beyond[J]. Science, 2009, 325(7):292-230.
[3]	JO H H, JUNG W S, MOON H T. Dynamics of Helping Behavior and Networks in a Small World[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2006, 74(2):26-39.
[4]	WANG Chaofeng, WANG Delong. Evaluation of the Importance of Airport Network Nodes Based on TOPSIS Model[J]. Mathematics in Practice and Knowledge, 2021, 51(1):79-87.
[5]	ALBERT R, ALBERT I, NAKARADO G L. Structural Vulnerability of the North American Power Grid[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004, 69(2):25-34.
[6]	MOTTER A E. Cascade Control and Defense in Complex Networks[J]. Physical Review Letters, 2004, 93(9):98-101.
[7]	ALBERT R, JEONG H, BARABASI A L. Diameter of the World-Wide Web[J]. Nature, 1999, 401(7):130-139. doi: 10.1038/43601 URL
[8]	LIU Zhonghua, JIANG Chengjiang, WANG Juyun, et al. The Node Importance in Actual Complex Networks Based on a Multi-attribute Ranking Method[J]. Knowledge-based Systems, 2015, 79(84):55-66.
[9]	ZHOU Xuan, ZHANG Fengming, LI Kewu, et al. Using the Importance Evaluation Matrix to Determine the Key Nodes of Complex Networks[J]. Journal of Physics, 2012, 61(5):1-7.
	周漩, 张凤鸣, 李克武, 等. 利用重要度评价矩阵确定复杂网络关键节点[J]. 物理学报, 2012, 61(5):1-7.
[10]	WANG Jin, WANG Boli. Research on the Importance of Railway Network Nodes in Urban Agglomerations Based on Complex Networks[J]. Inner Mongolia Highway and Transportation, 2021, 28(4):52-57.
	王晋, 王伯礼. 基于复杂网络的城市群铁路网络节点重要度研究[J]. 内蒙古公路与运输, 2021, 28(4):52-57.
[11]	FREEMAN L C. A Set of Measures of Centrality Based on Betweenness[J]. Sociometry, 1977, 40(1):35-41. doi: 10.2307/3033543 URL
[12]	SABIDUSSI G. The Centrality Index of a Graph[J]. Psychometrika, 1966, 31(4):581-603. doi: 10.1007/BF02289527 URL
[13]	LIU Jianguo, REN Zhuoming, GUO Qiang, et al. Research Progress on the Importance of Nodes in Complex Networks[J]. Journal of Physics, 2013, 62(17):9-18.
	刘建国, 任卓明, 郭强, 等. 复杂网络中节点重要性排序的研究进展[J]. 物理学报, 2013, 62(17):9-18.
[14]	RADICCHI F, FORTUNATO S, MARKINES B, et al. Diffusion of Scientific Credits and the Ranking of Scientists[J]. Physical Review E, 2009, 80(5):56-67.
[15]	LYU Linyuan, ZHOU Tao, ZHANG Qianming, et al. The H-index of a Network Node and Its Relation to Degree and Coreness[J]. Nature Communications, 2016, 7(1):16-27.
[16]	YIN Rongrong, YIN Xueliang, CUI Mengdian, et al. Scale-free Network Node Evaluation Method Based on Importance Contribution[J]. Journal of Software, 2019, 30(6):1875-1885.
	尹荣荣, 尹学良, 崔梦頔, 等. 基于重要度贡献的无标度网络节点评估方法[J]. 软件学报, 2019, 30(6):1875-1885.
[17]	BURT R S, KILDUFF M, TASSELLI S. Social Network Analysis: Foundations and Frontiers on Advantage[J]. Annual Review of Psychology, 2013, 64(1):527-547. doi: 10.1146/psych.2013.64.issue-1 URL
[18]	GONG Kai, KANG Li. A New K-Shell Decomposition Method for Identifying Influential Spreaders of Epidemics on Community Networks[J]. Journal of Systems Science and Information, 2018, 6(4):366-375. doi: 10.21078/JSSI-2018-366-10 URL
[19]	HAN Zhongming, WU Yang, TAN Xusheng, et al. Sequencing of Key Nodes in Complex Networks Oriented to Structural Holes[J]. Journal of Physics, 2015, 64(5):429-437.
	韩忠明, 吴杨, 谭旭升, 等. 面向结构洞的复杂网络关键节点排序[J]. 物理学报, 2015, 64(5):429-437.
[20]	OPRICOVIC S, TZENG G H. Compromise Solution by MCDM Methods: A Comparative Analysis of VIKOR and TOPSIS[J]. European Journal of Operational Research, 2004, 156(2):445-455. doi: 10.1016/S0377-2217(03)00020-1 URL
[21]	ROSTAMZADEH R, GOVINDAN K, ESMAEILI A, et al. Application of Fuzzy VIKOR for Evaluation of Green Supply Chain Management Practices[J]. Ecological Indicators, 2015, 49(1):188-202. doi: 10.1016/j.ecolind.2014.09.045 URL
[22]	JUAN C RZ, JOSE M Y. Application of Multicriteria Decision Methods for Electric Supply Planning in Rural and Remote Areas[J]. Renewable and Sustainable Energy Reviews, 2015, 52(2):557-571. doi: 10.1016/j.rser.2015.07.139 URL
[23]	OPRICOVIC S. Multicriteria Optimization of Civil Engineering Systems[D]. Belgrade: University of Belgrade, 1998.
[24]	OPRICOVIC S, TZENG G H. Extended VIKOR Method in Comparison with Outranking Methods[J]. European Journal of Operational Research, 2007, 178(2):514-529. doi: 10.1016/j.ejor.2006.01.020 URL
[25]	GUO Shuyu, MIAO Shihong, YIN Haoran, et al. Construction of Coupling Model and Evaluation of Node Importance for Electric Sensor Communication Network[C]//IEEE. 1st IEEE China International Youth Conference on Electrical Engineering(CIYCEE), November 1-4, 2020, Wuhan, China. New York: IEEE, 2020: 1-6.

DC		BC		CC		EC
序号	结果	序号	结果	序号	结果	序号	结果
D	0.80	B	0.40	D	0.83	D	0.55
B	0.60	D	0.35	B	0.71	C	0.47
C	0.60	C	0.10	C	0.71	E	0.45
E	0.60	E	0.05	E	0.63	B	0.38
F	0.40	A	0.00	F	0.56	F	0.34
A	0.20	F	0.00	A	0.46	A	0.13

节点序号	Q	排序
A	1.00	6
B	0.00	1
C	0.63	3
D	0.17	2
E	0.76	4
F	0.91	5

序号	DC	结果	BC	结果	CC	结果	EC	结果	VIKOR	结果
1	3	0.429	3	0.446	3	0.628	3	0.517	3	0.000
2	2	0.306	2	0.245	2	0.563	2	0.413	2	0.324
3	18	0.163	18	0.147	18	0.490	1	0.221	18	0.580
4	1	0.163	4	0.097	1	0.462	9	0.220	1	0.656
5	4	0.143	1	0.090	4	0.462	18	0.205	4	0.704
6	9	0.143	9	0.088	9	0.462	4	0.198	9	0.737
7	17	0.143	17	0.059	10	0.438	10	0.196	17	0.797
8	10	0.102	11	0.055	17	0.434	5	0.161	23	0.831
9	16	0.102	23	0.053	5	0.430	17	0.158	11	0.837
10	23	0.102	5	0.046	11	0.430	7	0.146	5	0.842

	节点数	连接概率	每次加入边数	邻居数	随机化重连边概率
ER	300	0.03	—	—	—
BA	300	—	2	—	—
WS	300	—	—	5	0.1