Influence Maximization via Vertex Countering

Download PDF

Abstract

Competitive viral marketing considers the product competition of multiple companies, where each user may adopt one product and propagate the product to other users. Existing studies focus on a traditional seeding strategy where a company only selects seeds from the users with no adopted product to maximize its influence (i.e., the number of users who will adopt its product). However, influential users are often rare, and the gain from traditional seeding will degrade as the number of seeds increases. Therefore, in this paper, we study the promising countering strategy which is to counter some users who initially use other products s.t. they will turn to adopting the target product and recommending it to others. We propose the problem of influence countering: given a graph, a budget 𝑏, a target company 𝐶𝑡 , and a set 𝑆 of the seeds adopting different companies (where each seed adopts one company), we counter 𝑏 users in 𝑆 who do not adopt 𝐶𝑡 to turn to adopt 𝐶𝑡 s.t. the expected number of users who eventually adopt 𝐶𝑡 in the influence diffusion is maximized. Following existing studies, we formalize the diffusion process by the Multi-Campaigner Independent Cascade model. We prove the influence countering problem is #P-complete and its influence computation is #P-hard. Then, we propose two novel algorithms MIC and MIC+ to address the problem. In general, MIC estimates seed influence by its empirical average influence in multiple graph samplings, while MIC+ improves MIC by reducing the cost of influence estimation and the required number of samples. Given pre-set 𝜀 and 𝑙, both algorithms return a (1 − 𝜀)-approximate solution with at least 1 − 𝑛−𝑙 probability. We also design an index for MIC+ to efficiently process graphs that are frequently updated. The experiments on 8 real-world datasets show that our algorithms are efficient in practice while offering strong result quality.