BCT: Revolutionizing Viral Marketing with Cost-Awareness and Billion-Scale Efficiency

TL;DR

Viral marketing research has long been stuck in the "Influence Maximization" (IM) paradigm, which naively assumes every user costs the same to recruit and provides equal value. This paper breaks that mold by introducing Cost-aware Targeted Viral Marketing (CTVM). The authors present BCT, an algorithm that scales to billion-edge networks (like Twitter), providing theoretically grounded results while running up to 4x faster than previous state-of-the-art methods.

Background: Why High Influence Doesn't Mean High Value

In traditional IM, the goal is simple: pick $k$ users to reach the maximum number of people. However, this produces two major "real-world" failures:

1. The Celebrity Problem: Algorithms often pick users like Katy Perry or Barack Obama as seeds. While influential, their cost of acquisition is prohibitive for most brands.
2. The Wrong Audience Problem: Maximizing raw reach might sweep in millions of users who have zero interest in the product being marketed.

The authors' insight is that we should optimize for Benefit (the value of target audiences) relative to Cost (the price of seed nodes).

Methodology: The Power of Benefit Sampling

The core of BCT lies in its Benefit Sampling Algorithm (BSA). Standard Reverse Influence Sampling (RIS) picks a random node and sees who can reach it. BCT improves this by picking "source" nodes with a probability proportional to their benefit $b(u)$.

1. Architecture and Logic

By weighting the sampling toward high-value targets, BCT constructs a hypergraph $H$ that more accurately reflects the "benefit landscape" of the network.

Above: The theoretical threshold $heta$ ensuring approximation guarantees.

2. The Stopping Rule

BCT doesn't just guess how many samples to take. It uses a dynamic stopping condition. It doubles the number of hyperedges in each round until the seed set coverage exceeds a calculated threshold ${\Lambda }_L$. This ensures the algorithm uses the minimal number of samples necessary to guarantee accuracy.

The mathematical proof showing that Benefit $B(S)$ can be accurately estimated through BSA sampling.

Experiments: Billion-Scale Performance

The authors tested BCT on the massive Twitter-2010 dataset (41.7M nodes, 1.5B edges).

Key Findings:

• Speed: Under the Linear Threshold (LT) model, BCT is the first sub-linear time algorithm for dense graphs because its complexity is independent of the number of edges.
• Quality: BCT significantly outperforms IM and Budgeted IM (BIM) because it intelligently avoids "expensive but low-relevance" nodes.

Figure 1: Comparison between BCT and baselines. BCT (dark color) consistently captures higher benefit for the same budget.

In a case study on trending topics (e.g., "Obama," "Marvel"), BCT identified local influencers—users with only a few thousand followers but extremely high activity and relevance—rather than just the most popular accounts.

Critical Insight: The Shift to Precision Marketing

The significance of this work is its shift from volume to value. By proving that we can maintain a $(1-1/e-ϵ)$ approximation ratio while accounting for heterogeneous costs, the authors have moved viral marketing from a theoretical exercise into a practical tool for data-driven ROI.

Limitations: While the LT model performance is stellar, the IC (Independent Cascade) model still requires more computational overhead per sample, though BCT remains the most efficient option currently available for that model as well.

Conclusion

BCT is a masterclass in algorithm optimization, combining statistical sampling theory with practical marketing constraints. For anyone working with billion-scale graphs, BCT offers a roadmap for efficient, value-driven influence analysis.