Quantum Simulations: A New Frontier for Influence Maximization in Social Networks
摘要
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.