中国物理B ›› 2024, Vol. 33 ›› Issue (1): 18901-18901.doi: 10.1088/1674-1056/acd3e0

• • 上一篇    下一篇

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

Pengli Lu(卢鹏丽)2, Jimao Lan(揽继茂)2, Jianxin Tang(唐建新)1,2,†, Li Zhang(张莉)2, Shihui Song(宋仕辉)2, and Hongyu Zhu(朱虹羽)2   

  1. 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
  • 收稿日期:2023-02-09 修回日期:2023-05-08 接受日期:2023-05-10 出版日期:2023-12-13 发布日期:2023-12-13
  • 通讯作者: Jianxin Tang E-mail:tangjx@lut.edu.cn
  • 基金资助:
    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).

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

Pengli Lu(卢鹏丽)2, Jimao Lan(揽继茂)2, Jianxin Tang(唐建新)1,2,†, Li Zhang(张莉)2, Shihui Song(宋仕辉)2, and Hongyu Zhu(朱虹羽)2   

  1. 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
  • Received:2023-02-09 Revised:2023-05-08 Accepted:2023-05-10 Online:2023-12-13 Published:2023-12-13
  • Contact: Jianxin Tang E-mail:tangjx@lut.edu.cn
  • Supported by:
    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).

摘要: 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

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.

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

中图分类号:  (Complex systems)

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