Identifying influential spreaders in social networks: A two-stage quantum-behaved particle swarm optimization with Lévy flight

doi:10.1088/1674-1056/acd3e0

Abstract The influence maximization problem aims to select a small set of influential nodes, termed a seed set, to maximize their influence coverage in social networks. Although the methods that are based on a greedy strategy can obtain good accuracy, they come at the cost of enormous computational time, and are therefore not applicable to practical scenarios in large-scale networks. In addition, the centrality heuristic algorithms that are based on network topology can be completed in relatively less time. However, they tend to fail to achieve satisfactory results because of drawbacks such as overlapped influence spread. In this work, we propose a discrete two-stage metaheuristic optimization combining quantum-behaved particle swarm optimization with Lévy flight to identify a set of the most influential spreaders. According to the framework, first, the particles in the population are tasked to conduct an exploration in the global solution space to eventually converge to an acceptable solution through the crossover and replacement operations. Second, the Lévy flight mechanism is used to perform a wandering walk on the optimal candidate solution in the population to exploit the potentially unidentified influential nodes in the network. Experiments on six real-world social networks show that the proposed algorithm achieves more satisfactory results when compared to other well-known algorithms.

Keywords: social networks influence maximization metaheuristic optimization quantum-behaved particle swarm optimization Lévy flight

Received: 09 February 2023
Revised: 08 May 2023
Accepted manuscript online: 10 May 2023

PACS:	89.75.-k	(Complex systems)
	01.75.+m	(Science and society)
	03.67.Ac	(Quantum algorithms, protocols, and simulations)
	05.40.Fb	(Random walks and Levy flights)

Fund: Project supported by the Zhejiang Provincial Natural Science Foundation (Grant No. LQ20F020011), the Gansu Provincial Foundation for Distinguished Young Scholars (Grant No. 23JRRA766), the National Natural Science Foundation of China (Grant No. 62162040), and the National Key Research and Development Program of China (Grant No. 2020YFB1713600).

Corresponding Authors: Jianxin Tang
E-mail: tangjx@lut.edu.cn

Cite this article:

Pengli Lu(卢鹏丽), Jimao Lan(揽继茂), Jianxin Tang(唐建新), Li Zhang(张莉), Shihui Song(宋仕辉), and Hongyu Zhu(朱虹羽) Identifying influential spreaders in social networks: A two-stage quantum-behaved particle swarm optimization with Lévy flight 2024 Chin. Phys. B 33 018901

