Influence maximization (IM) aims to identify a small set of influential users to maximize the information spread. It has been widely applied in the context of viral marketing, where a company distributes incentives to a few influencers to promote the product. However, in practical scenarios, not all users hold equal importance and certain users need to be prioritized for the specific requirements. Motivated by this, recently, a variant problem of IM, called influence maximization with priority (IMP), has been proposed. Given a graph G=(V,E), a priority set P ⊆ V and a threshold T ∈ [0, |P|], IMP aims to identify a set of k nodes (termed seeds ) to maximize the expected number of activated nodes in G while satisfying that the expected number of activated nodes in~P is no less than the given threshold. Nevertheless, we show that existing solutions for IMP are inferior in maximizing the influence spread in G, and can only offer poor approximation ratios in many cases. To address these limitations, in this paper, we first propose a novel framework named SAR with both superior effectiveness and strong theoretical guarantees. In addition, to obtain more practical results, we study the IMP problem under the adaptive setting, where the seeds are iteratively selected after observing the diffusion result of the previous seeds. We design an effective method AAS that achieves expected approximation guarantees. Extensive experiments demonstrate that, compared with the state-of-the-art method, SAR achieves up to 22.3% larger spread and ås achieves up to 42.6% larger spread, with both exhibiting a higher approximation ratio.

Influence minimization (IMIN) aims to identify a set of nodes to be blocked, such that the expected number of nodes activated by the given seed set is minimized. It has many important applications, such as misinformation suppression, and has been extensively studied in the literature. Existing works for IMIN, however, neglect key temporal information in real-world scenarios. In this paper, we generalize IMIN and study the time-critical influence minimization (TCIM) problem, which aims to minimize the activation duration-aware influence spread of the seed set by a deadline via node blocking. We show that TCIM is NP-hard and APX-hard, and the objective function is non-submodular. To address the problem, we propose CBFM, an efficient and effective algorithm that provides τ(1-1/e-ε)-approximation with at least 1-3δ probability, where τ is a data-driven parameter, ε and δ are tunable error parameters. Novel concentration results are designed to facilitate the establishment of the approximation guarantee. Moreover, we show that CBFM can be extended to tackle the misinformation mitigation (MM) problem. The existing MM solution offers the approximation guarantee only under specific assumptions. Our extended approach is assumption-free yet still attains the same guarantee, thereby bridging the theoretical gap. Finally, we conduct extensive experiments on 11 datasets to validate the performance of proposed algorithms on TCIM, IMIN (a special case of TCIM), and MM problems. The results show that for TCIM, CBFM achieves up to four orders of magnitude speedup over the baseline; for IMIN, CBFM outperforms the state-of-the-art in terms of efficiency, approximation ratio, and memory usage. Moreover, for MM, our solution can be two orders of magnitude faster than the corresponding state-of-the-art.

Given a graph G , a budget k and a misinformation seed set S, Influence Minimization (IMIN) via node blocking aims to find a set of k nodes to be blocked such that the expected spread of S is minimized. This problem finds important applications in suppressing the spread of misinformation and has been extensively studied in the literature. However, existing solutions for IMIN still incur significant computation overhead, especially when k becomes large. In addition, there is still no approximation solution with non-trivial theoretical guarantee for IMIN via node blocking prior to our work. In this paper, we conduct the first attempt to propose algorithms that yield data-dependent approximation guarantees. Based on the Sandwich framework, we first develop submodular and monotonic lower and upper bounds for our non-submodular objective function and prove the computation of proposed bounds is #P-hard. In addition, two advanced sampling methods are proposed to estimate the value of bounding functions. Moreover, we develop two novel martingale-based concentration bounds to reduce the sample complexity and design two non-trivial algorithms that provide (1 - 1/ e - ϵ )-approximate solutions to our bounding functions. Comprehensive experiments on 9 real-world datasets are conducted to validate the efficiency and effectiveness of the proposed techniques. Compared with the state-of-the-art methods, our solutions can achieve up to two orders of magnitude speedup and provide theoretical guarantees for the quality of returned results.