Maximizing Synergy: Influence Maximization for Complementary and Composite Products

TL;DR

In the world of viral marketing, products rarely exist in a vacuum. This paper tackles the complex reality of Complementary Products (where buying one leads to another) and Composite Complementary Products (CCP) (where buying a set leads to a new adoption). By introducing a multi-layer network model and the General-TIM algorithm, the authors provide a scalable framework that achieves a guaranteed approximation ratio for multi-product marketing under real-world budget (knapsack) constraints.

Problem & Motivation: The "iPhone & Airpods" Effect

Most Influence Maximization (IM) research asks: "Who should I give a free sample to, to maximize the spread of this specific product?" However, in reality, products are often linked. If you buy an iPhone, you are highly likely to buy AirPods. Alternatively, if you buy a laptop and a monitor, you might then buy a docking station.

Existing models fail because:

1. They assume products are independent.
2. They use simple cardinality constraints (e.g., "pick $k$ nodes"), ignoring that different seeds for different products have varying costs.
3. The objective function for Composite products becomes Non-Submodular, making it mathematically "unruly" to optimize.

Methodology: Multi-layers and Reverse Sampling

The authors propose a dual approach to handle these complexities.

1. The Multi-layer Construction

Each product $h_i$ is represented by a separate layer of the social network. If two products are complementary, directed edges are added between layers. This transforms the complex multi-product problem into a weighted IM problem on a much larger, consolidated graph.

Figure 1: Construction of a Multi-layer network where orange arrows represent complementary probabilities between different product layers.

2. General-TIM for Scalability

While a standard Greedy algorithm can solve submodular problems with knapsack constraints, it is too slow for large networks due to the overhead of Monte Carlo simulations. The authors introduce General-TIM, based on Reverse Influence Sampling (RIS). By generating Random Reverse Reachable (RR) sets, the problem is converted into a weighted set cover problem, allowing for near-optimal solutions in linear time.

3. The Sandwich Framework for IMCCP

When dealing with Composite Complementary Products, the influence function is no longer submodular. To solve this, the authors use the Sandwich Method:

• Upper Bound ($\gamma$): Decomposes hyperedges into multiple standard edges.
• Lower Bound ($\mu$): Prunes hyperedges that are unlikely to be activated. The algorithm picks the best solution among those optimized for the upper bound, the lower bound, and the original function.

Experiments & Results

The researchers tested their approach on co-authorship and Wiki-vote networks.

• Performance: Both Greedy and General-TIM achieved significantly higher influence spread than baseline heuristics (Max-Degree, Random).
• Efficiency: The table below illustrates the massive speedup provided by General-TIM compared to the standard Greedy approach.

Table II: Execution time (seconds). Note how General-TIM is roughly 66x faster than Greedy on Dataset-2.

Figure: The influence spread of the Sandwich Framework effectively tracks between the theoretical upper and lower bounds.

Critical Analysis & Conclusion

The primary contribution of this work is bridging the gap between theoretical IM and practical market scenarios involving bundled or related goods. By proving that the multi-layer construction preserves submodularity for simple complementary products, the authors enable the use of efficient RIS-based algorithms.

Limitations: The model assumes fixed complementary probabilities, which in reality might be dynamic or data-driven. Furthermore, while the Sandwich Framework is mathematically sound, the gap between the upper and lower bounds can vary significantly depending on the network topology.

Future Outlook: This research paves the way for "Bundle-aware" AI agents in digital marketing that can strategically allocate budgets across entire product ecosystems rather than single SKUs.