[1] Zamani E D and Spanaki K 2023 J. Bus. Res. 154 113311
[2] Nabity-Grover T, Cheung C M K and Bennett Thatcher J 2023 J. Bus. Res. 154 113310
[3] Hu X J, Qiu J, Zhao J and Li Y 2023 J. Retail. Consum. Serv. 70 103142
[4] Xiao Y P, Huang Z, Li Q, Lu X Y and Li T 2022 IEEE Trans. Knowl. Data Eng. 35 4682
[5] Domingos P and Richardson M 2001 Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (San Francisco:California) p. 57
[6] Kempe D, Kleinberg J and Tardos E 2003 Proceedings of the ninth ACM SIGKDD international confer-ence on Knowledge discovery and data mining (Washington:D.C.) p. 137
[7] Freeman L C 1978 Soc. Netw. 1 215
[8] Brin S and Page L 1998 Comput. Netw. ISDN Syst. 30 107
[9] Alshahrani M, Zhu F X, Sameh A, Mekouar S and Huang S 2020 Inform. Sci. 527 88
[10] Bozorgi A, Haghighi H, Sadegh Zahedi M and Rezvani M 2016 Inform. Proc. Manag. 52 1188
[11] Cai F, Qiu L R Kuai X K and Zhao H S 2019 IEEE Access 7 152115
[12] Zareie A, Sheikhahmadi A and Jalili M 2020 Expert Syst. Appl. 142 112971
[13] Li H, Zhang R S, Zhao Z L, Liu X and Yuan Y N 2021 Appl. Intell. 212 118702
[14] Leskovec J, Krause A and Guestrin C, Faloutsos C, VanBriesen J and Glance N 2007 13th International Conference on Knowledge Discovery and Data Mining (San Jose:CA) p. 420
[15] Goyal A, Lu W and Lakshmanan L V S 2011 Proceedings of the 20th international conference companion on World wide web (Hyderabad:India) p. 47
[16] Zhang S Q, Zeng X X and Tang B 2021 Inf. Syst. 102 101828
[17] Chen W, Wang Y J and Yang S Y 2009 Acm Sigkdd International Conference on Knowledge Discovery & Data Mining (Paris:France) p. 199
[18] Zareie A and Sheikhahmadi A 2018 Expert Syst. Appl. 93 200
[19] Wang Y F, Dong W Y and Dong X S 2018 Fut. Gener. Comput. Syst. 88 755
[20] Li W M, Zhong K X, Wang J J and Chen D H 2021 Expert Syst. Appl. 169 114207
[21] Meng L, Xu G Q and Yang P L and Tu D Q 2022 J. Comput. Sci. 60 101591
[22] Li Q, Cheng L, Wang W,Li X H,Li S D and Zhu P C 2023 Appl. Math. Comput. 442 127721
[23] Jiang Q Y, Song G J, Gao C,Wang Y, Si W J and Xie K Q 2011 Proceedings of the Twenty-Fifth AAAI Conference on Articial Intelligence (San Francisco, California) p. 7
[24] Gong M G, Yan J N and Shen B,Ma L J and Cai Q 2016 Inform. Sci. 367 600
[25] Tang J X, Zhang R S, Yao Y B, Zhao Z L, Wang P, Li H and Yuan J L 2018 Knowl. Based Syst. 160 88
[26] Cui L Z, Hu H X, Yu S, Yan Q, Ming Z, Wen Z K and Lu N 2018 J. Netw. Comput. Appl. 103 119
[27] Singh S S, Kumar A, Singh K and Biswas B 2019 Appl. Soft Comput. 82 105554
[28] Wang L, Ma L and Wang C and Xie N G 2021 IEEE Trans. Evol. Comput. 25 1091
[29] Weskida M and Michalski R 2019 J. Comput. Sci. 31 77
[30] Sun J, Feng B and Xu W B 2004 IEEE Conf. Cyber Inte. Syst. 1 111
[31] Yang C X, Zhang J and Tong M S 2021 IEEE Trans. Antennas Propag. 69 9
[32] Bajaj A and Abraham A 2022 2022 IEEE Cong. Evol. Comput. (CEC) 1
[33] Dian S Y, Zhong J N, Guo B, Liu J X and Guo R 2022 Expert Syst. Appl. 208 118256
[34] Lu X L and He G 2021 Appl. Soft Comput. 99 106894
[35] Li L L, Jiao L C and Zhao J Q Shang R H and Gong M G 2017 Patt. Reco. 63 1
[36] Zhou B H and Lei Y R 2021 Appl. Soft Comput. 111 107717
[37] Pei S, Muchnik L, Andrade J S, Zheng Z M and Makse H A 2014 Sci. Rep. 4 5547
[38] Kennedy J and Eberhart R 1995 Proceedings of ICNN'95-International Conference on Neural Networks 4 1942
[39] Jensi R and Jiji G W 2016 Appl. Soft Comput. 43 248
[40] Lu J W, Zhang J and Sheng J N 2022 Swarm Evol. Comput. 69 100989
[41] Dennis C, Ombuki-Berman B M and Engelbrecht A 2021 2021 IEEE Cong. Evol. Comput. (CEC) 10 2289
[42] Clerc M 1999 Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 3 1951

[1]	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(任卫平). Chin. Phys. B, 2023, 32(9): 098904.
[2]	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.
[3]	Influence fast or later: Two types of influencers in social networks Fang Zhou(周方), Chang Su(苏畅), Shuqi Xu(徐舒琪), and Linyuan Lü(吕琳媛). Chin. Phys. B, 2022, 31(6): 068901.
[4]	Uncovering offline event similarity of online friends by constructing null models Wenkuo Cui(崔文阔), Jing Xiao(肖婧), Ting Li(李婷), Xiaoke Xu(许小可). Chin. Phys. B, 2019, 28(6): 068901.
[5]	Evolutionary prisoner's dilemma on Newman--Watts socialnetworks with an asymmetric payoff distribution mechanism Du Wen-Bo(杜文博), Cao Xian-Bin(曹先彬), Yang Han-Xin(杨涵新), and Hu Mao-Bin(胡茂彬) . Chin. Phys. B, 2010, 19(1): 010204.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Identifying influential spreaders in social networks: A two-stage quantum-behaved particle swarm optimization with Lévy flight

Cite this article:

Online attention