HSCM: Why "Persistence Pays Off" in Social Network Diffusion

TL;DR

Most social diffusion models assume a "one-and-done" approach: if a friend doesn't convince you to buy a product today, they never will. The History Sensitive Cascade Model (HSCM) breaks this mold by introducing Historical Sensitivity. It mathematically proves that repeated exposure increases adoption probability and provides a rigorous framework for calculating these odds using Markov chains and polynomial algorithms for tree structures.

The "Memoryless" Flaw in Prior Work

In classical models like the Independent Cascade Model (ICM), an active node gets exactly one shot to activate its neighbor. If it fails, that specific link is effectively dead. Similarly, the Linear Threshold Model (LTM) only looks at the current state of active neighbors.

The authors argue this ignores human psychology. In the real world, if Bob pestered Alice every week for 10 weeks to buy an iPod, Alice is statistically more likely to succumb in week 10 than she was in week 1. Existing models treat week 10 the same as week 1, a phenomenon the authors call a lack of Historical Sensitivity.

Methodology: Capturing the Dynamics of Time

The core contribution of HSCM is moving from static probabilities to time-dependent state transitions.

1. The Tree Algorithm

For tree-structured graphs (like corporate hierarchies), the authors provide a computationally efficient polynomial-time algorithm. The probability $P(v_{k+1})$ that a node $v$ is active at time $k+1$ is calculated as: $P(v_{k+1})=[P(influencer(v{)}_k)-P(v_k)]imesW+P(v_k)$ This formula captures the "delta" of new influence while retaining the memory of previous activation states.

2. General Graphs and the State Space Problem

In general graphs with cycles, influence can loop back. To solve this, the authors map the network to a Markov Model.

• State Representation: Every possible combination of active/inactive nodes is a state (a power set of $V$).
• Transition Matrix: They build a $2^{n}imes{2}^n$ stochastic matrix $A$ where each entry $A[i,j]$ represents the probability of the network moving from state $i$ to state $j$.

Figure 1: The algorithm for constructing the stochastic matrix to track diffusion across general graphs.

Experimental Insights: Scaling and Density

The authors tested HSCM on Scale-Free networks (the gold standard for social structures).

Density and Speed

High-density networks (more connections per node) don't just reach more people; they reach them faster. Innovation spreads easily in highly connected graphs because a node is likely to have multiple neighbors who can reinforce the "historical" pressure.

The "Optimal Seed" Strategy

One of the most practical findings is the "cascade time per node" analysis. The experiments showed that increasing the number of initial "seed" nodes (Selected-Number) improves speed, but only up to a point.

Figure 2: Landscape of Cascade Time per Node across different thresholds and seed sizes.

In their 100-node simulation, they found that a "Selected-Number = 3" was a critical threshold. Adding more than 3 initial nodes yielded diminishing returns in terms of final spread speed, suggesting that marketers should aim for a small, potent core of influencers rather than a broad, shallow campaign.

Critical Insight & Conclusion

The HSCM provides the mathematical backbone for what we intuitively know: persistence matters.

Takeaways:

1. Historical Sensitivity is a vital parameter for any diffusion model aiming for realism in viral marketing or epidemiology.
2. Structural Leverage: In trees, the influence is predictable and polynomial; in general graphs, the complexity grows exponentially (NP-Hard), requiring the Markov approach.
3. Hybrid Marketing: The paper suggests a "Mass Marketing + Viral Targeting" combo. Mass marketing lowers the global "threshold," while viral targeting triggers the sensitive history-based cascade.

Limitations: The primary drawback is the state-space explosion. A network of 100 nodes creates a matrix of $2^{100}$, which is computationally impossible for direct Markov calculation. Future work must bridge the gap between "historical sensitivity" and "computational scalability" using approximation heuristics like Greedy or Hill-Climbing algorithms.