Beyond One-Off Clicks: Maximizing Cumulative Influence in the Era of Repeated Consumption

TL;DR

Classic Influence Maximization (IM) assumes a user is a "one-and-done" target. Once they buy a product, they are "active" and the job is finished. This paper by Zhou et al. challenges this by introducing Cumulative Influence Maximization (CIM). Using the Voter Model, they provide a mathematical bridge to model repeated activations (like daily coffee runs or monthly subscriptions) and offer an "ExactSolution" that identifies the best seeds for maximum long-term profit.

Academic Positioning: This work moves away from the NP-hard complexity of Independent Cascade (IC) models toward a more tractable, matrix-based approach for recurring viral marketing.

The Problem: The "Once-Active" Fallacy

In the literature of viral marketing, we usually assume that if a friend influences you to buy a phone, you've been "captured." But what about products like toothpaste, cigarettes, or video game microtransactions?

Existing models (IC and LT) are limited because:

1. State Persistence: They assume once you are active, you stay active forever.
2. No Re-activation: They cannot quantify the value of a user who "buys again and again."
3. Complexity: They are often NP-hard, requiring greedy approximations that are computationally expensive for large graphs.

The authors argue that the total volume of activations is a better metric for real-world ROI than simple reach.

Methodology: The Power of the Voter Model

To handle the "back-and-forth" nature of human behavior, the authors utilize the Voter Model. Unlike IC models where edges "fire" once, the Voter Model allows a node to be activated at step $t+1$ based on its neighbors' states at step $t$.

1. The Mathematical Intuition

The core insight is that cumulative influence—the expected total number of activations over $T$ steps—can be expressed as a summation of state probabilities. By representing the network as a weight matrix $W$, the authors prove that:

${\sigma }_V^T(S)={\sum }_{t=0}^T{\Pi }_0^S\cdot W^t\cdot 1$

This means the influence is not just a random simulation; it is a convergent series. If the time horizon $T$ is infinite, this simplifies beautifully into a matrix inversion: $(E-W{)}^{-1}$.

2. The ExactSolution Algorithm

Because the cumulative influence of a seed set is simply the sum of the influences of individual nodes (a property derived from the linear nature of the Voter Model), we don't need a greedy search. We simply compute a "Score" for every node and pick the Top-K.

Figure 1: The Objective Function for Cumulative Influence.

Experiments: Superior Quality at a Reasonable Cost

The authors tested their approach on datasets ranging from Facebook (4k nodes) to Epinions (51k nodes).

Key Findings:

• Performance: ExactSolution consistently beat PhaseRank and Degree-based methods. While PageRank is a decent approximation, it misses the nuances of repeated propagation over specific time horizons.
• Convergence: The cumulative influence stabilizes quickly. The difference between a limited time $T$ and $T=\infty$ is mathematically bounded, making the model robust for "short-term campaigns" (e.g., marketing ice cream in summer).

Figure 2: Performance on Facebook and Digger datasets showing ExactSolution leading the pack.

Efficiency:

While heuristic methods like "Degree" take sub-second time, they produce sub-optimal seeds. ExactSolution takes about a minute for a 50k-node graph—a very acceptable trade-off for the leap in accuracy.

Figure 3: Runtime across different datasets. ExactSolution spans the 10-100s range, making it highly practical.

Critical Insight & Conclusion

This paper is a vital reminder that the model chosen for the social dynamics dictates the complexity of the optimization. By switching to a Voter Model, the authors turned a notoriously "hard" problem (IM) into a "tractable" one (CIM), while arguably making it more realistic for the consumer goods industry.

Limitations: The model assumes we know the edge weights $W$ perfectly. In reality, edge weights are latent and must be inferred from historical data, which remains a massive challenge.

Final Takeaway: If your business model relies on retention and repeat purchases rather than a one-time acquisition, stop using standard IM algorithms. Focus on Cumulative Influence via the Voter Model.