Identifying multiple influential spreaders in complex networks based on spectral graph theory

doi:10.1088/1674-1056/acac0b

中国物理B ›› 2023, Vol. 32 ›› Issue (9): 98904-098904.doi: 10.1088/1674-1056/acac0b

Identifying multiple influential spreaders in complex networks based on spectral graph theory

Dong-Xu Cui(崔东旭), Jia-Lin He(何嘉林)^†, Zi-Fei Xiao(肖子飞), and Wei-Ping Ren(任卫平)

School of Computer Science and Engineering, China West Normal University, Nanchong 637009, China

收稿日期:2022-09-13 修回日期:2022-12-11 接受日期:2022-12-16 发布日期:2023-08-28
通讯作者: Jia-Lin He E-mail:hejialin32@126.com
基金资助:
Project supported by the National Natural Science Foundation of China (Grant No. 62176217), the Program from the Sichuan Provincial Science and Technology, China (Grant No. 2018RZ0081), and the Fundamental Research Funds of China West Normal University (Grant No. 17E063).

Identifying multiple influential spreaders in complex networks based on spectral graph theory

Dong-Xu Cui(崔东旭), Jia-Lin He(何嘉林)^†, Zi-Fei Xiao(肖子飞), and Wei-Ping Ren(任卫平)

School of Computer Science and Engineering, China West Normal University, Nanchong 637009, China

Received:2022-09-13 Revised:2022-12-11 Accepted:2022-12-16 Published:2023-08-28
Contact: Jia-Lin He E-mail:hejialin32@126.com
Supported by:
Project supported by the National Natural Science Foundation of China (Grant No. 62176217), the Program from the Sichuan Provincial Science and Technology, China (Grant No. 2018RZ0081), and the Fundamental Research Funds of China West Normal University (Grant No. 17E063).

摘要/Abstract

摘要： One of the hot research topics in propagation dynamics is identifying a set of critical nodes that can influence maximization in a complex network. The importance and dispersion of critical nodes among them are both vital factors that can influence maximization. We therefore propose a multiple influential spreaders identification algorithm based on spectral graph theory. This algorithm first quantifies the role played by the local structure of nodes in the propagation process, then classifies the nodes based on the eigenvectors of the Laplace matrix, and finally selects a set of critical nodes by the constraint that nodes in the same class are not adjacent to each other while different classes of nodes can be adjacent to each other. Experimental results on real and synthetic networks show that our algorithm outperforms the state-of-the-art and classical algorithms in the SIR model.

关键词: spectral graph theory, Laplace matrix, influence maximization, multiple influential spreaders

Abstract: One of the hot research topics in propagation dynamics is identifying a set of critical nodes that can influence maximization in a complex network. The importance and dispersion of critical nodes among them are both vital factors that can influence maximization. We therefore propose a multiple influential spreaders identification algorithm based on spectral graph theory. This algorithm first quantifies the role played by the local structure of nodes in the propagation process, then classifies the nodes based on the eigenvectors of the Laplace matrix, and finally selects a set of critical nodes by the constraint that nodes in the same class are not adjacent to each other while different classes of nodes can be adjacent to each other. Experimental results on real and synthetic networks show that our algorithm outperforms the state-of-the-art and classical algorithms in the SIR model.

Key words: spectral graph theory, Laplace matrix, influence maximization, multiple influential spreaders

中图分类号: (Structures and organization in complex systems)

89.75.Fb

Dong-Xu Cui(崔东旭), Jia-Lin He(何嘉林), Zi-Fei Xiao(肖子飞), and Wei-Ping Ren(任卫平). Identifying multiple influential spreaders in complex networks based on spectral graph theory[J]. 中国物理B, 2023, 32(9): 98904-098904.

参考文献

[1] Domingos P and Richardson M 2001 Mining the Network Value of Customers (San Francisco), p. 57
[2] Hébert-Dufresne L, Allard A, Young J and Dubé L J 2013 Sci. Rep. 3 2171
[3] Carrington P, John S and Stan W 2005 Models and Methods in Social Network Analysis (Cambridge: Cambridge University Press)
[4] Richardson M and Domingos P 2002 Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, July, 2002, Edmonton, Alberta, Canada, p. 61
[5] Kitsak Maksim, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E and Makse H A 2010 Nat. Phys. 6 888
[6] Lü L, Chen D, Ren X, Zhang Q, Zhang Y and Zhou T 2016 Phys. Rep. 650 1
[7] Morone F and Makse H A 2015 Nature 524 65
[8] Pei S, Wang J, Morone F and Makse H A 2019 Complex Networks 8 2051
[9] Costa G S and Ferreira S C 2020 Phys. Rev. 101 022311
[10] Bovet A and Makse H A 2019 Nat. Commun. 10 1
[11] Bonacich P 1972 Math. Soc. 2 113
[12] Chen D, Lü L, Shang M, Zhang Y and Zhou T 2012 Physica A 391 1777
[13] Freeman L C 1978 Social Networks 1 215
[14] Sabidussi Gert 1966 Psychometrika 31 581
[15] Dangalchev C 2006 Physica A 365 556
[16] Chen D, Gao H, Lü L and Zhou T 2013 PLoS ONE 8 1
[17] Brin S and Page L 1998 Computer Networks and ISDN Systems 30 107
[18] Lü L, Zhang Y, Yeung C H and Zhou T 2011 PLoS ONE 6 1
[19] Fan T, Lü L, Shi D and Zhou T 2021 Commun. Phys. 4 272
[20] Colizza V, Flammini A, Serrano M A and Vespignani A 2006 Nat. Phys. 2 110
[21] Kempe D, Kleinberg J and Tardos É 2003 Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August, 2003, Washington, DC, USA, p. 137
[22] Chen W, Wang Y and Yang S 2009 Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, June, 2009, Paris, France, p. 199
[23] Zhao X, Huang B, Tang M, Zhang H and Chen D 2014 Europhys. Lett. 108 68005
[24] Guo L, Lin J, Guo Q and Liu J 2016 Phys. Lett. A 380 837
[25] Morone F and Makse H 2015 Nature 524 65
[26] Zhang J, Chen D, Dong Q and Zhao Z 2016 Sci. Rep. 6 1
[27] Sun H, Chen D, He J and Ch'ng E 2019 Physics A 519 303
[28] Fan C, Zeng L, Sun Y and Liu Y 2020 Nat. Mach. Intell. 2 317
[29] Lancichinetti A, Fortunato S and Radicchi F 2009 Phys. Rev. E 80 1
[30] Hethcote H W 2000 SIAM Rev. 42 599
[31] Yang R, Wang B, Ren J, Bai W, Shi Z, Wang W and Zhou T 2007 Phys. Lett. A 364 189
[32] Kong Y, Shi G, Wu R and Zhang Y 2019 Physics Reports 832 1
[33] Ryan R and Nesreen A 2015 Proceedings of the 29th AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas USA, p. 4292
[34] https://doi.org/10.24433/CO.3005605.v1
[35] Guimerá R, Danon L, Díaz-Guilera A, Giralt F and Arenas A 2003 Phys. Rev. E 68 065103
[36] Jeong H, Mason S P, Barabási A L and Oltvai Z N 2001 Nature 411 41
[37] http://interactome.dfci.harvard.edu/H_sapiens/
[38] Leskovec J, Kleinberg J and Faloutsos C 2007 Graph Evolution: Densification and Shrinking Diameters, March, 2007, New York, USA, 1

Identifying multiple influential spreaders in complex networks based on spectral graph theory

Identifying multiple influential spreaders in complex networks based on spectral graph theory

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

Metrics

本文评价

推荐阅读 0