-
针对复杂网络中关键节点的识别、评估及排序问题, 受物理系统中不同节点间信息的多维度、多层次相互影响过程的启发, 提出了一种基于图卷积神经网络的多维参数的节点重要性评估方法. 该方法结合了卷积神经网络自动学习的特性, 综合考虑节点的内在特性、与邻近节点的交互关系以及其在整个网络中的功能角色, 构建了一种新颖的关键节点识别框架, 即多维参数控制图卷积网络(multi-parameter control graph convolutional networks, MPC-GCN). 通过卷积神经网络对节点及其邻居特征的逐层聚合, 自动提取并综合节点的局部特性、全局特性及位置特性, 实现对节点重要性的多维度评估, 同时引入灵活的参数调整机制, 允许调整不同维度信息对评估结果的影响权重, 以适应不同结构网络的需求. 为验证该方法的有效性, 在随机生成的小型网络上验证了参数对模型的作用; 并在8个大型网络上利用SIR模型进行仿真实验, 以M(R)值、Kendall相关系数、被传染节点占比及最大连通子图相对大小作为评价标准. 结果表明, MPC-GCN方法在单调性、准确性、适用性及鲁棒性上都优于其他相关方法, 能够显著区分不同节点的重要程度. 该方法有效克服了现有方法在评估角度和适应能力上的局限性, 提高了评估的全面性和适用性.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 440
Google Scholar
[2] Barabási A L, Albert R 1999 Science 286 509
Google Scholar
[3] 许怡岚, 郭唐仪, 唐坤, 张滢颖, 李林蔚 2024 兵工学报 45 552
Google Scholar
Xu Y L, Guo T Y, Tang K, Zhang Y Y, Li L W 2024 Acta Armamentarii 45 552
Google Scholar
[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
Google Scholar
Wang L L, Huang M, Gao L 2020 J. Transp. Inform. Safety 38 80
Google Scholar
[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, Lü S Q, Liu Y 2023 Chin. Phys. B 32 118902
Google Scholar
[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
Google Scholar
Zhang X L, Tang J X 2021 Comp. Eng. 47 139
Google Scholar
[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, 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 1
Google Scholar
[30] Qin P, Chen W F, Zhang M, Li D F, Feng G C 2024 IEEE Access 12 71956
Google Scholar
[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 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 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
Google Scholar
[44] Zhu S Q, Zhan J, Li X 2023 Sci. Rep. 13 16404
Google Scholar
[45] 杨松青, 蒋沅, 童天驰, 严玉为, 淦各升 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
-
图 2 随机森林模型评估MPC-GCN模型效果 (a)回归散点图; (b)特征重要性图
Fig. 2. Random forest model evaluation of MPC-GCN model performance: (a) Regression scatter plot; (b) feature importance plot.
图 4 8种节点排序性方法在8个网络上的Kendall相关系数对比 (a) Karate; (b) Jazz; (c) NS; (d) USAir; (e) PB; (f) Route; (g) G300; (h) G10010
Fig. 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) G300; (h) G10010.
图 6 网络最大连通子图随移除节点比例变化情况 (a) Karate; (b) Jazz; (c) NS; (d) USAir; (e) PB; (f) Route; (g) G300; (h) G10010
Fig. 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) G300; (h) G10010.
图 3 不同评估方法在8个网络上的单调性指标M
Fig. 3. Monotonicity metrics M of various assessment methods on 8 networks.
图 5 以前5%为初始感染节点的8种节点排序性方法在8个网络上的传染情况对比 (a) Karate; (b) Jazz; (c) NS; (d) USAir; (e) PB; (f) Route; (g) G300; (h) G10010
Fig. 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 
下载: 导出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
下载: 导出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×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 否
下载: 导出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
Google Scholar
Xu Y L, Guo T Y, Tang K, Zhang Y Y, Li L W 2024 Acta Armamentarii 45 552
Google Scholar
[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
Google Scholar
Wang L L, Huang M, Gao L 2020 J. Transp. Inform. Safety 38 80
Google Scholar
[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, Lü S Q, Liu Y 2023 Chin. Phys. B 32 118902
Google Scholar
[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
Google Scholar
Zhang X L, Tang J X 2021 Comp. Eng. 47 139
Google Scholar
[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, 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 1
Google Scholar
[30] Qin P, Chen W F, Zhang M, Li D F, Feng G C 2024 IEEE Access 12 71956
Google Scholar
[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 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 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
Google Scholar
[44] Zhu S Q, Zhan J, Li X 2023 Sci. Rep. 13 16404
Google Scholar
[45] 杨松青, 蒋沅, 童天驰, 严玉为, 淦各升 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
下载:
计量
- 文章访问数: 340
- PDF下载量: 9
- 被引次数: 0
