Beyond Fixed Budgets: Maximizing the Profit/Cost Ratio in Viral Marketing

TL;DR

Viral marketing is no longer just about picking $k$ people to start a trend. This paper introduces a General Ratio Maximization (GRM) framework that treats the budget as a flexible variable. By optimizing the Profit/Cost ratio, the authors account for the influence of existing products and reward intermediate "influencers," achieving superior efficiency on million-node social networks.

The Problem: The Arbitrary "k" and the Multi-Product Reality

Most classic Influence Maximization (IM) research asks: "Given $k$ seeds, how do we maximize spread?" But for a real-world CMU, setting $k=100$ or $k=1000$ is often a shot in the dark.

Moreover, users don't exist in a vacuum. If a user already owns a 4K monitor, they are more likely to buy a high-end GPU (positive complementarity) but less likely to buy another monitor (negative competition). Current models largely ignore these cross-product impacts and the fact that intermediate users who help spread the message—not just the initial seeds—deserve a slice of the reward.

Methodology: Redefining Influence and Profitability

The authors propose a general influence measure $I_{uv}(A)$ that combines:

1. Topology & Intimacy: Based on interaction frequency rather than just binary connections.
2. Product Awareness: A term $\sum p_{Aj}$ that captures the willingness to adopt product A given existing products $j$.

The Objective Function

Instead of maximizing influence $(\sigma )$, they maximize the ratio: $o_A(S)=\frac{extProfit(S)}{extCost(S)}$ Where Cost includes rewards for initial seeds and intermediate influencers who successfully convert others.

The SmoothGreedy Algorithm

The challenge? This ratio is non-monotone submodular. Adding a seed might actually decrease your efficiency. The authors use a double-greedy approach with a probabilistic "smooth" decision-making process.

Figure 1: The dual-factor influence model accounting for social intimacy and product coexistence.

Scalability through MapReduce

To handle graphs like the 4.8M node LiveJournal dataset, the authors designed DismoothGreedyGRM. They solve the "serialization bottleneck" of greedy algorithms by treating selection actions as transactions and using a MapReduce framework to filter and select candidates in parallel.

Figure 2: The iterative MapReduce workflow for parallelizing seed selection.

Experiments and Results

The researchers tested their approach against SOTA baselines (CELF, PMIA, IMM).

• Efficiency: As the cost of seeds $(\gamma )$ increases, SmoothGreedyGRM maintains a significantly higher profit/cost ratio, while fixed-budget models see their efficiency plummet.
• Speed: Their linear-time complexity ensures constant running time regardless of the seed set size, unlike traditional greedy methods where time grows with $k$.

Figure 3: Performance comparison showing SmoothGreedyGRM's resilience to rising seed costs.

Critical Insight & Future Work

The core value of this work is the abandonment of the fixed budget. By proving that the profit/cost ratio inherits submodularity, the authors provide a mathematically grounded way to find the "sweet spot" of marketing spend.

Limitations: The model assumes we have access to user-product interaction data $(p_{ij})$, which may be proprietary or difficult to obtain in cross-platform marketing. Future research could explore Transfer Learning to estimate these weights across different social domains.

Conclusion

This paper represents a shift towards Cost-Efficient AI in marketing. It successfully bridges the gap between theoretical submodular maximization and the practical complexities of modern online ecosystems.