RevMax: Monetizing the Social Graph via Competitive Viral Marketing

TL;DR

Social network hosts like Meta or LinkedIn frequently run simultaneous ads for competing products (e.g., Xbox vs. PlayStation). This paper shifts the focus from traditional "influence spread" to Host Revenue Maximization. It tackles the NP-hard, non-submodular challenge of assigning non-overlapping seed users to multiple campaigners, providing both theoretically grounded approximations and highly scalable greedy heuristics.

Context: Why Traditional Viral Marketing Fails the Host

In the classic viral marketing setup, a single company identifies $k$ influencers to maximize product adoption. However, in the real world:

1. Host Secrecy: The social graph is a "black box" held by the host. Campaigners only provide target user lists and bid values.
2. Competition: Users are unlikely to buy two competing products. If a user adopts Campaign A, they are "lost" to Campaign B.
3. Targeting: Different campaigners value different users differently. A banking professional is worth more to a fintech app than to a gaming company.

Existing solutions often aim for "fair spread" among clients, but for a platform host, Total Expected Revenue is the ultimate metric.

The Technical Core: Solving the NP-Hard Puzzle

The authors tackle the problem under the two pillars of influence theory: Independent Cascade (IC) and Linear Threshold (LT) models. Both versions are NP-hard and lose the "submodularity" property that usually allows simple greedy algorithms to perform well.

1. The IC Model: Most Influential Tree Extraction

To make the problem tractable, the authors propose extracting the Most Influential Tree (MIT). By transforming a complex graph into a directed spanning tree that preserves high-probability paths, they can apply a Dynamic Programming (DP) approach.

The DP state tracks the best revenue for a subtree given that a specific ancestor was chosen as a seed. While this is exponential in the number of campaigners, it is polynomial for the number of nodes, making it a powerful tool for localized clusters.

2. The LT Model: Optimistic Partitioning

For the LT model, the authors introduce a brilliant insight: Individual Revenue.

• Phase 1 (Optimistic Selection): Assume each node will be won by the highest-paying campaigner. Use a standard $1-1/e$ greedy algorithm to pick $mimesk$ global seeds.
• Phase 2 (Optimal Partitioning): Once the global seeds are picked, how do we split them? Since the total activation probability in LT models is linear across seeds (Proposition 2), the host can use DP to assign each seed to the advertiser that yields the highest "marginal individual revenue."

Experimental Results & Scalability

The researchers tested their methods on datasets like Flickr (20M edges) and DBLP.

Key Findings:

• RevMax-C (Combined): consistently beats greedy benchmarks by a healthy margin but struggles with a high number of seeds (due to the DP complexity).
• RevMax-S (Separate): A simplified greedy version that deletes nodes after assignment. While it lacks the theoretical "tightness" of RevMax-C, it scales linearly, making it the practical choice for networks with millions of users.

Critical Analysis & Takeaways

The brilliance of this work lies in the Individual Revenue decomposition. By proving that the expected revenue from a set of seeds is simply the sum of individual revenues under the LT model, they turned a combinatorial nightmare into a partition problem.

Limitations: The MIT extraction for the IC model simplifies the graph significantly. In highly dense graphs with many redundant paths, this might underestimate the secondary "ripples" of influence.

Future Outlook: As privacy regulations like GDPR limit the data advertisers can see, "Seed Selection as a Service" by the host—using these RevMax algorithms—is likely to become the standard for social platform monetization.