# From Competition to Complementarity: Comparative Influence Diffusion and Maximization

arXiv: https://arxiv.org/abs/1507.00317 · HTML: https://mlsanity.com/paper/1507.00317/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2015.

## Built on by (most cited first, 6 of 6)

- [Simulating Opinion Dynamics with Networks of LLM-based Agents](https://mlsanity.com/paper/2311.09618/) (2023)
- [DEBATE: A Large-Scale Benchmark for Evaluating Opinion Dynamics in Role-Playing LLM Agents](https://mlsanity.com/paper/2510.25110/) (2025)
- [Graph Bayesian Optimization for Multiplex Influence Maximization](https://mlsanity.com/paper/2403.18866/) (2024)
- [Viral Marketing in Social Networks with Competing Products](https://mlsanity.com/paper/2312.15819/) (2023)
- [Jointly Complementary&Competitive Influence Maximization with Concurrent Ally-Boosting and Rival-Preventing](https://mlsanity.com/paper/2302.09620/) (2023)
- [A Generalisation of Voter Model: Influential Nodes and Convergence Properties](https://mlsanity.com/paper/2411.04564/) (2024)

## Abstract (arXiv)

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". The applicability of both techniques extends beyond our model and problems. Our experiments show that the proposed algorithms consistently outperform intuitive baselines in four real-world social networks, often by a significant margin. In addition, we learn model parameters from real user action logs.