Beyond Reach: Optimizing the Bottom Line in Viral Marketing via Submodular Maximization

TL;DR

While most research focuses on Influence Maximization (getting the most views), this paper tackles the more practical problem of Profit Maximization. By treating viral marketing as an unconstrained submodular optimization task, the authors introduce a Double Greedy framework with Iterative Pruning that guarantees high-profit seed selection even in billion-scale networks.

Context: Why "Most Influential" Isn't Always "Most Profitable"

In the classic viral marketing paradigm, we assume a fixed budget (e.g., "pick 50 users") and try to maximize reach. However, in reality, every seed user has a cost (incentives, free samples), and every activated user provides a benefit. If you pay a high-cost influencer whose audience overlaps significantly with others, your net profit might actually drop.

The mathematical challenge? Non-monotonicity. While influence spread always increases as you add more seeds, Profit ($\varphi (S)=\beta (S)-c(S)$) does not. Adding seeds past a certain point leads to diminishing returns that No longer cover the costs.

Methodology: The Double Greedy Strategy & Iterative Pruning

The authors identify that Profit is a submodular function. To solve it, they move away from simple hill-climbing (which fails for non-monotone functions) and adopt the Double Greedy approach.

1. The Iterative Pruning Technique

Because checking every node in a network of millions is expensive, the authors propose a "Warm-Start" via pruning. By examining marginal gains at the empty set and the full set, they identify:

• A*: Nodes that must be in the optimal set.
• B*: Nodes that might be in the optimal set.

This prunes the search space from the entire graph $V$ to the subset $B^{\ast }\setminus A^{\ast }$.

2. Double Greedy (DG)

The algorithm maintains two sets ($S$ and $T$) and iterates through nodes. It makes a decision for each node based on the relative marginal gain of adding it to $S$ versus removing it from $T$.

The pruning process relies on these submodular inequalities to guarantee that no potential global maximizers are lost.

Experiments: Performance on Large-Scale OSNs

The authors tested their algorithms on datasets ranging from Facebook (4K nodes) to LiveJournal (5M nodes).

Key Insights from Results:

1. Robustness across Cost Models: In "Degree-Proportional" costs (where influencers are expensive), traditional algorithms (IMM/BCT) failed significantly, often resulting in negative profits because they over-prioritize expensive high-degree nodes.
2. Efficiency: The DGIP algorithm handles 5 million nodes in under 600 seconds, making it production-ready for large social platforms.
3. Tighter Bounds: The authors derived instance-specific upper bounds. For most cases, their algorithm achieved results within 76%-90% of the theoretical maximum profit.

Comparison of profits: Notice how our greedy approaches (SGIP/DGIP) maintain peak performance while baselines like IMM drop significantly as costs vary.

Critical Analysis & Takeaways

The brilliance of this work lies in the Iterative Pruning. By bridging the gap between theoretical submodular optimization and the practical realities of Online Social Networks (OSNs), the authors solved the "negative profit" trap that many viral marketing campaigns fall into.

Limitations: The model assumes we know the costs and benefits per user accurately. In practice, estimating the "benefit" of a user activation ($b(v)$) is a separate challenge involving complex attribution modeling.

Conclusion

This paper shifts the viral marketing conversation from "how many" to "how much." By utilizing the submodular properties of profit, the DGIP algorithm provides a scalable, theoretically grounded framework for any company looking to maximize their ROI on social influence.