An Iterated Carousel Greedy Algorithm for Finding Minimum Positive Influence Dominating Sets in Social Networks
Yunfan Shan, Qinma Kang, Ran Xiao, Yiran Chen, Yunfan Kang
Abstract
The online social network has become an integral part of modern society and serves as an excellent platform for information diffusion, marketing, and so on. The minimum positive influence dominating set (MPIDS) problem aims to find a set of at least half neighbors of every individual with minimum cardinality and has lots of applications in the social network. Even though numerous algorithms have been proposed for this hard combinatorial problem, challenges such as poor quality and scalability have motivated the researchers for better solutions. In this article, we focus on designing a simple and effective method and propose an iterated carousel greedy (ICG) algorithm for the MPIDS problem. The destruction, carousel, and reconstruction (DCR) procedures are well-designed based on the problem-specific knowledge to improve the algorithm performance, while maintaining the simplicity of the ICG algorithm. The ICG algorithm uses a fast greedy algorithm to generate an initial solution with a certain quality. It then obtains a sequence of better solutions by iterating over DCR phases. A carefully designed experiment is carried out to determine the best parameter configuration. The experimental results on real-world networks indicate that the proposed ICG algorithm significantly outperforms the current state-of-the-art algorithms.