CVAP: Beyond Static Probabilities in Social Influence Maximization

TL;DR

The classic Independent Cascade Model (ICM) assumes your probability of influencing a friend is always the same, regardless of how many others have tried. This paper proves that's wrong. By introducing the Cascade with Varying Activation Probability (CVAP) model, the authors reflect the real-world "Unaware" and "Saturated" effects, proving that while influence behavior is complex, we can still achieve guaranteed $(1-1/e)$ optimality in seed selection.

Problem & Motivation: The Static Probability Myth

In the world of Influence Maximization (IMP), we ask: "Which $k$ nodes should we seed to start a wildfire of information?" For decades, the industry relied on ICM, where each edge $(u,v)$ has a static probability $q$.

However, human behavior is more nuanced. The authors identify two critical psychological phases through an empirical study of the Renren social network:

1. The Unaware Effect: At first, a user might miss a message or ignore a single recommendation. As more friends share it, "awareness" and social proof increase the probability of activation.
2. The Saturated Effect: After dozens of exposures, if a user hasn't joined, they likely find the content unappealing or annoying. The probability then plummets.

Methodology: Designing the CVAP Model

To capture this "hump-shaped" probability curve, the authors propose a piecewise function for $p(k)$, where $k$ is the number of exposures:

• Phase 1 (Growth): A Logistic function models the increasing awareness.
• Phase 2 (Decline): A Linear function models the subsequent saturation.

Fig 1. The learned activation probability showing the rise (Unaware) and fall (Saturated) phases.

The Mathematical "Secret Sauce"

A core challenge in IMP is Submodularity—the property of diminishing marginal returns. If a model isn't submodular, the simple Greedy Algorithm (adding nodes one by one) might fail catastrophically. The authors prove that as long as $p(k+1)\le \frac{p(k)}{1-p(k)}$, the influence spread function $\sigma (A)$ remains submodular. They provide a specific parameter constraint for their Logistic-Linear model to ensure this holds.

Experiments & Results: Real-World Accuracy

The study utilized a massive dataset from Renren (China's Facebook equivalent), tracking video sharing actions over three years.

• Turning Point: The data shows that the probability of sharing a video peaks at around 10 exposures.
• Accuracy: In simulations on the Xi’an Jiaotong University network (48k nodes), the CVAP model predicted influence spread with less than 3% absolute error compared to real-world trace data.

Fig 2. The high alignment between CVAP simulated spread and real-world data.

Critical Insight & Conclusion

The CVAP model represents a transition from "Black-box" probabilistic models to "Behavioral" social models.

Key Takeaways:

• Marketing Strategy: Bombarding a user after 10-15 unsuccessful friend recommendations is likely a waste of resources; the Saturated Effect has already set in.
• Algorithmic Safety: Even with varying probabilities, we can still use Greedy Algorithms (with CELF heuristics) safely, as long as the probability decay follows the submodularity constraints.

Limitations: The model assumes nodes are homogeneous (everyone reacts to the 10th exposure the same way). Future work could introduce user-specific sensitivities ($r_1,r_2$) to create a personalized influence framework.