A multidimensional node importance evaluation method based on graph convolutional networks

Wang Bo-Ya; Yang Xiao-Chun; Lu Sheng-Rong; Tang Yong-Ping; Hong Shu-Quan; Jiang Hui-Yuan

doi:10.7498/aps.73.20240937

Abstract
This paper deals with the problem of identifying, evaluating, and ranking key nodes in complex networks by introducing a novel multi-parameter control graph convolutional network (MPC-GCN) for assessing node importance. Drawing inspiration from the multidimensional and hierarchical interactions between nodes in physical systems, this method integrates the automatic feature learning capabilities of graph convolutional networks (GCNs) with a comprehensive analysis of intrinsic properties of nodes, their interactions with neighbors, and their roles in the broader network. The MPC-GCN model provides an innovative framework for identifying key node by using GCNs to iteratively aggregate node and neighbor features across layers. This process captures and combines local, global, and positional characteristics, enabling a more nuanced, multidimensional assessment of node importance. Moreover, the model also includes a flexible parameter adjustment mechanism that allows for adjusting the relative weights of different dimensions, thereby adapting the evaluation process to various network structures. To validate the effectiveness of the model, we first test the influence of model parameters on randomly generated small networks. We then conduct extensive simulations on eight large-scale networks by using the susceptible-infected-recovered (SIR) model. Evaluation metrics, including the M(R) score, Kendall’s tau correlation, the proportion of infected nodes, and the relative size of the largest connected component, are used to assess the model’s performance. The results demonstrate that MPC-GCN outperforms existing methods in terms of monotonicity, accuracy, applicability, and robustness, providing more precise differentiation of node importance. By addressing the limitations of current methods, such as their reliance on single-dimensional perspectives and lack of adaptability, the MPC-GCN provides a more comprehensive and flexible approach to node importance assessment. This method significantly improves the breadth and applicability of node ranking in complex networks.

Keywords:
graph convolutional networks /

multidimension parameters /

node importance
FullText HTML : translate this paragraph

Cited By

图 1 随机生成的网络G₁₂

Figure 1. Randomly generated networks G₁₂.

DownLoad: Full-Size Img PowerPoint

图 2 随机森林模型评估MPC-GCN模型效果　(a)回归散点图; (b)特征重要性图

Figure 2. Random forest model evaluation of MPC-GCN model performance: (a) Regression scatter plot; (b) feature importance plot.

DownLoad: Full-Size Img PowerPoint

图 4 8种节点排序性方法在8个网络上的Kendall相关系数对比　(a) Karate; (b) Jazz; (c) NS; (d) USAir; (e) PB; (f) Route; (g) G₃₀₀; (h) G₁₀₀₁₀

Figure 4. Comparison of Kendall’s Tau coefficient for 8 node ranking methods on 8 networks: (a) Karate; (b) Jazz; (c) NS; (d) USAir; (e) PB; (f) Route; (g) G₃₀₀; (h) G₁₀₀₁₀.

DownLoad: Full-Size Img PowerPoint

图 6 网络最大连通子图随移除节点比例变化情况　(a) Karate; (b) Jazz; (c) NS; (d) USAir; (e) PB; (f) Route; (g) G₃₀₀; (h) G₁₀₀₁₀

Figure 6. Variation of the network’s largest connected component with the proportion of removed nodes: (a) Karate; (b) Jazz; (c) NS; (d) USAir; (e) PB; (f) Route; (g) G₃₀₀; (h) G₁₀₀₁₀.

DownLoad: Full-Size Img PowerPoint

图 3 不同评估方法在8个网络上的单调性指标M

Figure 3. Monotonicity metrics M of various assessment methods on 8 networks.

DownLoad: Full-Size Img PowerPoint

图 5 以前5%为初始感染节点的8种节点排序性方法在8个网络上的传染情况对比　(a) Karate; (b) Jazz; (c) NS; (d) USAir; (e) PB; (f) Route; (g) G₃₀₀; (h) G₁₀₀₁₀

