Beyond Buzz: Maximizing Profit in Social Networks through LT-V Modeling

TL;DR

While many algorithms focus on making a product "go viral," few address whether that virality actually translates into dollars. This paper introduces ProMax, a framework that bridges the gap between social influence and economic adoption. By modeling user valuations and dynamic pricing, the authors present PAGE, an algorithm that seeks the "sweet spot" of discounts to maximize net profit rather than just the number of active nodes.

Background: The Price of Popularity

In the world of Influence Maximization (InfMax), the goal has traditionally been simple: pick $k$ seeds to infect the most people. However, real-world examples like the iPhone versus cheaper competitors or the fire-sale success of the HP TouchPad prove that influence $eq$ adoption. An individual might be fully aware of a product via their social circle but refuse to buy it because the price exceeds their personal valuation.

The Problem: The Monetary Blind Spot

Existing models (LT, IC) treat adoption as a binary state triggered by influence. They ignore:

1. Valuations: Every user has a maximum price they are willing to pay.
2. Acquisition Costs: Marketing to seeds isn't free.
3. The Pricing Dilemma: Higher prices increase per-unit profit but kill the cascade; lower prices boost the cascade but may lead to net losses.

Methodology: The LT-V Model and PAGE

The researchers extend the Linear Threshold model into LT-V. In this model, a node transitions from Inactive $\to$ Influenced $\to$ Adopting. Crucially, the transition to Adopting only occurs if the quoted price $p_i\le v_i$ (the user's valuation).

The PAGE Algorithm (Price-Aware GrEedy)

The core innovation is how PAGE handles the price vector. While baseline algorithms either charge everyone the "Optimal Myopic Price" (All-OMP) or give seeds away for free (FFS), PAGE evaluates the "Profit Potential" of each node.

For every candidate seed, PAGE asks: "How much should I discount this specific person to maximize the total downstream profit from everyone they might influence?" It uses numerical methods (like the Golden Section Search) to find the optimal price point for each seed during the greedy selection process.

Experiments and Results

The authors tested their approach on three major datasets: Epinions, Flixster, and NetHEPT.

Performance and Robustness

PAGE outperformed both "Always Charge" and "Always Free" strategies. It proved particularly robust in "Low-Influence" networks where giving free samples (FFS) would be a waste of money, and in "High-Influence" networks where charging full price (All-OMP) would stifle a lucrative cascade.

(Performance on Epinions-WD showing PAGE consistently leads in profit)

Strategic Pricing Intuition

One of the most interesting findings is how PAGE assigns prices over time. As shown below, initial seeds (the most influential ones) receive the deepest discounts. As the algorithm picks less influential seeds, the price gradually rises toward the Myopic Price, as these later seeds have less "cascade power" to justify a heavy discount.

(Price assigned to seeds increases as their marginal influence decreases)

Critical Insight: Why PAGE is Faster

Technically, PAGE does more work per iteration (optimizing price). However, it actually runs faster than the baselines in many scenarios. This is because by finding the "true" optimal marginal profit, the algorithm creates a clearer ranking in the priority queue used by the CELF (Cost-Effective Lazy Forward) optimization, leading to significantly fewer Monte Carlo simulations.

Takeaway and Future Work

The PAGE algorithm demonstrates that social network marketing should not be a "one-price-fits-all" endeavor. By treating pricing as a dynamic variable tailored to a user's position in the network, companies can significantly increase their ROI.

Future research directions:

• Scalability: Moving away from Monte Carlo simulations to faster heuristics like LDAG or SimPath to handle billion-scale graphs.
• Spontaneous Interest: Modeling "organic" adoption that happens outside of social influence.
• Multi-Product Competition: How to maximize profit when competitors are also offering discounts in the same network.