-
识别复杂网络中的传播关键节点在加速信息扩散、抑制病毒或谣言的传播等应用中至关重要.现有识别网络传播中关键节点的方法各有局限:复杂网络中心性方法仅从局域或者全局拓扑结构预测节点影响力;传统机器学习和深度学习方法不适用于图结构数据;已有基于图神经网络的方法忽视了传播过程自身的动力学特性.鉴于此,本文提出一种融合传播过程动力学特征与节点局域结构的传播动态图神经网络(Propagation Dynamics Graph Neural Network,PDGNN),用于识别复杂网络传播中的关键节点.通过结合易感-感染-恢复传播模型,提取节点传播过程中的动态感染特征,构建高维特征向量并设计优化的损失函数,以实现对复杂网络传播关键节点的准确识别.在两个合成网络和七个真实网络上的实验结果表明,PDGNN在复杂网络传播关键节点识别准确性上优于经典的中心性方法、基于传统机器学习和深度学习的方法以及现有的基于图神经网络的方法.Identifying the most influential nodes in the spreading process in complex networks is crucial in many applications, such as accelerating the diffusion of information and suppressing the spread of viruses or rumors. Existing methods for identifying influential spreaders have their limitations: classical network centrality methods rely solely on local or global topology to predict node influence; traditional machine learning and deep learning methods are not suitable for graph-structured data; and existing graph neural network-based methods neglect the dynamic characteristics of the propagation process itself. However, researches have pointed out that a node’s spreading influence does not only depend on its structural location, but is also significantly influenced by the dynamics of the spreading process itself. In this paper, we propose a Propagation Dynamics Graph Neural Network (PDGNN) that integrates the dynamic features of the propagation process and the structural features of nodes to identify influential nodes. Specifically speaking, based on the Susceptible-Infected-Recovered (SIR) propagation model, the dynamic infection features and potential infection capacity of nodes are extracted from the epidemic spreading process. Then a high-dimensional feature vector consisting of the embedding and the degree of the local transmission tree, and the dynamic sensitivity centrality of each node is constructed and used as the input to the graph neural network. To deal with the problem of imbalanced numbers between critical nodes and non-critical nodes in training the model and optimizing the output, an optimized loss function is designed, which combines Focal Loss with Mean Squared Error. Experimental results on two synthetic networks and seven real-world networks show that PDGNN outperforms classical centrality methods, traditional machine learning and deep learning-based methods, and existing graph neural network-based methods in identifying influential nodes in the spreading process in complex networks. The performance of PDGNN is robust when the infection rate and the size of the training set change. Under a wide range of infection rates, the proposed PDGNN can accurately identify influential spreaders. Even when the training set is 30% of the total dataset, the imprecision of PDGNN is small in all nine studied networks.
-
Keywords:
- complex networks /
- influential nodes /
- graph neural network /
- local transmission tree
-
[1] Wang X F, Li X, Chen G R 2012 Network Science:An Introduction (Beijing:Higher Education Press), pp 7-14(in Chinese)[汪小帆,李翔,陈关荣2012网络科学导论(北京:高等教育出版社)第7-14页]
[2] Nielsen B F, Simonsen L, Sneppen K 2021 Phys. Rev. Lett. 126118301
[3] Song K, Park H, Lee J, Kim A, Jung J 2023 Sci. Rep. 1311469
[4] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6888
[5] Kim S, Jiang J Y, Han J, Wang W 2023 In Proceedings of the 17th International AAAI Conference on Web and Social Media, Limassol, Cyprus, June 5-8, 2023, pp 482-493
[6] Lü L, Chen D, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 6501
[7] Pei S, Morone F, Makse H A 2018 Complex Spreading Phenomena in Social Systems:Influence and Contagion in Real-World Social Networks (Berlin:Springer)125
[8] Liu J, Li X, Dong J 2021 Sci. China Tech. Sci. 64451
[9] Fan T, Lü L, Shi D, Zhou T 2021 Commun. Phys. 4272
[10] Liu Y, Zeng Q, Pan L, Tang M 2023 IEEE Trans. Netw. Sci. Eng. 102201
[11] Zhao G, Jia P, Huang C, Zhou A, Fang Y 2020 IEEE Access 865462
[12] Asgharian Rezaei A, Munoz J, Jalili M, Khayyam H 2023 Expert Syst. Appl. 214119086
[13] Yu E Y, Wang Y P, Fu Y, Chen D B, Xie M 2020 Knowledge-Based Syst. 198105893
[14] Ou Y, Guo Q, Xing J L, Liu J G 2022 Expert. Syst. Appl. 203117515
[15] Ahmad W, Wang B, Chen S 2024 Appl. Intell. 543260
[16] Zhao G, Jia P, Zhou A, Zhang B 2020 Neurocomputing 41418
[17] Rashid Y, Bhat J I 2024 Knowledge-Based Syst. 283111163
[18] Xiong Y, Hu Z, Su C, Cai S M, Zhou T 2024 Appl. Soft Comput. 111895
[19] Munikoti S, Das L, Natarajan B 2021 In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, Melbourne, Australia, October 17-20, 2021, pp 3245-3251
[20] Xhonneux L P, Qu M, Tang J 2020 In Proceedings of the 37th International Conference on Machine Learning, Virtual Event, July 13-18, 2020, pp 10432-10441
[21] Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 863200
[22] Wang W, Tang M, Zhang H F, Gao H, Do Y, Liu Z H 2014 Phys. Rev. E 90042803
[23] Li J, Liu Y, Wang W, Zhou T 2024 Acta Phys. Sin. 73314
[24] Šikić M, Lančić A, Antulov-Fantulin N,Štefančić H 2013 Eur. Phys. J. B 861
[25] Lawyer G 2015 Sci. Rep. 58665
[26] Liu Y, Tang M, Zhou T, Do Y 2016 Phys. A 452289
[27] Narayanan A, Chandramohan M, Venkatesan R, Chen L H, Liu Y, Jaiswal S 2017 arXiv:1707.05005[cs.LG]
[28] Liu J G, Lin J H, Guo Q, Zhou T 2016 Sci. Rep. 621380
[29] Wu Y, Hu Y, Yin S, Cai B, Tang X, Li X 2024 Knowledge-Based Syst. 301112235
[30] Ross T Y, Dollár G 2017 In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Venice, Italy, October 22-29, 2017, pp 2980-2988
[31] Rozemberczki B, Allen C, Sarkar R 2021 J. Complex Netw. 9 cnab014
[32] Spring N, Mahajan R, Wetherall D, Anderson T 2004 IEEE/ACM Trans. Netw. 122
[33] Adamic L A, Glance N 2005 In Proceedings of the 3rd International Workshop on Link Discovery, Chicago Illinois, USA, August 21-25, 2005, pp 36-43
[34] Gleiser P M, Danon L 2003 Adv. Complex. Syst. 6565
[35] Watts D J, Strogatz S H 1998 Nature 393440
[36] Rossi R, Ahmed N 2015 In Proceedings of the 29th AAAI Conference on Artificial Intelligence, Austin, Texas, USA, January 25-30, 2015, pp 4292-4293
[37] Panzarasa P, Opsahl T, Carley K M 2009 J. Am. Soc. Inf. Sci. Technol. 60911
[38] Castellano C, Pastor-Satorras R 2010 Phys. Rev. Lett. 105218701
[39] Li R, Wang W, Shu P, Yang H, Pan L, Cui A, Tang M 2016 Complex Syst. Complex Sci. 131
[40] Morone F, Makse H A 2015 Nature 52465
计量
- 文章访问数: 86
- PDF下载量: 4
- 被引次数: 0
下载:
