B-IMCP: Mastering Viral Marketing through Cross-Sell Dynamics

TL;DR

Marketing a single product in a vacuum is a luxury few companies have. Most businesses manage portfolios where products like computers and printers, or machine learning and statistics books, are intrinsically linked. This paper introduces the B-IMCP (Budgeted Influence Maximization with Cross-sell of Products) problem. It moves beyond the classic "who are the top-k influencers" question by integrating product costs, profit benefits, total budgets, and cross-sell triggers into a unified mathematical framework.

Problem & Motivation: The Reality of the "Cross-Sell"

Previous SOTA (State Of The Art) research treated products as independent entities. If you were marketing a laptop and a printer, you'd find the best seeds for the laptop and the best for the printer separately.

The authors argue this is inefficient. In reality:

1. Threshold Lowering: If a friend buys a Mac, you are more likely to buy an iPhone. Your "threshold" for the second product drops because of the first.
2. Budget Tension: A company only has \X$ to spend. Should they give away 10 expensive laptops or 50 cheap printers?
3. Influence Decay: The further a recommendation travels from the original seed, the weaker it becomes.

Methodology: The LT-CP Model

The core of this paper is the Linear Threshold for Cross-sell of Products (LT-CP) model.

1. Modeling Interaction

The authors use a bipartite graph $H=(P1,P2,C)$ to represent cross-sell relationships between two sets of products.

• Must-Buy: You only consider Product B after purchasing Product A (e.g., Video Game Console $\to$ Controller).
• May-Buy: Purchasing A simply lowers your resistance to buying B (e.g., Statistics Book $\to$ Machine Learning Book).

2. The Math of Decay and Thresholds

Unlike standard models, the influence of node $j$ on node $i$ is scaled by $(1-L(j)\delta -\delta )$, where $L(j)$ is the distance from the seed. This captures the "dilution" of word-of-mouth as it passes through strangers.

3. The Greedy Approximation

Since the problem is NP-hard, the authors utilize a greedy strategy. Because of the budget constraint, the feasible set is not a simple matroid but a p-system. This allows the authors to prove a competitive ratio that depends on the ratio of maximum to minimum product costs ($\alpha =c_M/c_m$).

Fig 1: Two types of cross-sell graphs: (i) complete bipartite and (ii) one-to-one.

Experiments & Deep Insights

The authors tested their algorithms on real-world graphs, including the WikiVote trust network and Telco call records (354k nodes).

Key Findings:

• Cross-sell Leveraged Revenue: Using the cross-sell relationship produces significantly higher revenue (sometimes >50% increase) compared to treating products as independent.
• Seed Overlap: When cross-selling is strong (lowered thresholds), the optimal strategy is to have a high overlap between the seeds of both products. You essentially target the same group of influencers to kickstart a multi-product cascade.
• Distance: As cross-sell potential weakens, seeds must be spread further apart geographically or socially to capture more "fringe" adopters.

Fig 2: Performance comparison of Greedy (GA) vs. Heuristics. GA consistently leads in revenue across different datasets.

Critical Analysis & Conclusion

Takeaway

The paper effectively bridges the gap between theoretical influence maximization and practical retail marketing. The insight that buying history can be used to mine association rules to set influence thresholds is a powerful application for e-commerce.

Limitations

• Negative Influence: The model assumes all word-of-mouth is positive. In the real world, a bad review for the "anchor" product (P1) would likely kill the cross-sell potential for P2.
• Computation: The greedy algorithm, while accurate, remains slow for massive networks. The authors proposed a Maximum Influence Heuristic (MIH), but even this struggles at the million-node scale.

Future Outlook

The next frontier is a model that integrates competitor influence. If I buy Amazon's Kindle, I am effectively "blocked" from my threshold lowering for a Nook. Combining cross-sell dynamics with competitive "blocking" is the missing link for a perfect market simulation.