Prithu Banerjee, Wei Chen, Laks V. S. Lakshmanan
arXiv 6 Jul 2018 · cs.SI
arXiv:1807.02502 · PDF · DOI · OpenAlex · Extracted main text
Motivated by applications such as viral marketing, the problem of influence maximization (IM) has been extensively studied in the literature. The goal is to select a small number of users to adopt an item such that it results in a large cascade of adoptions by others. Existing works have three key limitations. (1) They do not account for economic considerations of a user in buying/adopting items. (2) Most studies on multiple items focus on competition, with complementary items receiving limited attention. (3) For the network owner, maximizing social welfare is important to ensure customer loyalty, which is not addressed in prior work in the IM literature. In this paper, we address all three limitations and propose a novel model called UIC that combines utility-driven item adoption with influence propagation over networks. Focusing on the mutually complementary setting, we formulate the problem of social welfare maximization in this novel setting. We show that while the objective function is neither submodular nor supermodular, surprisingly a simple greedy allocation algorithm achieves a factor of $(1-1/e-\epsilon)$ of the optimum expected social welfare. We develop \textsf{bundleGRD}, a scalable version of this approximation algorithm, and demonstrate, with comprehensive experiments on real and synthetic datasets, that it significantly outperforms all baselines.
appendix boundary found by none_found · 100% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | David Kempe, Jon Kleinberg, and Éva Tardos (2003) Maximizing the spread of influence through a social network | 1.000 | 10 | 3 | 100% |
| 2 | Uriel Feige and Jan Vondrák (2010) The submodular welfare problem with demand queries | 1.000 | 5 | 3 | 100% |
| 3 | Youze Tang, Yanchen Shi, and Xiaokui Xiao (2015) Influence maximization in near-linear time: A martingale approach | 0.874 | 21 | 2 | 100% |
| 4 | Wei Lu, Wei Chen, and Laks VS Lakshmanan (2015) From competition to complementarity: comparative influence diffusion and maximization self | 0.874 | 13 | 2 | 100% |
| 5 | Donald M Topkis (1998) Supermodularity and Complementarity | 0.843 | 3 | 3 | 100% |
| 6 | Sayan Bhattacharya, Wolfgang Dvorák, Monika Henzinger, and Martin St… (2017) Welfare maximization with friends-of-friends network externalities | 0.811 | 4 | 2 | 100% |
| 7 | Michael Kapralov, Ian Post, and Jan Vondrák (2013) Online submodular welfare maximization: Greedy is optimal | 0.811 | 4 | 2 | 100% |
| 8 | Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani (2007) Algorithmic game theory | 0.811 | 4 | 2 | 100% |
| 9 | Hung T Nguyen, My T Thai, and Thang N Dinh (2016) Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks | 0.737 | 3 | 2 | 100% |
| 10 | Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier (2014) Maximizing social influence in nearly optimal time | 0.737 | 3 | 2 | 100% |
Showing the top 10 of 53 scored citations.