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

作　　者：卢鹏丽 揽继茂 唐建新 张莉 宋仕辉 朱虹羽 Pengli Lu;Jimao Lan;Jianxin Tang;Li Zhang;Shihui Song;Hongyu Zhu(Wenzhou Engineering Institute of Pump&Valve,Lanzhou University of Technology,Wenzhou 325100,China;School of Computer and Communication,Lanzhou University of Technology,Lanzhou 730050,China)

机构地区：[1]Wenzhou Engineering Institute of Pump&Valve,Lanzhou University of Technology,Wenzhou 325100,China [2]School of Computer and Communication,Lanzhou University of Technology,Lanzhou 730050,China

出　　处：《Chinese Physics B》2024年第1期743-754,共12页中国物理B（英文版）

基　　金：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);the National Key Research and Development Program of China (Grant No.2020YFB1713600)。

摘　　要：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.

关 键 词：social networks influence maximization metaheuristic optimization quantum-behaved particle swarm optimization Lévy flight 

分 类 号：O157.5[理学—数学] TP18[理学—基础数学]