Influence maximization is a well-studied data mining problem that asks for a small set of influential users froma social network, such that by targeting them as early adopters, the expected total adoption through influence cascades over the network is maximized. However, almost all prior work focuses on cascades of a single propagating entity or purely-competitive entities. In this work, we proposed the Comparative Independent Cascade (Com-IC) model that covers the full spectrum of entity interactions from competition to complementarity. In Com-IC, users’ adoption decisions depend not only on edge-level information propagation, but also on a node-level automaton governed by a set of model parameters, enabling the model to capture both competition and complementarity to any possible degree. We designed efficient and effective approximation algorithms via non-trivial techniques based on reverse-reachable sets and a novel “sandwich approximation” strategy. The applicability of both techniques extends beyond our model and problems. Empirical studies showed that the proposed algorithms consistently outperform intuitive baselines on four real-world social networks, often by a significant margin.
LinkedIn Engineering @ VLDB 2016