Influence maximization (IM) has received great attention and has become a widely studied problem in social network analysis. The IM problem aims to find the top k nodes that maximize influence in the network. In IM, the Greedy algorithm is the first simulations-based algorithm that guarantees to give a solution with an approximation of \(\left( 1-\frac{1}{e}\right) \) . This simulation nature of the Greedy algorithm makes it limited to smaller social networks as it takes higher execution time to execute on bigger networks. Besides this, quantum computers have shown their supremacy in efficiency as compared to classical computers. This work introduces quantum simulations in IM and proposes a novel quantum simulations-based Greedy algorithm. The Greedy-based proposed algorithm simulates the influence using the quantum circuit. This work maps the influence diffusion rules in the quantum circuit which are encoded by quantum gates. The proposed work conducts experiments under the constraints of available qubits and shows that the quantum-simulation-based Greedy algorithm achieved a similar influence as the classical Greedy algorithm.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Quantum Simulations: A New Frontier for Influence Maximization in Social Networks

  • Sunil Kumar Meena,
  • Shashank Sheshar Singh,
  • Yogendra Meena,
  • Kuldeep Singh

摘要

Influence maximization (IM) has received great attention and has become a widely studied problem in social network analysis. The IM problem aims to find the top k nodes that maximize influence in the network. In IM, the Greedy algorithm is the first simulations-based algorithm that guarantees to give a solution with an approximation of \(\left( 1-\frac{1}{e}\right) \) . This simulation nature of the Greedy algorithm makes it limited to smaller social networks as it takes higher execution time to execute on bigger networks. Besides this, quantum computers have shown their supremacy in efficiency as compared to classical computers. This work introduces quantum simulations in IM and proposes a novel quantum simulations-based Greedy algorithm. The Greedy-based proposed algorithm simulates the influence using the quantum circuit. This work maps the influence diffusion rules in the quantum circuit which are encoded by quantum gates. The proposed work conducts experiments under the constraints of available qubits and shows that the quantum-simulation-based Greedy algorithm achieved a similar influence as the classical Greedy algorithm.