# Viral Marketing in Social Networks with Competing Products

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 62 references that are in the map.
- First posted on arXiv 25 Dec 2023.

## Builds on (most cited first, 10 of 10)

- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [From Competition to Complementarity: Comparative Influence Diffusion and Maximization](https://mlsanity.com/paper/1507.00317/) (2015)
- [Controlling Elections through Social Influence](https://mlsanity.com/paper/1711.08615/) (2017)
- [Convergence of Opinion Diffusion is PSPACE-complete](https://mlsanity.com/paper/1912.09864/) (2019)
- [Opinion Forming in Erdos-Renyi Random Graph and Expanders](https://mlsanity.com/paper/1805.12172/) (2018)
- [Majority Opinion Diffusion in Social Networks: An Adversarial Approach](https://mlsanity.com/paper/2012.03143/) (2020)
- [Limitations of Greed: Influence Maximization in Undirected Networks Re-visited](https://mlsanity.com/paper/2002.11679/) (2020)
- [A Formal Model for Polarization under Confirmation Bias in Social Networks](https://mlsanity.com/paper/2112.09542/) (2021)
- [Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes](https://mlsanity.com/paper/2302.06760/) (2023)
- [The Power of Two Choices in Distributed Voting](https://mlsanity.com/paper/1404.7479/) (2014)

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

- [A Generalisation of Voter Model: Influential Nodes and Convergence Properties](https://mlsanity.com/paper/2411.04564/) (2024)

## Abstract (arXiv)

Consider a directed network where each node is either red (using the red product), blue (using the blue product), or uncolored (undecided). Then in each round, an uncolored node chooses red (resp. blue) with some probability proportional to the number of its red (resp. blue) out-neighbors. What is the best strategy to maximize the expected final number of red nodes given the budget to select k red seed nodes? After proving that this problem is computationally hard, we provide a polynomial time approximation algorithm with the best possible approximation guarantee, building on the monotonicity and submodularity of the objective function and exploiting the Monte Carlo method. Furthermore, our experiments on various real-world and synthetic networks demonstrate that our proposed algorithm outperforms other algorithms. Additionally, we investigate the convergence time of the aforementioned process both theoretically and experimentally. In particular, we prove several tight bounds on the convergence time in terms of different graph parameters, such as the number of nodes/edges, maximum out-degree and diameter, by developing novel proof techniques.