Figure 5. Comparison of infection dynamics among 8 node ranking methods initiated with the top 5% nodes as infections on 8 networks: (a) Karate; (b) Jazz; (c) NS; (d) USAir; (e) PB; (f) Route; (g) G₃₀₀; (h) G₁₀₀₁₀.

DownLoad: Full-Size Img PowerPoint

表 2 8个网络参数描述

Table 2. Parameters description of 8 networks.

网络	V	E	$ \left\langle k \right\rangle $	$ {k_{\max }} $	$ \left\langle d \right\rangle $	$ {d_{\max }} $	$ {\mu _{{\text{th}}}} $	D	C
Karate	33	54	6.5455	22	1.9924	4	0.1134	0.14	0.57
Jazz	198	2742	27.6970	100	2.2350	6	0.0266	0.14	0.62
NS	379	914	4.8232	34	6.0419	17	0.0964	0.013	0.74
USAir	332	2126	12.8072	139	2.7381	6	0.0243	0.039	0.63
PB	1222	16714	27.3552	351	2.7375	8	0.0125	0.022	0.32
Router	5022	6258	2.49	106	6.4488	15	0.0583	0.00050	0.012
G₃₀₀	300	2218	14.79	27	2.41	4	0.069	0.050	0.050
G₁₀₀₁₀	10010	19891	3.97	13	17.32	109	0.251	0.00040	0.00023

DownLoad: CSV

表 1 SIR模型与8种节点重要性方法的排序结果及Kendall相关系数对比

Table 1. Comparison of SIR model rankings and Kendall’s tau coefficients with 8 node importance methods.

名称	SIR	DC	BC	OGC	KSGC	LGIC	EDGM	HVGC	MPC-GCN
排序结果	7	7	6	7	7	7	7	7	7
	1	9	9	1	9	1	1	9	1
	6	1	7	6	1	6	6	1	6
	2	6	5	2	6	2	2	6	2
	5	5	1	5	5	5	5	5	5
	4	2	2	9	2	9	9	2	4
	9	4	12	4	4	4	4	4	9
	3	12	11	3	3	3	3	3	3
	8	11	10	8	8	12	12	8	8
	11	10	8	12	12	11	11	12	10
	10	8	4	11	11	10	10	11	12
	12	3	3	10	10	8	8	10	11
τ		–0.606	–0.0303	0.667	0.333	0.576	0.576	0.333	0.939

DownLoad: CSV

表 3 8个网络幂律及泊松分布拟合检验结果

Table 3. Fitting test results of power law and Poisson distributions for 8 networks.

网络	δ	拟合优度检验	P值<0.05	λ	拟合优度检验	P值<0.05
Karate	0.55	0.29	否	4.59	6.28×10²	是
Jazz	0.27	0.15	是	27.70	2.89×10²³	是
NS	1.55	0.76	是	4.82	5.61×10¹⁴	是
USAir	0.95	0.77	是	12.81	1.22×10⁸	是
PB	1.07	0.85	是	27.36	1.07×10²⁴⁷	是
Router	1.77	0.89	是	2.49	2.31×10¹²⁵	是
G₃₀₀	0.79	0.073	否	14.79	14.51	否
G₁₀₀₁₀	0.24	0.054	否	4.04	29.6	否

DownLoad: CSV

