MIMP: Decoding the Complexity of Multi-Attribute Viral Marketing

TL;DR

Most viral marketing research assumes a product is a single "point" of influence. This paper argues that products are actually clusters of multiple attributes (e.g., a phone's camera, battery life, and price) that propagate independently. By introducing the Multi-attribute based Influence Maximization Problem (MIMP) and the MIC model, the authors tackle the mathematical "nightmare" of non-submodularity using a clever Sandwich Approximation Algorithm.

Problem & Motivation: Beyond the "Single Information" Myth

In the classic Independent Cascade (IC) model, the goal is simple: pick $k$ seeds to maximize the expected number of influenced nodes. This works if you're spreading a single meme or a simple link. But what if you're selling a high-end car?

One customer might care about safety, while another cares about acceleration. A purchase only happens when a user identifies enough attributes to satisfy their personal "buy" threshold. Mathematically, this shifts the problem from submodular (where diminishing returns apply) to non-submodular. In non-submodular settings, the classic Greedy Algorithm—the industry standard—loses its guaranteed $1-1/e$ performance bound.

Methodology: The MIC Model and the Sandwich Strategy

1. The MIC Model (Multi-dimensional IC)

The authors extend the IC model by treating each attribute as a separate dimension.

• Independent Diffusion: Attribute $A$ and Attribute $B$ spread through the same social edges but with different probabilities ($p_{uv}^1,p_{uv}^2,...$).
• Node Decision: A node $v$ is activated only if the weighted sum of accepted attributes exceeds a threshold $het{a}_v$: $\sum w_{\varphi }\ge het{a}_v$

2. Overcoming Non-Submodularity

Since the problem is non-submodular, the authors use the Sandwich Approximation. They "trap" the complex MIMP objective function ($f$) between two simpler, submodular functions:

• Lower Bound ($\underline{f}$): A restrictive scenario where a user only buys if all attributes are accepted.
• Upper Bound ($\bar{f}$): A permissive scenario where a user buys if at least one attribute is accepted.

Note: The framework relies on solving these bounds via greedy selection to estimate the optimal seed set $S$.

Experiments: Performance at Scale

The authors tested their algorithm on the NetScience (co-authorship) and Wikivote datasets.

Key Findings:

1. Correctness: The performance of the Sandwich Algorithm (red/blue lines in the paper's actual plots) consistently sits between the theoretical upper and lower bounds.
2. Superiority: Even though the problem is harder, the proposed method significantly outperforms Max Degree (picking the most connected people) and Random selection.
3. Attribute Sensitivity: Adding more attributes increases the gap between the upper and lower bounds, suggesting that product complexity makes strategic seed selection even more critical.

As the budget $k$ increases, the influence spread of the Sandwich Algorithm grows more steeply compared to traditional baselines.

Critical Analysis & Conclusion

The MIMP framework is a significant step toward making Influence Maximization realistic. Commercial products are rarely one-dimensional. However, the model assumes attributes propagate "independently," which might not be true—seeing a "high price" attribute might affect how a user perceives a "high performance" attribute (the Halo Effect).

Takeaways for Researchers:

• Don't assume submodularity: If your model involves complex decision thresholds (like multi-attribute logic), your standard greedy algorithm might be failing you.
• The Sandwich Strategy is powerful: When an objective function is messy, find its "conservative" and "optimistic" submodular cousins.

Future Work

The next frontier is likely correlated attribute diffusion, where the success of one attribute's spread influences the probability of another, or incorporating dynamic weights that change as the "viral" campaign progresses.