关键词: 社交网络, NP难度问题, 正影响支配集, 贪心算法, 轮转贪心

Abstract: The problem of the smallest positive influence dominating set in a social network is a NP-hard combinatorial optimization problem. Aiming at this problem, there are two typical greedy algorithms with fast solving speed at present, but the quality of greedy solution needs to be improved. The carousel greedy method is to improve the quality of greedy solution without increasing the time complexity of greedy algorithm, and for some classical NP-hard problems, the experimental results show that the carousel greedy method can effectively improve their greedy algorithms. In this paper, the carousel greedy method is combined with the two greedy algorithms that have positive influence on the dominant set to improve the solution quality of the greedy algorithm, so as to propose the corresponding rotation greedy algorithm. The experimental results on several real social network instances show that, compared with the original greedy algorithms, the solution quality of the proposed carousel greedy algorithm is improved.

Key words: social network, NP hard problem, positive influence dominating set, greedy algorithm, carousel greedy