CAM: Maximizing Social Activity Through Continuous Marketing Strategies

TL;DR

Social network optimization is moving beyond just "counting influenced nodes." This paper introduces Continuous Activity Maximization (CAM), a framework that treats marketing as a continuous investment (lattice-based) rather than a binary selection. By proving the non-submodularity of activity benefits and introducing a Sandwich Approximation Framework with specific sampling techniques (RE/RN), the authors solve a complex NP-hard problem with scalable, theoretically guaranteed algorithms.

Context: From Binary Influence to Continuous Activity

Standard Influence Maximization (IM) asks a simple question: Which $k$ nodes should we trigger to reach the most people? However, in the real world:

1. Edges aren't equal: Interacting with a close friend might generate more "activity benefit" (profit) than a casual acquaintance.
2. Strategies aren't binary: You don't just "pick" a user; you offer them a 20% discount, a 50% coupon, or a free trial—each with a different probability of success.

The CAM problem addresses these gaps by modeling marketing strategies as $d$-dimensional vectors $\mathbf{x}$ on a lattice $\mathcal{X}$.

The Mathematical Challenge: Why Greedy Isn't Enough

In traditional IM, the objective function is submodular (the law of diminishing returns applies). In CAM, the objective function $f_c(\mathbf{x})$ is monotone but neither DR-submodular nor DR-supermodular.

Specifically, the "combination effect"—where two seeds together activate a high-value edge that neither could reach alone—breaks the submodularity. Without this property, a standard greedy algorithm loses its $(1-1/e)$ guarantee.

Methodology: The Sandwich & Sampling Strategy

The authors propose a multi-step solution to bypass the lack of DR-submodularity:

1. The Sandwich Framework

Since $f_c(\mathbf{x})$ is hard to optimize directly, the authors define:

• Lower Bound ($\underline{f_c}$): Only counts edges where both endpoints are activated by the same seed.
• Upper Bound ($\overline{f_c}$): Relaxes the requirement, allowing any influenced node to contribute to half of its connected edge activity.
• Finding the Solution: Both bounds are DR-submodular. By maximizing these, we "sandwich" the optimal solution.

2. Scalable Sampling (RE & RN Sampling)

To handle massive networks, the authors adapt Reverse Influence Sampling (RIS):

• RE-sampling (Random Edge): Estimates the main objective and lower bound by sampling high-value edges and generating reverse-reachable sets.
• RN-sampling (Random Node): Specifically designed for the upper bound's node-centric structure.

Formula 5: The continuous activity function reflecting the total expected benefit across all possible seed sets $S$ generated by strategy $\mathbf{x}$.

Experimental Insights

The authors tested their framework using Dataset-3 (Arxiv collaboration), Dataset-2 (Wiki), and Dataset-1 (Co-authorship).

Key Results:

• Superiority over Baselines: The Sandwich approach consistently yielded higher activity benefits than MaxDegree or Random strategies.
• Performance Stability: While MaxDegree and IM fluctuated depending on the dataset type, the CAM algorithm remained robust due to its data-dependent approximation ratio.

Figure: Performance on Dataset-3 under the IC-model, showing the Sandwich algorithm outperforming traditional heuristics as the budget increases.

Critical Analysis & Future Outlook

While the paper provides a breakthrough for lattice-based optimization in social networks, there are a few considerations:

• Complexity: Creating a constructed graph for Monte Carlo simulations (as suggested in Remark 2) adds overhead, though the RIS-based IMM adaptation mitigates this significantly.
• Granularity Trade-off: The accuracy depends on the granularity $t$. A very small $t$ (near-continuous) increases the number of greedy iterations ($k/t$), which might challenge real-time applications.

Conclusion: This work is a significant milestone for "Viral Marketing 2.0." It proves that we can optimize complex, non-submodular rewards in social networks using disciplined mathematical bounds and modern sampling techniques.