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.
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 Nature524 65 [8] Pei S, Wang J, Morone F and Makse H A 2019 Complex Networks8 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 A391 1777 [13] Freeman L C 1978 Social Networks1 215 [14] Sabidussi Gert 1966 Psychometrika31 581 [15] Dangalchev C 2006 Physica A365 556 [16] Chen D, Gao H, Lü L and Zhou T 2013 PLoS ONE8 1 [17] Brin S and Page L 1998 Computer Networks and ISDN Systems30 107 [18] Lü L, Zhang Y, Yeung C H and Zhou T 2011 PLoS ONE6 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. A380 837 [25] Morone F and Makse H 2015 Nature524 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 A519 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. E80 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. A364 189 [32] Kong Y, Shi G, Wu R and Zhang Y 2019 Physics Reports832 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. E68 065103 [36] Jeong H, Mason S P, Barabási A L and Oltvai Z N 2001 Nature411 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
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
