RMG: Mastering Multi-Product Profit Maximization in Social Networks

TL;DR

The PM2A problem moves beyond simple "influence spread" to "profit optimization." The proposed Randomized Modified Greedy (RMG) algorithm utilizes Reverse Influence Sampling (RIS) to achieve a (1 - 1/e - ε) approximation—the theoretical upper bound for this NP-hard problem. It effectively solves the challenge of distributing a single budget across multiple products with different costs and rewards.

Context & Motivation: Why One Product Isn't Enough

Classic Influence Maximization (IM) asks: "Which $k$ nodes reach the most people?" In reality, companies have a portfolio of products. A user might adopt a low-cost "entry" product or a high-profit "luxury" item.

The Problem:

1. Heterogeneity: Each product has unique activation costs ($c_i$) and profit margins ($p_i$).
2. Coupled Budget: A single budget $B$ must be split among $q$ products.
3. Submodularity: Profit isn't linear; adding seeds has diminishing returns, making the optimization complex (#P-hard).

Methodology: The Copy-Graph and RIS

1. The q-Component Copy Graph (G̃)

To handle $q$ products, the authors create $q$ identical copies of the social network $G$. A node $u$ in copy $i$ represents a user adopting product $i$. This transformation allows the PM2A problem to be viewed as a single submodular maximization task over the composite graph $ildeG$.

2. Randomized Modified Greedy (RMG)

The core of RMG is a "Modified Greedy" approach. Standard greedy can fail when some nodes are extremely expensive but profitable. RMG avoids this by:

• Enumeration: Checking all sets of size 1 and 2 first.
• Cost-Effective Selection: Greedily adding nodes based on the ratio of marginal profit gain to cost.
• RIS Sampling: Using Random Reverse Reachable (RR) sets to estimate influence without expensive Monte Carlo simulations.

Experimental Validation

Testing on NetHEPT, wikiVote, and Epinions (up to 75k nodes and 500k edges), RMG consistently beat benchmarks like PMCE and standard greedy heuristics.

Key Observations:

• Superior Profit: RMG achieves significantly higher profit as the budget increases, widening the gap with baseline methods.
• Smart Allocation: As shown in the budget distribution plots, the algorithm initially targets products with the highest profit-to-cost ratio. As those reach saturation (diminishing returns), RMG pivots the remaining budget to secondary products.

Critical Insight: RefOPT Estimation

One of the paper's strongest contributions is Algorithm 5 (Refined OPT Estimation). The efficiency of RIS depends on the number of samples $heta=\lambda /OPT$. If $OPT$ is underestimated, we sample too much (slow); if overestimated, we lose accuracy. RefOPT uses a greedy knapsack-style pre-selection to find a tight lower bound for $OPT$, ensuring RMG is both fast and accurate.

Conclusion & Future Work

The RMG algorithm sets a new benchmark for multi-adoption profit maximization. By proving a (1 - 1/e - ε) ratio, it reaches the theoretical limit of what can be computed in polynomial time.

Future Directions:

• Competition: How does the algorithm change if Product A and Product B are competitors (adopting A prevents adopting B)?
• Scalability: While efficient, the $n^4{q}^8$ theoretical complexity bound suggests there is still room for optimization in extremely high-dimensional product spaces.

Academic Reference

Tiantian Chen et al. "A random algorithm for profit maximization in online social networks." Applied Soft Computing (2019).