Maximizing Time-Decaying Influence: Why "Freshness" Matters in Social Networks

TL;DR

Information in social networks is perishable. A week-old rumor is far less likely to spread than a fresh one. This paper bridges the gap between theoretical influence maximization and reality by introducing Time-Varying (TV) models. By proving these models remain submodular, the authors unlock a scalable, near-linear time algorithm that outperforms traditional methods in both speed and accuracy.

The "Freshness" Gap: Why Fixed Probabilities Fail

In classical models like Independent Cascade (IC) or Linear Threshold (LT), an edge between two users has a static probability. However, empirical data from platforms like Digg shows that the probability of influence halves within a single day.

Existing research focused on time-delay (how long it takes for a message to jump from A to B), but overlooked time-decay (how the persuasive power of the message itself erodes over time). Addressing decay is technically challenging because it breaks the standard "coin-flipping" proofs used to guarantee that greedy algorithms will find a near-optimal solution.

Methodology: The Core Insight

The researchers proposed two new models: TV-IC and TV-LT.

• Time-Delay: Handled by a likelihood function $f_e(t-t_u)$, representing heterogeneity in human activity.
• Time-Decay: Handled by a non-increasing function $p_e(t)$, representing the loss of "freshness."

Solving the Submodularity Puzzle

To prove that a greedy strategy still works, the authors had to prove submodularity. They did this by imagining a process where every edge has a "threshold" assigned before the diffusion starts. They showed that the set of activated nodes corresponds to reachability in a graph that evolves based on the seed set—a breakthrough that allows (1-1/e) approximation guarantees even with decaying probabilities.

Scalability via Reverse Influence (RI) Sets

Traditional Monte-Carlo simulations are too slow for networks with millions of edges. The authors adapted the IMM (Influence Maximization Martingale) framework. They developed a novel dynamic programming algorithm to find the Latest Activation Time ($au$):

$au[u]={\max }_{v\in N^{+}(u)}\min \{au[v]-d_{uv},p_{uv}^{-1}(x_{uv})\}$

This allows the algorithm to "work backward" from a target node to find potential influencers in $O(m\log n)$ time.

Experimental Battleground

The authors tested their method against several baselines, including LazyGreedy (simulation-based) and IMM-IC (standard IMM without decay).

• Accuracy: In the ego-Twitter dataset, standard models that ignored decay were up to 30% less accurate in identifying the best seed sets.
• Efficiency: The proposed method finished in seconds on graphs where LazyGreedy timed out after 10,000 seconds.

Critical Analysis & Conclusion

Takeaway

The major contribution here isn't just "adding time" to the equations; it's the proof that Time-Decay preserves submodularity. This ensures that the decades of research into greedy submodular optimization can be applied to more realistic, "perishable" information networks.

Limitations & Future Work

• Parameter Learning: The model assumes edge decay functions are known. In reality, these must be learned from historical cascade logs.
• Recurrent Cascades: The model assumes power always decays. However, some memes or news "recur" (e.g., seasonal trends). Such cases would break the non-increasing assumption and likely break submodularity.

The future of viral marketing and rumor control lies in these temporal models. This work provides the mathematical and algorithmic foundation to scale those solutions to the size of the modern web.