HOU Shiyu; LIU Ying; TANG Ming

doi:10.7498/aps.74.20250179

Abstract

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 of identifying influential spreaders have their limitations. Specifically speaking, 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; existing graph neural network-based methods neglect the dynamic characteristics of the propagation process itself. Researchers have pointed out that the spreading influence of nodes not only depends on their structural location, but is also significantly influenced by the dynamics of the spreading process itself. In this work, 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 of each node consisting of the embedding and degree of its local transmission tree, as well as its dynamics-sensitive centrality 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 in two synthetic networks and seven real-world networks show that the 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. In a wide range of infection rates, the proposed PDGNN can accurately identify influential spreaders. Despite the fact that the training set accounts for 30% of the total dataset, the PDGNN has the smallest inaccuracy in all nine studied networks.

Keywords:

Authors and contacts

Corresponding author: LIU Ying, shinningliu@163.com

Funds: Project supported by the Key Program of the National Natural Science Foundation of China (Grant No. 12231012), the International (Refional) Cooperation and Exchange Program of the National Natural Science Foundation of China (Grant No. 42461144209), and the Young Scientists Fund of the National Natural Science Foundation of China (Grant No. 61802321).

FullText HTML

References

[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
[31]
[32]
[33]
[34]
[35]
[36]
[37]
[38]
[39]
[40]

Cited By

DownLoad: Full-Size Img PowerPoint

网络	$ \left\|N\right\| $	$ \left\|E\right\| $	$ \langle k \rangle $	$ k_{{\mathrm{max}}} $	c	$ \beta_{\mathrm{c}} $
Musae_chameleon	2277	31371	27. 555	732	0. 481	0. 036
Router	5022	6258	2. 492	106	0. 012	0. 401
Blogs	3982	6803	3. 417	189	0. 284	0. 293
Jazz	198	2742	27. 69	78	0. 242	0. 036
Celegans	295	2244	15. 214	116	0. 189	0. 066
Ca-netscience	379	914	4. 823	34	0. 741	0. 207
CollegeMsg	1893	13835	14. 62	255	0. 109	0. 068
SCF1	1000	2991	5. 982	99	0. 032	0. 167
SCF2	2000	8997	8. 997	43	0. 009	0. 111

DownLoad: CSV

Networks	SVM		CGNN		RF		PDGNN
Networks	Recall	PR_AUC	Recall	PR_AUC	Recall	PR_AUC	Recall	PR_AUC
Musae_chameleon	0 3603	0.3603	0	0.378	0	0.2667	0.9524	0.3991
Router	0.4048	0.7776	0.3864	0.603	0.4762	0.7714	1	0.8761
Blogs	0.5897	0.8095	0.4651	0.6582	0.3333	0.7134	1	0.9089
Jazz	0	1	0	0.1843	0.5	1	1	1
Celegans	0.6	0.75	0	0	0.2	0.3333	1	0.8889
Ca-netscience	0.1667	0.7452	0	0.1607	0	0.6389	1	1
CollegeMsg	0.1579	0.5673	0.125	0.2968	0.0526	0.6965	1	0.6431
SCF1	0.2	0.5741	0.6	0.7783	0.2	0.4792	1	0.9709
SCF2	0.4091	0.8158	0.2268	0.7653	0.1818	0.8002	1	0.8837

DownLoad: CSV

[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
[31]
[32]
[33]
[34]
[35]
[36]
[37]
[38]
[39]
[40]

[1]	XIE Hanchen, WU Minggong, WEN Xiangxi, LI Dongdong, ZHANG Mingyu. A Method for Identifying Key Nodes in Complex Networks Based on Weighted Cycle Ratio. Acta Physica Sinica, 2025, 74(14): . doi: 10.7498/aps.74.20250338
[2]	Li Jiang, Liu Ying, Wang Wei, Zhou Tao. Identifying influential nodes in spreading process in higher-order networks. Acta Physica Sinica, 2024, 73(4): 048901. doi: 10.7498/aps.73.20231416
[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, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
[4]	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, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
[5]	Su Zhen, Gao Chao, Li Xiang-Hua. Analysis of the effect of node centrality on diffusion mode in complex networks. Acta Physica Sinica, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
[6]	Han Zhong-Ming, Chen Yan, Li Meng-Qi, Liu Wen, Yang Wei-Jie. An efficient node influence metric based on triangle in complex networks. Acta Physica Sinica, 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
[7]	Han Zhong-Ming, Wu Yang, Tan Xu-Sheng, Duan Da-Gao, Yang Wei-Jie. Ranking key nodes in complex networks by considering structural holes. Acta Physica Sinica, 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
[8]	Liu Wei-Yan, Liu Bin. Congestion control in complex network based on local routing strategy. Acta Physica Sinica, 2014, 63(24): 248901. doi: 10.7498/aps.63.248901
[9]	Yu Hui, Liu Zun, Li Yong-Jun. Key nodes in complex networks identified by multi-attribute decision-making method. Acta Physica Sinica, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
[10]	Hu Qing-Cheng, Yin Yan-Shen, Ma Peng-Fei, Gao Yang, Zhang Yong, Xing Chun-Xiao. A new approach to identify influential spreaders in complex networks. Acta Physica Sinica, 2013, 62(14): 140101. doi: 10.7498/aps.62.140101
[11]	Yuan Wei-Guo, Liu Yun, Cheng Jun-Jun, Xiong Fei. Empirical analysis of microblog centrality and spread influence based on Bi-directional connection. Acta Physica Sinica, 2013, 62(3): 038901. doi: 10.7498/aps.62.038901
[12]	Liu Jin-Liang. Research on synchronization of complex networks with random nodes. Acta Physica Sinica, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
[13]	Ren Zhuo-Ming, Liu Jian-Guo, Shao Feng, Hu Zhao-Long, Guo Qiang. Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks. Acta Physica Sinica, 2013, 62(10): 108902. doi: 10.7498/aps.62.108902
[14]	Zhou Xuan, Zhang Feng-Ming, Zhou Wei-Ping, Zou Wei, Yang Fan. Evaluating complex network functional robustness by node efficiency. Acta Physica Sinica, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
[15]	LÜ Ling, Liu Shuang, Zhang Xin, Zhu Jia-Bo, Shen Na, Shang Jin-Yu. Spatiotemporal chaos anti-synchronization of a complex network with different nodes. Acta Physica Sinica, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
[16]	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, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
[17]	Cui Ai-Xiang, Fu Yan, Shang Ming-Sheng, Chen Duan-Bing, Zhou Tao. Emergence of local structures in complex network:common neighborhood drives the network evolution. Acta Physica Sinica, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
[18]	Lü Ling, Zhang Chao. Chaos synchronization of a complex network with different nodes. Acta Physica Sinica, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
[19]	Xu Dan, Li Xiang, Wang Xiao-Fan. An investigation on local area control of virus spreading in complex networks. Acta Physica Sinica, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
[20]	Li Ji, Wang Bing-Hong, Jiang Pin-Qun, Zhou Tao, Wang Wen-Xu. Growing complex network model with acceleratingly increasing number of nodes. Acta Physica Sinica, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051

Catalog

Vol. 74, Issue 10 - 2025-05-20

Metrics

Abstract views: 469
PDF Downloads: 23
Cited By: 0

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

Search

Article

留言板

Abstract

Authors and contacts

Corresponding author: LIU Ying, shinningliu@163.com

FullText HTML

References

Cited By

Catalog

Metrics

Authors

Referees

About Journal

About

Search

Article

留言板

Abstract

Authors and contacts

Corresponding author: LIU Ying, shinningliu@163.com

FullText HTML

References

Cited By

Catalog

Metrics

Publishing process

Authors

Referees

About Journal

About