Dynamic Propagation Rates: The Hidden Dimension of Viral Marketing

TL;DR

Existing viral marketing models assume influence spreads at a constant speed. This paper proves—via Twitter data—that "trending" topics actually speed up. The authors introduce the Dynamic Influence Propagation (DIP) model and the FAST algorithm, which optimizes seed sets by predicting exactly when this viral speedup will occur, reducing marketing costs while meeting reach targets.

Background: Why Static Models Fail

In the world of Online Social Networks (OSNs), the "Triggering Model" and "Continuous-Time Diffusion" have been the gold standards. But they share a fatal flaw: they are sociologically "blind." In reality, when a topic hits a critical mass (becomes "trending"), users react faster, retweeting and sharing with less delay.

By analyzing 5,049 Twitter trending topics, the authors confirmed that a vast majority of viral content sees a significant drop in "retweet delay" after hitting the trending list. If a marketer uses a static model, they will likely over-recruit "seed" users (influencers), wasting budget because they don't account for the natural acceleration the topic will gain on its own.

Figure 1: Twitter data proves that the propagation rate (L) significantly increases after a topic starts trending.

Methodology: The FAST Framework

The core challenge of the TAP-DIP (Threshold Activation Problem under DIP) is its dependency on a global state. You can't know the propagation rate until you know how many people are influenced, but you can't calculate the influence without knowing the rate.

1. The Dynamic Influence Propagation (DIP) Model

The authors define a rate function $\rho (t)$ that stays at 1 until a threshold $\varphi |V|$ is met, then jumps to $r$ ($r>1$). This creates a "Speedup Time" variable.

2. FAST (Finding Anticipated Speedup Time)

To solve this, the authors developed FAST. Instead of brute-forcing every possible moment the speedup could happen, FAST treats the required seed set size as a function of time $t$ and applies Lipschitz Optimization.

• Intuition: The function for the minimum seed set is "smooth" enough that we can iteratively narrow down the optimal time $t$ where the rate should jump.
• Subroutines: It utilizes MMinSeed and Multi-IM to handle multiple requirements (e.g., "reach 5% to start trending" AND "reach 20% total reach").

3. MMinSeed & Multi-IM

Standard sampling like IMM or RIS is built for single-objective maximization. The authors re-engineered this into a Multi-threshold problem. They designed a submodular objective function that stops "counting" influence for a specific goal once its target threshold is hit, ensuring the algorithm focuses budget on the unmet requirements.

Experimental Evidence

The authors tested FAST against massive datasets, including Pokec (1.6M nodes) and LiveJournal (4.8M nodes).

Performance & Scalability

A key finding was that the Multi-IM approach is significantly more efficient than standard IMM because it calculates sample requirements dynamically. In large networks, FAST completed its optimization in a few hours, whereas traditional methods might struggle with the complexity of dual thresholds.

Figure 2: FAST demonstrates near-linear scalability relative to the number of edges in the network.

Quality of Results

In simulations, the seed sets generated by FAST successfully hit activation targets. Interestingly, "Base" models (which ignore DIP) reached much more than the threshold, proving that without DIP, you are likely buying more influence than you actually need.

Critical Analysis & Takeaways

This paper adds a vital "dimension" to the TAP problem: Time-Dependency linked to Global Reach.

• Impact: For platforms like X (Twitter) or TikTok, where "Trending" algorithms are transparent, this model allows for high-precision viral engineering.
• Limitation: The current model assumes the rate changes only once. Real-world virality might have multiple stages of acceleration or even a "fatigue" deceleration.
• Future Work: Expanding this to a "Continuous Rate Change" model where speed is a continuous function of current reach would be the next logical step in this research lineage.

Final Takeaway: In the race for attention, understanding when the crowd takes over is just as important as knowing who to start with.