[1]	Watts D J, Strogatz S H 1998 Nature 393 440 Google Scholar
[2]	Barabási A L, Albert R 1999 Science 286 509 Google Scholar
[3]	许怡岚, 郭唐仪, 唐坤, 张滢颖, 李林蔚 2024 兵工学报 45 552 Xu Y L, Guo T Y, Tang K, Zhang Y Y, Li L W 2024 Acta Armamentarii 45 552
[4]	孙利娜, 梁葆华, 陈志伟 2022 火力与指挥控制 47 119 Google Scholar Sun L N, Liang B H, Chen Z W 2022 Fire Control Command Control 47 119 Google Scholar
[5]	李晓龙, 韩益亮, 吴旭光, 张德阳 2018 燕山大学学报 42 444 Google Scholar Li X L, Han Y L, Wu X G, Zhang D Y 2018 J. YanShan Univ. 42 444 Google Scholar
[6]	罗浩, 闫光辉, 张萌, 包峻波, 李俊成, 刘婷, 杨波, 魏军 2020 计算机研究与发展 57 954 Google Scholar Luo H, Yan G H, Zhang M, Bao J B, Li J C, Liu T, Yang B, Wei J 2020 J. Comp. Res. Develop. 57 954 Google Scholar
[7]	Klemm K, Serrano M Á, Eguíluz V M, Miguel M S 2012 Scientific Reports 2 292 Google Scholar
[8]	王灵丽, 黄敏, 高亮 2020 交通信息安全 38 80 Wang L L, Huang M, Gao L 2020 J. Transp. Inform. Safety 38 80
[9]	Lai Q, Zhang H H 2022 Chin. Phys. B 31 068905 Google Scholar
[10]	Howell N 1985 Can. J. Sociol. 10 209 Google Scholar
[11]	Freeman L C 1977 Sociometry 40 35 Google Scholar
[12]	Sabidussi G 1966 Psychometrika 31 581 Google Scholar
[13]	Zareie A, Sheikhahmadi A, Khamforoosh K 2018 Expert Syst. Appl. 108 96 Google Scholar
[14]	Li H, Shang Q, Deng Y 2021 Chaos Soliton. Fract. 143 110456 Google Scholar
[15]	Zareie A, Sheikhahmadi A 2018 Expert Syst. Appl. 93 200 Google Scholar
[16]	Yu H, Liu Z, Li Y J 2013 Ieee 2013 5th International Conference on Measuring Technology and Mechatronics Automation (ICMTMA) Hong Kong, China, January 16–17, 2013 pp1292–1295
[17]	樊燕妮, 刘三阳, 白艺光 2020 数学的实践与认识 50 159 Fan Y N, Liu S Y, Bai Y G 2020 Math. Pract. Theory 50 159
[18]	Ma L L, Ma C, Zhang H F, Wang B H 2016 Physica A 451 205 Google Scholar
[19]	Jiang Y, Yang S Q, Yan Y W, Tong T C, Dai J Y 2022 Chin. Phys. B 31 058903 Google Scholar
[20]	Yang X, Xiao F Y 2021 Knowl. Based Syst. 227 107198 Google Scholar
[21]	Shang Q, Deng Y, Cheng K H 2021 Inform. Sci. 577 162 Google Scholar
[22]	Ai D, Liu X L, Kang W Z, Li L N, Lv S Q, Liu Y 2022 Chin. Phys. B 32 118902
[23]	Ullah A, Wang B, Sheng J F, Long J, Khan N, Sun Z J 2021 Expert Syst. Appl. 186 115778 Google Scholar
[24]	张宪立, 唐建新 2021 计算机工程 47 139 Zhang X L, Tang J X 2021 Comp. Eng. 47 139
[25]	阮逸润, 老松杨, 汤俊, 白亮, 郭延明 2022 物理学报 71 176401 Google Scholar Ruan Y R, Lao S Y, Tang J, Bai L, Guo Y M 2022 Acta Phys. Sin. 71 176401 Google Scholar
[26]	Xu K, Hu W 2018 Leskovec Proc 7th International Conference on Learning Representations (ICLR) LA, USA, May 6–9, 2018 pp1467–5463
[27]	曹璐, 丁苍峰, 马乐荣, 延照耀, 游浩, 洪安琪 2024 计算机科学与探索 Cao L, Ding C F, Ma L R, Yan Z Y, You H, Hong A Q 2024 Journal of Frontiers of Computer Science and Technology
[28]	Kipf, T N, Welling, M 2017 5th International Conference on Learning Representations Toulon, France, April 24–26, 2017
[29]	Maurya S K, Liu X, Murata T 2019 Proceedings of the 28th ACM International Conference on Information and Knowledge Management Beijing, China, November 3-7, 2019 pp2149–2152
[30]	Kumar M S, Liu X, Murata T 2021 ACM Trans. 15 1
[31]	Goel D, Shen H, Tian H, Guo M Y 2024 Expert Syst. Appl. 249 123636 Google Scholar
[32]	Qu H B, Song Y R, Li R Q, Li M 2023 Physica A 632 129339 Google Scholar
[33]	Ramachandran K, Rj T 2022 The 2022 Intelligent Computing for Sustainable Energy and Environment Hobart, Australia, February 18–20, 2022 pp1–10
[34]	Sun C C, Li C H, Lim X, Zheng T J, Meng F R, Rui X B, Wan Z X 2023 Artif. Intell. Rev. 56 2263 Google Scholar
[35]	Xiong C, Li W, Liu Y, Wang M H 2021 IEEE Signal Proc. Lett. 28 573 Google Scholar
[36]	Li Z, Xing Y Y, Huang J M, Wang H B, Gao J L, Yu G X 2021 Future Gener. Comp. Syst. 116 145 Google Scholar
[37]	Zhao G H, Jia P, Zhou A M, Zhang B 2020 Neurocomputing 414 18 Google Scholar
[38]	Liu C, Cao T T, Zhou L X 2022 Knowl. Based Syst. 251 109220 Google Scholar
[39]	Chen W J, Feng F L, Wang Q F, He X N, Song C G, Ling G H, Zhang Y D 2023 IEEE T. Knowl. Data En. 35 3500 Google Scholar
[40]	Li W J, Li T, Nikougoftar E 2024 Chaos Soliton. Fract. 187 115388 Google Scholar
[41]	Yu E Y, Wang Y P, Fu Y, Chen D B, Xie M 2020 Knowl. Based Syst. 198 105893 Google Scholar
[42]	Zhang L, Song H D, Aletras N, Lu H P 2022 Pattern Recogn. 128 108661 Google Scholar
[43]	Han B, Wei Y, Kang L, Wang Q, Yang Y 2022 Front. Phys. 9 2296
[44]	Yang X, Xiao F Y 2021 Knowl. Based Syst. 227 107198 Google Scholar
[45]	Ullah A, Wang B, Sheng J F, Long J, Khan N, Sun Z J 2021 Expert Syst. Appl. 186 115778 Google Scholar
[46]	Zhu S Q, Zhan J, Li X 2023 Sci. Rep. 13 16404 Google Scholar
[47]	Shang Q, Deng Y, Cheng K H 2021 Inform. Sciences 577 162 Google Scholar
[48]	杨松青, 蒋沅, 童天驰, 严玉为, 淦各升 2021 物理学报 70 216401 Google Scholar Yang S Q, Jiang Y, Tong T C, Yan Y W, Gan G S 2021 Acta Phys. Sin. 70 216401 Google Scholar

[1]	Ouyang Xin-Jian, Zhang Yan-Xing, Wang Zhi-Long, Zhang Feng, Chen Wei-Jia, Zhuang Yuan, Jie Xiao, Liu Lai-Jun, Wang Da-Wei. Modeling ferroelectric phase transitions with graph convolutional neural networks. Acta Physica Sinica, doi: 10.7498/aps.73.20240156
[2]	Wang Ting-Ting, Liang Zong-Wen, Zhang Ruo-Xi. Importance evaluation method of complex network nodes based on information entropy and iteration factor. Acta Physica Sinica, doi: 10.7498/aps.72.20221878
[3]	Ruan Yi-Run, Lao Song-Yang, Tang Jun, Bai Liang, Guo Yan-Ming. Node importance ranking method in complex network based on gravity method. Acta Physica Sinica, doi: 10.7498/aps.71.20220565
[4]	Huang Ying, Gu Chang-Gui, Yang Hui-Jie. Junk-neuron-deletion strategy for hyperparameter optimization of neural networks. Acta Physica Sinica, doi: 10.7498/aps.71.20220436
[5]	Zhu Qi, Xu Duo, Zhang Yuan-Jun, Li Yu-Juan, Wang Wen, Zhang Hai-Yan. Ultrasonic detection of white etching defect based on convolution neural network. Acta Physica Sinica, doi: 10.7498/aps.71.20221504
[6]	Liu Hui, Wang Bing-Jun, Lu Jun-An, Li Zeng-Yang. Node-set importance and optimization algorithm of nodes selection in complex networks based on pinning control. Acta Physica Sinica, doi: 10.7498/aps.70.20200872
[7]	Yang Song-Qing, Jiang Yuan, Tong Tian-Chi, Yan Yu-Wei, Gan Ge-Sheng. A method of evaluating importance of nodes in complex network based on Tsallis entropy. Acta Physica Sinica, doi: 10.7498/aps.70.20210979
[8]	Xu Qi-Wei, Wang Pei-Pei, Zeng Zhen-Jia, Huang Ze-Bin, Zhou Xin-Xing, Liu Jun-Min, Li Ying, Chen Shu-Qing, Fan Dian-Yuan. Extracting atmospheric turbulence phase using deep convolutional neural network. Acta Physica Sinica, doi: 10.7498/aps.69.20190982
[9]	Peng Xiang-Kai, Ji Jing-Wei, Li Lin, Ren Wei, Xiang Jing-Feng, Liu Kang-Kang, Cheng He-Nan, Zhang Zhen, Qu Qiu-Zhi, Li Tang, Liu Liang, Lü De-Sheng. Online learning method based on artificial neural network to optimize magnetic shielding characteristic parameters. Acta Physica Sinica, doi: 10.7498/aps.68.20190234
[10]	Huang Li-Ya, Tang Ping-Chuan, Huo You-Liang, Zheng Yi, Cheng Xie-Feng. Node importance based on the weighted K-order propagation number algorithm. Acta Physica Sinica, doi: 10.7498/aps.68.20190087
[11]	Yang Jian-Nan, Liu Jian-Guo, Guo Qiang. Node importance idenfication for temporal network based on inter-layer similarity. Acta Physica Sinica, doi: 10.7498/aps.67.20172255
[12]	Kong Jiang-Tao, Huang Jian, Gong Jian-Xing, Li Er-Yu. Evaluation methods of node importance in undirected weighted networks based on complex network dynamics models. Acta Physica Sinica, doi: 10.7498/aps.67.20172295
[13]	Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Chen Li-Dong. Node importance measurement based on neighborhood similarity in complex network. Acta Physica Sinica, doi: 10.7498/aps.66.038902
[14]	Wang Yu, Guo Jin-Li. Evaluation method of node importance in directed-weighted complex network based on multiple influence matrix. Acta Physica Sinica, doi: 10.7498/aps.66.050201
[15]	Liu Jian-Guo, Ren Zhuo-Ming, Guo Qiang, Wang Bing-Hong. Node importance ranking of complex networks. Acta Physica Sinica, doi: 10.7498/aps.62.178901
[16]	Ren Zhuo-Ming, Shao Feng, Liu Jian-Guo, Guo Qiang, Wang Bing-Hong. Node importance measurement based on the degree and clustering coefficient information. Acta Physica Sinica, doi: 10.7498/aps.62.128901
[17]	Yu Hui, Liu Zun, Li Yong-Jun. Key nodes in complex networks identified by multi-attribute decision-making method. Acta Physica Sinica, doi: 10.7498/aps.62.020204
[18]	Zhou Xuan, Zhang Feng-Ming, Li Ke-Wu, Hui Xiao-Bin, Wu Hu-Sheng. Finding vital node by node importance evaluation matrix in complex networks. Acta Physica Sinica, doi: 10.7498/aps.61.050201
[19]	Wang Yong-Sheng, Sun Jin, Wang Chang-Jin, Fan Hong-Da. Prediction of the chaotic time series from parameter-varying systems using artificial neural networks. Acta Physica Sinica, doi: 10.7498/aps.57.6120
[20]	PENG HWAN-WU. IMPORTANCE OF LIFE TIME CORRELATION EXPERIMENTS. Acta Physica Sinica, doi: 10.7498/aps.18.165

Metrics

Abstract views: 284
PDF Downloads: 6
Cited By: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

Search

Article

留言板