Negative Influence Blocking Maximization with Uncertain Sources under the Independent Cascade Model

Abstract The propagation of negative influences, such as epidemic spreading, rumors, and false information in social networks and computer viruses, may lead to serious consequences. The issue of negative influence blocking maximization (IBM) has aroused intense interest from researchers. However, in real-world social network environments, the source of negative influence is typically unknown. In most cases, we only know the distribution of negative seeds and the probability for each node to be a negative seed. In this paper, this problem is defined as negative influence blocking maximization with an uncertain source (IBM-US), and a model is shown to approximately describe opposing effects that proliferate in the IBM-US problem. To calculate the blocking effect of the joint impact of positive and negative seed sets, a blocking function is defined, and an algorithm called IBM-Seed is used for the IBM problem in the independent cascade (IC) propagation model. A sampling-based algorithm IBM-US-SB-Seed is proposed to achieve an approximate solution for the IBM-US problem. The convergence of the IBM-US-SB-Seed algorithm is proven, and the convergence speed and the number of samples are analyzed. An extended sampling-based algorithm IBM-US-Seed for the IBM-US problem is shown to achieve a proper balance between result precision and computation time. The proposed algorithms are tested on real datasets, and the experimental results demonstrate that the proposed algorithms can yield higher quality results than other similar methods.