Influence Maximization with Spontaneous User Adoption

We incorporate self activation into influence propagation 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 reflects the real-world scenarios such as people naturally share product recommendations with their friends even without marketing intervention. It also leads to two new forms of optimization problems: (a) em preemptive influence maximization (PIM), which aims to find k nodes that, if self-activated, can reach the most number of nodes before other self-activated nodes; and (b) em boosted preemptive influence maximization (BPIM), which aims to select k seeds that are guaranteed to be activated and can reach the most number of nodes before other self-activated nodes. We propose scalable algorithms for PIM and BPIM and prove that they achieve 1-varepsilon approximation for PIM and 1-1/e-varepsilon approximation for BPIM, 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 BPIM when self-activation behaviors are non-uniform across nodes.