Beyond Node Counting: Maximizing Collective Profit in Social Activities

TL;DR

Most viral marketing research focuses on individual influence—how many people did we reach? This paper argues that in the real world, profit often comes from group activities (like multiplayer games or group buying). The authors define the Maximizing Activity Profit (MAP) problem, prove its complexity, and provide a set of algorithms that efficiently navigate the "non-submodular" landscape of group dynamics.

Background: Why Individual Influence is Not Enough

In classic Influence Maximization (IM), the goal is to activate the largest number of nodes. However, imagine a cooperative video game or a "team-buy" discount. If only one person is activated, the activity doesn't happen, and the profit is zero. Profit is only generated when a specific group (a hyperedge) is activated.

From an optimization perspective, this change is catastrophic. The objective function $f(S)$ is no longer submodular (the law of diminishing returns no longer strictly applies), making the standard greedy algorithm lose its theoretical guarantees.

Methodology: Taming the Non-Submodular Beast

The researchers tackle this through three distinct technical pillars:

1. Supermodular Degree & IESG

The authors use the supermodular degree ($\Delta$), which measures how much a function deviates from submodularity. By selecting a node along with its "supermodular set" (nodes that boost its marginal gain), the Improved Extendible System Greedy (IESG) algorithm achieves a solid $1/(\Delta +2)$ approximation ratio.

The logic behind calculating joint marginal gains to overcome submodularity violations.

2. Exchange Improvement (EIA)

Recognizing that greedy choices can be short-sighted, the paper introduces an Exchange Improvement Algorithm. It leverages the M-convexity of the feasible region, allowing the algorithm to swap a low-performing seed with a high-potential non-seed to iteratively climb the profit peak.

3. Randomized Variation (RV)

Calculation of expected profit in the Independent Cascade (IC) model is #P-hard. The authors solve this by using a polling-based method (Reverse Reachable sets). Instead of simulating the whole network, they sample "influential paths" in reverse, which dramatically speeds up the process.

Experimental Insights

The authors tested their methods on datasets like Facebook (dense) and Epinions (large/sparse).

• Performance: EIA and IESG consistently yielded higher profits than "InfMax" (which only looks at spread) or "DegMax" (which only looks at connections).
• Efficiency: On the Epinions dataset, the RV technique was a game-changer. As the seed set $k$ increased, the running time actually decreased because finding successful activation paths becomes statistically easier, resulting in an 89% reduction in compute time.

Comparison across Facebook, arXiv, and Epinions datasets showing the superiority of EIA and IESG.

Critical Analysis & Conclusion

Takeaway

The MAP problem is a much more realistic reflection of modern digital economies than simple node-counting. By characterizing the "synergy" between users through supermodular sets, the authors provide a bridge between theoretical social computing and practical e-commerce.

Limitations

While the supermodular degree $\Delta$ is small in the tested datasets, in highly specialized niche networks, $\Delta$ could be much larger, potentially weakening the approximation guarantee. Additionally, the model assumes activity profits are known and static, whereas in reality, user excitement might decay over time.

Future Work

The next frontier lies in Dynamic MAP, where social ties and activity profits fluctuate, requiring algorithms that can adapt in real-time to shifting user interests.

References

• Yang, W., et al. "Maximizing Activity Profit in Social Networks." IEEE Transactions on Knowledge and Data Engineering (TKDE).
• Kempe, D., et al. "Maximizing the spread of influence through a social network." KDD '03.