Influence maximization is a well-studied problem that asks for a small set of influential users from a 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 propose 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 whose behavior is governed by a set of model parameters, enabling our model to capture not only competition, but also complementarity, to any possible degree. We study two natural optimization problems, Self Influence Maximization and Complementary Influence Maximization, in a novel setting with complementary entities. Both problems are NP-hard, and we devise 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. Our experiments show that the proposed algorithms consistently outperform intuitive baselines in four realworld social networks, often by a significant margin. In addition, we learn model parameters from real user action logs. Review of Classical IC Model. In the IC model [16] , there is just one entity (e.g., idea or product) being propagated through the network. An instance of the model has a directed graph G = (V, E, p) where p : E → [0, 1], and a seed set S ⊂ V . For convenience, we use pu,v for p (u, v). At time step 0, the seeds are active and all other nodes are inactive. Propagation proceeds in discrete time steps. At time t, every node u that became active at t−1 makes one attempt to activate each of its inactive out-neighbors v. This can be seen as node u "testing" if the edge (u, v) is "live" or "blocked". The out-neighbor v becomes active at t iff the edge is live. The propagation ends when no new nodes become active. Key differences from IC model. In the Comparative IC model 1 No generality is lost in assuming seeds adopt an item without testing the NLA: for every v ∈ V , we can create two dummy nodes vA, vB and edges (vA, v) and (vB, v) with pv A ,v = pv B ,v = 1. Requiring seeds to go through NLA is equivalent to constraining that A-seeds (B-seeds) be selected from all vA's (resp. vB's).
The related complementary opinion is extended by Lu et al. REF , who proposed the Comparative Independent Cascade (Com-IC) model consisting of edge-level information propagation and a Node-Level Automation (NLA) that ultimately makes adoption decisions based on a set of model parameters called Global Adoption Probabilities (GAPs), to address the Complementary Influence Maximization problem.
From Competition to Complementarity: Comparative Influence Diffusion and Maximization
ArXiv
ArXiv
Computer Science Physics