Maximizing Social Welfare in a Competitive Diffusion Model
This work is significant for researchers and practitioners in viral marketing and social network analysis, as it provides a more realistic model for competitive influence maximization by considering economic incentives and social welfare, rather than just individual item adoption.
This paper addresses competitive influence maximization by incorporating economic incentives into user decision-making within a utility-driven propagation model (UIC) to maximize social welfare. The authors developed efficient approximation algorithms for this NP-hard problem, outperforming baselines in solution quality and running time on large real networks.
Influence maximization (IM) has garnered a lot of attention in the literature owing to applications such as viral marketing and infection containment. It aims to select a small number of seed users to adopt an item such that adoption propagates to a large number of users in the network. Competitive IM focuses on the propagation of competing items in the network. Existing works on competitive IM have several limitations. (1) They fail to incorporate economic incentives in users' decision making in item adoptions. (2) Majority of the works aim to maximize the adoption of one particular item, and ignore the collective role that different items play. (3) They focus mostly on one aspect of competition -- pure competition. To address these concerns we study competitive IM under a utility-driven propagation model called UIC, and study social welfare maximization. The problem in general is not only NP-hard but also NP-hard to approximate within any constant factor. We, therefore, devise instant dependent efficient approximation algorithms for the general case as well as a $(1-1/e-ε)$-approximation algorithm for a restricted setting. Our algorithms outperform different baselines on competitive IM, both in terms of solution quality and running time on large real networks under both synthetic and real utility configurations.