Inﬂuence maximization is a well-studied data mining problem that asks for a small set of inﬂuential users froma social network, such that by targeting them as early adopters, the expected total adoption through inﬂuence 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 eﬃcient and eﬀective 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 signiﬁcant margin.
LinkedIn Engineering @ VLDB 2016