MIMA: Redefining Influence Maximization Through Multiple Acceptances and Diminishing Returns

TL;DR

Most social influence research asks: "How many people can we activate?" This paper asks: "How many times will the network accept our product?" By introducing the MIMA (Multiple Influences and Multiple Acceptances) model, the authors bridge the gap between social network analysis and economic principles like Diminishing Marginal Utility, providing a more robust framework for real-world viral marketing.

Background & Positioning

Influence Maximization (IM) has long been dominated by the Independent Cascade (IC) and Linear Threshold (LT) models. These models are inherently binary—once a node is "active," the story ends. However, in retail or services, customer lifetime value depends on repeat purchases. MIMA is a pioneering effort to quantify total adoption volume rather than just a simple count of unique adopters.

The Core Challenge: The "Diminishing" Reality

In the real world, two things happen as you buy more of a product (e.g., a specific brand of toothpaste):

1. Expertise Gain: You might become more persuasive to your friends since you are a frequent user. But your 10th purchase doesn't make you proportionally more persuasive than your 1st.
2. Satiety/Threshold: You are less likely to buy another tube if your cupboard is already full.

Traditional models ignore these dynamics. The MIMA model formalizes these using an exponential decay function: $h(x)=\alpha (1-\exp (-\beta x))$ Where $\alpha$ and $\beta$ control the upper bound and the rate of diminishing returns.

Methodology: The MIMA Framework

The paper defines the Acceptance Volume Maximization Problem, which aims to select $k$ seeds to maximize the expected total volume of acceptances across the entire network.

1. Model Architecture

The propagation process is iterative. A node $u$ accepts an item $z$ times if the cumulative influence from its neighbors exceeds a threshold $het{a}_{u,z}$. Crucially, $heta$ is not fixed; it grows as $z$ increases, making subsequent acceptances harder.

The exponential decay function $h(x)$ used for both influence and threshold curves.

2. Algorithmic Solutions

• GREEDY (Algorithm 1): Uses Monte Carlo simulations to pick nodes. While it guarantees a $(1-e^{-1}-ϵ)$ approximation, it is computationally expensive ($O(n^3)$).
• HEUR (Algorithm 3): A smarter heuristic that estimates influence spread using dynamic programming. It calculates acceptance probabilities per node and aggregates them without full-scale simulation, drastically improving speed.

Experimental Insights

The authors tested MIMA on Twitter and Brightkite datasets.

Performance Comparison

Experiments compared MIMA against DEGREE-DISCOUNT and ONE-WAVE-DIFFUSION.

• Superior Spread: GREEDY and HEUR consistently reached higher total volumes.
• Efficiency: HEUR demonstrated a remarkable balance, being nearly as fast as simple degree-based methods while maintaining high accuracy.

Figure: Comparison on Brightkite and Twitter shows HEUR (Heuristic) closely trailing GREEDY while outperforming traditional benchmarks.

Critical Analysis & Takeaways

The strength of this paper lies in its economic grounding. By treating influence as a submodular function of acceptance volume, it proves that local greedy choices still lead to globally competitive results.

Limitations:

• The model assumes a static network. In real-world multi-purchase scenarios, network edges might evolve over time.
• The parameters $\alpha$ and $\beta$ are assumed to be known or sampled, but in practice, estimating these from historical purchase data is a separate, complex challenge.

Summary

MIMA moves the needle for IM research by reflecting the "volume-based" nature of modern commerce. For researchers and product markers, it provides a rigorous mathematical path to optimize not just for reach, but for total market penetration.