STAB: Reaching the Viral Tipping Point with Minimal Cost and Maximum Scale

TL;DR

In viral marketing, the question isn't always "How much reach can I get for $10k?" but often "How many influencers do I need to guarantee 100,000 users?" This is the Threshold Activation Problem (TAP). This paper presents STAB, the first scalable, parallelizable algorithm for TAP that handles networks with millions of nodes and accounts for external influence (e.g., TV ads or external news), outperforming existing state-of-the-art algorithms by up to 1,000x.

The "Why": Why TAP isn't just Inverse Influence Maximization

Most research focus has been on Influence Maximization (IM): Given budget $k$, maximize influence $\sigma (S)$. However, businesses often have target-based KPIs (Threshold $T$).

Current SOTA algorithms like IMM or TIM are built for IM. When forced to solve TAP (usually via binary search on $k$), they become incredibly inefficient. Moreover, these models ignore External Influence—the reality that people don't just buy things because of friends; they also buy things because of external media.

The Breakthrough: Generalized Reachability

The authors bridge the gap between complex stochastic diffusion models (like Independent Cascade or Linear Threshold) and simple graph reachability. They prove that the Triggering Model is equivalent to Generalized Reachability.

Core Logic:

1. Oracles: Instead of running heavy Monte Carlo simulations, they use Sketch-based estimators (bottom-k ranks).
2. External Influence Integration: They model external activation as a set $A^{ext}$. The internal influence is then calculated on a "residual" graph $H_i$ where externally activated nodes are already accounted for.
3. Bicriteria Guarantee: Users provide a parameter $\alpha$. STAB guarantees:
   • Activation: $\ge T-2\alpha T$
   • Seed Set Size: $\le (1+4\alpha T+\log T)imesOPT$

Figure 1: STAB transforms the problem into a series of sketch-based reachability queries on sampled graphs.

Methodology: The STAB Algorithm

The algorithm follows a greedy approach but replaces the "expensive" evaluation of marginal gain with an "efficient" sketch estimation.

• Phase 1 (Oracle Construction): Sample l graphs and compute reachability sketches. This is highly parallelizable.
• Phase 2 (Greedy Selection): Pick nodes that maximize the marginal gain in the sketch.
• Two Estimators:
  • C1: Blazing fast but loses accuracy as the seed set grows.
  • C2: Slower but provides tighter estimates for large seed sets.

Performance: Decimating the Competition

Tested on massive datasets (Youtube, Wikitalk), STAB-C2 shows remarkable efficiency.

• Scale: On the Wikitalk dataset ($2.4M$ nodes), STAB finds a solution in under 2 minutes, whereas IMM reaches memory limits or takes hours.
• Precision: IMM consistently "overshoots"—for a target $T$, it might activate $2.5imesT$ because it underestimates the power of limited seeds, wasting money. STAB hits the target with surgical precision.

Figure 2: Running time and activation vs. Threshold T. Note the logarithmic scale showing STAB's orders-of-magnitude advantage.

The "Counter-Intuitive" Finding in External Influence

In the Facebook dataset experiment, the authors found something strange: sometimes increasing external influence makes the algorithm choose MORE seeds.

• Insight: External influence can "even out" the marginal gains across the network, making it harder for the greedy algorithm to distinguish the "true" influencers from average nodes, particularly when estimation errors are present.

Conclusion & Future Impact

STAB represents a shift from theoretical IM toward pragmatic, target-driven viral marketing. By effectively combining internal social "triggers" with external "shocks" and using sketch-based estimation, it proves we don't need to choose between mathematical rigor and massive scale.

Future Work: Integrating cost-aware models (where different nodes cost different amounts) into the STAB framework could further optimize real-world marketing budgets.