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

doi:10.1088/1674-1056/acac0b

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.

Keywords: spectral graph theory Laplace matrix influence maximization multiple influential spreaders

Received: 13 September 2022
Revised: 11 December 2022
Accepted manuscript online: 16 December 2022

PACS:

89.75.Fb

(Structures and organization in complex systems)

Fund: 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).

Corresponding Authors: Jia-Lin He
E-mail: hejialin32@126.com

Cite this article:

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 2023 Chin. Phys. B 32 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

[1]	AIGCrank: A new adaptive algorithm for identifying a set of influential spreaders in complex networks based on gravity centrality Ping-Le Yang(杨平乐), Lai-Jun Zhao(赵来军), Chen Dong(董晨),Gui-Qiong Xu(徐桂琼), and Li-Xin Zhou(周立欣). Chin. Phys. B, 2023, 32(5): 058901.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

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

Cite this article:

Online attention