论文标题
在竞争扩散模型中最大化社会福利
Maximizing Social Welfare in a Competitive Diffusion Model
论文作者
论文摘要
由于病毒营销和感染遏制等应用，影响最大化（IM）在文献中引起了很多关注。它旨在选择少量的种子用户采用一个项目，以便采用网络中的大量用户。竞争性IM专注于网络中竞争项目的传播。现有关于竞争性IM的作品有几个限制。 （1）他们未能将经济激励措施纳入用户决策中。 （2）大多数作品旨在最大程度地采用一个特定项目，而忽略不同项目扮演的集体角色。 （3）他们主要集中在竞争的一个方面 - 纯粹的竞争。为了解决这些问题，我们根据称为UIC的公用事业驱动的传播模型研究竞争性IM，并研究社会福利最大化。通常，这个问题不仅是NP-硬化，而且在任何恒定因素内都达到了近似值。因此，我们为常规情况设计了即时依赖性有效近似算法，以及$（1-1/e-ε）$ - 近似算法用于限制设置。在综合和真实效用配置下，我们的算法在解决方案质量和大型真实网络上的运行时间方面都优于竞争性IM的不同基准。
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.
