Effective Influence Maximization with Priority

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 𝐺 = (𝑉 , 𝐸), a priority set 𝑃 ⊆ 𝑉 and a threshold 𝑇 ∈ [0, |𝑃 |], IMP aims to identify a set of 𝑘 nodes (termed seeds) to maximize the expected number of activated nodes in 𝐺 while satisfying that the expected number of activated nodes in 𝑃 is no less than the given threshold. Nevertheless, we show that existing solutions for IMP are inferior in maximizing the influence spread in 𝐺, 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 AAS achieves up to 42.6% larger spread, with both exhibiting a higher approximation ratio. CCS Concepts • Theory of computation → Graph algorithms analysis.