-
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
Metrics
- Abstract views: 53
- PDF Downloads: 2
- Cited By: 0
下载:
