-
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.
[1] Watts D J, Strogatz S H 1998 Nature 393 440Google Scholar
[2] Barabási A L, Albert R 1999 Science 286 509Google Scholar
[3] 许怡岚, 郭唐仪, 唐坤, 张滢颖, 李林蔚 2024 兵工学报 45 552Google Scholar
Xu Y L, Guo T Y, Tang K, Zhang Y Y, Li L W 2024 Acta Armamentarii 45 552Google Scholar
[4] 孙利娜, 梁葆华, 陈志伟 2022 火力与指挥控制 47 119Google Scholar
Sun L N, Liang B H, Chen Z W 2022 Fire Control Command Control 47 119Google Scholar
[5] 李晓龙, 韩益亮, 吴旭光, 张德阳 2018 燕山大学学报 42 444Google Scholar
Li X L, Han Y L, Wu X G, Zhang D Y 2018 J. YanShan Univ. 42 444Google Scholar
[6] 罗浩, 闫光辉, 张萌, 包峻波, 李俊成, 刘婷, 杨波, 魏军 2020 计算机研究与发展 57 954Google 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 954Google Scholar
[7] Klemm K, Serrano M Á, Eguíluz V M, Miguel M S 2012 Scientific Reports 2 292Google Scholar
[8] 王灵丽, 黄敏, 高亮 2020 交通信息与安全 38 80Google Scholar
Wang L L, Huang M, Gao L 2020 J. Transp. Inform. Safety 38 80Google Scholar
[9] Lai Q, Zhang H H 2022 Chin. Phys. B 31 068905Google Scholar
[10] Howell N 1985 Can. J. Sociol. 10 209Google Scholar
[11] Freeman L C 1977 Sociometry 40 35Google Scholar
[12] Sabidussi G 1966 Psychometrika 31 581Google Scholar
[13] Zareie A, Sheikhahmadi A, Khamforoosh K 2018 Expert Syst. Appl. 108 96Google Scholar
[14] Li H, Shang Q, Deng Y 2021 Chaos Soliton. Fract. 143 110456Google Scholar
[15] Zareie A, Sheikhahmadi A 2018 Expert Syst. Appl. 93 200Google 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 205Google Scholar
[19] Jiang Y, Yang S Q, Yan Y W, Tong T C, Dai J Y 2022 Chin. Phys. B 31 058903Google Scholar
[20] Yang X, Xiao F Y 2021 Knowl. Based Syst. 227 107198Google Scholar
[21] Shang Q, Deng Y, Cheng K H 2021 Inform. Sci. 577 162Google Scholar
[22] Ai D, Liu X L, Kang W Z, Li L N, Lü S Q, Liu Y 2023 Chin. Phys. B 32 118902Google Scholar
[23] Ullah A, Wang B, Sheng J F, Long J, Khan N, Sun Z J 2021 Expert Syst. Appl. 186 115778Google Scholar
[24] 张宪立, 唐建新 2021 计算机工程 47 139Google Scholar
Zhang X L, Tang J X 2021 Comp. Eng. 47 139Google Scholar
[25] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明 2022 71 176401Google Scholar
Ruan Y R, Lao S Y, Tang J, Bai L, Guo Y M 2022 Acta Phys. Sin. 71 176401Google Scholar
[26] Xu K, Hu W, Leskovec J, Jegelka S 2018 Leskovec Proc 7th International Conference on Learning Representations (ICLR) LA, USA, May 6–9, 2019 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 2021 ACM Trans Knowl Discov Data. 15 1Google Scholar
[30] Qin P, Chen W F, Zhang M, Li D F, Feng G C 2024 IEEE Access 12 71956Google Scholar
[31] Goel D, Shen H, Tian H, Guo M Y 2024 Expert Syst. Appl. 249 123636Google Scholar
[32] Qu H B, Song Y R, Li R Q, Li M 2023 Physica A 632 129339Google Scholar
[33] Ramachandran K, Rj T 2022 ICSEE 2022 Total Centrality: A New Centrality Measure Using Graph Neural Network Hobart, Australia, February 18–20, 2022
[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 2263Google Scholar
[35] Xiong C, Li W, Liu Y, Wang M H 2021 IEEE Signal Proc. Lett. 28 573Google 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 145Google Scholar
[37] Zhao G H, Jia P, Zhou A M, Zhang B 2020 Neurocomputing 414 18Google Scholar
[38] Liu C, Cao T T, Zhou L X 2022 Knowl. Based Syst. 251 109220Google 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 3500Google Scholar
[40] Li W J, Li T, Nikougoftar E 2024 Chaos Soliton. Fract. 187 115388Google Scholar
[41] Yu E Y, Wang Y P, Fu Y, Chen D B, Xie M 2020 Knowl. Based Syst. 198 105893Google Scholar
[42] Zhang L, Song H D, Aletras N, Lu H P 2022 Pattern Recogn. 128 108661Google Scholar
[43] Han B, Wei Y, Kang L, Wang Q, Yang Y 2022 Front. Phys. 9 2296Google Scholar
[44] Zhu S Q, Zhan J, Li X 2023 Sci. Rep. 13 16404Google Scholar
[45] 杨松青, 蒋沅, 童天驰, 严玉为, 淦各升 2021 70 216401Google Scholar
Yang S Q, Jiang Y, Tong T C, Yan Y W, Gan G S 2021 Acta Phys. Sin. 70 216401Google Scholar
-
图 5 以前5%为初始感染节点的8种节点排序性方法在8个网络上的传染情况对比 (a) Karate; (b) Jazz; (c) NS; (d) USAir; (e) PB; (f) Route; (g) G300; (h) G10010
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) G300; (h) G10010.
表 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 G300 300 2218 14.79 27 2.41 4 0.069 0.050 0.050 G10010 10010 19891 3.97 13 17.32 109 0.251 0.00040 0.00023 表 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 表 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×102 是 Jazz 0.27 0.15 是 27.70 2.89×1023 是 NS 1.55 0.76 是 4.82 5.61×1014 是 USAir 0.95 0.77 是 12.81 1.22×108 是 PB 1.07 0.85 是 27.36 1.07×10247 是 Router 1.77 0.89 是 2.49 2.31×10125 是 G300 0.79 0.073 否 14.79 14.51 否 G10010 0.24 0.054 否 4.04 29.6 否 -
[1] Watts D J, Strogatz S H 1998 Nature 393 440Google Scholar
[2] Barabási A L, Albert R 1999 Science 286 509Google Scholar
[3] 许怡岚, 郭唐仪, 唐坤, 张滢颖, 李林蔚 2024 兵工学报 45 552Google Scholar
Xu Y L, Guo T Y, Tang K, Zhang Y Y, Li L W 2024 Acta Armamentarii 45 552Google Scholar
[4] 孙利娜, 梁葆华, 陈志伟 2022 火力与指挥控制 47 119Google Scholar
Sun L N, Liang B H, Chen Z W 2022 Fire Control Command Control 47 119Google Scholar
[5] 李晓龙, 韩益亮, 吴旭光, 张德阳 2018 燕山大学学报 42 444Google Scholar
Li X L, Han Y L, Wu X G, Zhang D Y 2018 J. YanShan Univ. 42 444Google Scholar
[6] 罗浩, 闫光辉, 张萌, 包峻波, 李俊成, 刘婷, 杨波, 魏军 2020 计算机研究与发展 57 954Google 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 954Google Scholar
[7] Klemm K, Serrano M Á, Eguíluz V M, Miguel M S 2012 Scientific Reports 2 292Google Scholar
[8] 王灵丽, 黄敏, 高亮 2020 交通信息与安全 38 80Google Scholar
Wang L L, Huang M, Gao L 2020 J. Transp. Inform. Safety 38 80Google Scholar
[9] Lai Q, Zhang H H 2022 Chin. Phys. B 31 068905Google Scholar
[10] Howell N 1985 Can. J. Sociol. 10 209Google Scholar
[11] Freeman L C 1977 Sociometry 40 35Google Scholar
[12] Sabidussi G 1966 Psychometrika 31 581Google Scholar
[13] Zareie A, Sheikhahmadi A, Khamforoosh K 2018 Expert Syst. Appl. 108 96Google Scholar
[14] Li H, Shang Q, Deng Y 2021 Chaos Soliton. Fract. 143 110456Google Scholar
[15] Zareie A, Sheikhahmadi A 2018 Expert Syst. Appl. 93 200Google 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 205Google Scholar
[19] Jiang Y, Yang S Q, Yan Y W, Tong T C, Dai J Y 2022 Chin. Phys. B 31 058903Google Scholar
[20] Yang X, Xiao F Y 2021 Knowl. Based Syst. 227 107198Google Scholar
[21] Shang Q, Deng Y, Cheng K H 2021 Inform. Sci. 577 162Google Scholar
[22] Ai D, Liu X L, Kang W Z, Li L N, Lü S Q, Liu Y 2023 Chin. Phys. B 32 118902Google Scholar
[23] Ullah A, Wang B, Sheng J F, Long J, Khan N, Sun Z J 2021 Expert Syst. Appl. 186 115778Google Scholar
[24] 张宪立, 唐建新 2021 计算机工程 47 139Google Scholar
Zhang X L, Tang J X 2021 Comp. Eng. 47 139Google Scholar
[25] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明 2022 71 176401Google Scholar
Ruan Y R, Lao S Y, Tang J, Bai L, Guo Y M 2022 Acta Phys. Sin. 71 176401Google Scholar
[26] Xu K, Hu W, Leskovec J, Jegelka S 2018 Leskovec Proc 7th International Conference on Learning Representations (ICLR) LA, USA, May 6–9, 2019 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 2021 ACM Trans Knowl Discov Data. 15 1Google Scholar
[30] Qin P, Chen W F, Zhang M, Li D F, Feng G C 2024 IEEE Access 12 71956Google Scholar
[31] Goel D, Shen H, Tian H, Guo M Y 2024 Expert Syst. Appl. 249 123636Google Scholar
[32] Qu H B, Song Y R, Li R Q, Li M 2023 Physica A 632 129339Google Scholar
[33] Ramachandran K, Rj T 2022 ICSEE 2022 Total Centrality: A New Centrality Measure Using Graph Neural Network Hobart, Australia, February 18–20, 2022
[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 2263Google Scholar
[35] Xiong C, Li W, Liu Y, Wang M H 2021 IEEE Signal Proc. Lett. 28 573Google 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 145Google Scholar
[37] Zhao G H, Jia P, Zhou A M, Zhang B 2020 Neurocomputing 414 18Google Scholar
[38] Liu C, Cao T T, Zhou L X 2022 Knowl. Based Syst. 251 109220Google 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 3500Google Scholar
[40] Li W J, Li T, Nikougoftar E 2024 Chaos Soliton. Fract. 187 115388Google Scholar
[41] Yu E Y, Wang Y P, Fu Y, Chen D B, Xie M 2020 Knowl. Based Syst. 198 105893Google Scholar
[42] Zhang L, Song H D, Aletras N, Lu H P 2022 Pattern Recogn. 128 108661Google Scholar
[43] Han B, Wei Y, Kang L, Wang Q, Yang Y 2022 Front. Phys. 9 2296Google Scholar
[44] Zhu S Q, Zhan J, Li X 2023 Sci. Rep. 13 16404Google Scholar
[45] 杨松青, 蒋沅, 童天驰, 严玉为, 淦各升 2021 70 216401Google Scholar
Yang S Q, Jiang Y, Tong T C, Yan Y W, Gan G S 2021 Acta Phys. Sin. 70 216401Google Scholar
Catalog
Metrics
- Abstract views: 351
- PDF Downloads: 9
- Cited By: 0