Paper Info
Title
Influence Maximization with Spontaneous User Adoption.
Abstract
We incorporate the realistic scenario of spontaneous user adoption into influence propagation (also refer to as self-activation) and propose the self-activation independent cascade (SAIC) model: nodes may be self activated besides being selected as seeds, and influence propagates from both selected seeds and self activated nodes. Self activation occurs in many real world situations; for example, people naturally share product recommendations with their friends, even without marketing intervention. Under the SAIC model, we study three influence maximization problems: (a) boosted influence maximization (BIM) aims to maximize the total influence spread from both self-activated nodes and k selected seeds; (b) preemptive influence maximization (PIM) aims to find k nodes that, if self-activated, can reach the most number of nodes before other self-activated nodes; and (c) boosted preemptive influence maximization (BPIM) aims to select k seed that are guaranteed to be activated and can reach the most number of nodes before other self-activated nodes. We propose scalable algorithms for all three problems and prove that they achieve $1-1/e-\varepsilon$ approximation for BIM and BPIM and $1-\varepsilon$ for PIM, for any $\varepsilon > 0$. Through extensive tests on real-world graphs, we demonstrate that our algorithms outperform the baseline algorithms significantly for the PIM problem in solution quality, and also outperform the baselines for BIM and BPIM when self-activation behaviors are nonuniform across nodes.
Year
DOI
Venue
2020
10.1145/3336191.3371791
WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining Houston TX USA February, 2020
Keywords
Field
DocType
preemptive influence maximization, reverse influence sampling
Information retrieval,Computer science,Maximization
Conference
ISBN
Citations 
PageRank 
978-1-4503-6822-3
1
0.35
References 
Authors
18
4
Name
Order
Citations
PageRank
Lichao Sun19414.15
Albert Chen28512.66
Philip S. Yu3306703474.16
Wei Chen43416170.71