AlgCP: Maximizing Host Profit in Billion-Scale Competitive Viral Marketing
Host Profit Maximization for Competitive Viral Marketing in Billion-Scale Networks
The paper introduces CPro (Competitive Profit Maximization), a framework for social network hosts to maximize commission-based revenue from multiple competing campaigners. The authors propose AlgCP, a randomized approximation algorithm that achieves a provable performance bound on billion-scale networks, such as Twitter.
TL;DR
The research addresses a critical gap in social media advertising: how a network host (like Facebook or Twitter) can maximize total commission from multiple competing advertisers (campaigners). By introducing the CPro problem and the AlgCP algorithm, the authors provide the first scalable, randomized approximation solution that works on graphs with billions of edges, completing computations in minutes where previous methods would fail.
Problem & Motivation: The Tug-of-War for Users
In the real world, viral marketing isn't a solo game. Companies like Apple and Samsung compete for the same set of "influential" users. Previous research typically assumed:
- Only one company is marketing.
- Or, all players have full knowledge of the network.
The Reality Check: Network hosts treat their graphs as "trade secrets." Campaigners pay a commission only when a target user adopts their product. This creates a messy mathematical landscape: the host's profit function is non-monotone (adding a seed can sometimes decrease total profit due to competition) and non-submodular (the "diminishing returns" rule doesn't strictly apply).
Methodology: The Two-Stage Scalable Engine
The core challenge is solving an NP-hard problem without the usual submodular "safety net." The authors break the problem into two distinct phases.
1. Myopia Overall Seed Selection (MOS)
Instead of figuring out which campaigner gets which seed immediately, MOS identifies a general set of high-value seeds. It uses Reverse Reachable (RR) sets—a technique where we start from a random node and trace backward to see who could have influenced it.
The logic relies on Lemma 1, where the probability of a seed set intersecting an RR set is proportional to its total expected profit.
2. Seed Set Partition (SePar)
Once the top seeds are found, the host must decide which campaigner "owns" which seed. The authors prove that the profit of each seed can be isolated once the total seed set is fixed. They use Dynamic Programming to find the optimal partition, ensuring the host allocates seeds to the campaigners willing to pay the highest commissions for the resulting influence.
Experimental Results: Performance at Scale
The authors tested AlgCP on datasets ranging from small citation networks (NetHEPT) to the massive Twitter graph (42M nodes, 1.5B edges).
Efficiency and Profit Results
On the billion-edge Twitter network, AlgCP identifies top seeds in only a few minutes.
| Dataset | AlgCP Profit () | Random Profit () |
|---|---|---|
| Epinions | 74K | 0.4K |
| Orkut | 196K | 0.8K |
| 6.3K | 0.32K |
Comparison shows AlgCP providing 15x to 100x more profit than random baselines.
Figure (a): Running time remains manageable even as the network scales to billions of connections.
Critical Insight & Future Outlook
The brilliance of this work lies in the K-LT model extension. By recognizing that an influenced node's choice is based on the relative influence strength of competitors, the authors were able to isolate seed profits (Proposition 1). This isolation is what allows the algorithm to scale; without it, the inter-dependencies between seed choices would grow exponentially.
Takeaway for Industry: For platforms managing "multi-tenant" ad campaigns, this algorithm provides a robust way to ensure the platform maximizes its own bottom line while maintaining a fair, commission-based environment for advertisers. Overcoming the non-submodularity of competitive influence marks a significant theoretical and practical milestone.