Influence Blocking Maximization Under Refutation

In social networks, a phenomenon termed the refutation mechanism arises when certain users spontaneously counter negative information based on their knowledge and experience. To the best of our knowledge, this paper focuses on the influence blocking maximization under the refutation mechanism for the first time. Specifically, incorporating the refutation mechanism with the Competitive Independent Cascade (CIC) model, we introduce the Refutation Competitive Independent Cascade (RCIC) model, while also considering real-time delay. Under the proposed model, we study the Joint Influence Blocking Maximization (JIBM) problem. The objective of JIBM is to maximize the expected number of nonnegatives by finding a set of positive seeds in a network. We show that the problem is NP-hard. We present a scalable approximation algorithm, named RR-JIBM, by making a non-trivial adaptation of the generation process of reverse reachable sets. We prove that the given algorithms achieve (1 − 1/e − ε)-approximation for any ε > 0 for JIBM problem. An improved algorithm named RR-JIBM+ is also proposed to improve the efficiency of RR-JIBM in reality. Experiments on real-world social networks show that our algorithms outperform other intuitive baselines in reducing the number of nodes influenced by negative seed nodes. Meanwhile, the RR-JIBM+ algorithm has a higher efficiency advantage than RR-JIBM on different datasets.