A generalized linear threshold model for an improved description of the spreading dynamics

Yijun Ran, Xiaomin Deng, Xiaomeng Wang, Tao Jia

Abstract

Many spreading processes in real-life can be considered complex contagions, often modeled using the linear threshold (LT) model. Despite its widespread usage, the LT model suffers from several limitations: vaguely defined discrete-time steps, synchronous updating that ignores individual differences, and incompatibility with simple contagion models. We propose a generalized linear threshold (GLT) model for continuous-time stochastic complex contagion, implemented via the Gillespie algorithm. We find that the traditional LT model systematically underestimates spreading speed and sequence randomness. The GLT model integrates seamlessly with SI or SIR models, enabling the study of hybrid spreading where simple contagion triggers complex cascades.

Introduction

In network science, spreading processes are generally divided into two categories: simple contagion (e.g., a virus where a single exposure can infect) and complex contagion (e.g., social movements requiring a "critical mass" of exposures). While the Linear Threshold (LT) model is the standard mathematical tool for complex contagion, it possesses three major flaws:

  1. Vague Time Steps: Discrete steps lack a clear physical meaning, making it difficult to measure the actual speed of a spreading event.
  2. Synchronous Updating: Nodes update in batches, which ruins the natural sequence and randomness of the infection order.
  3. Incompatibility: It is mathematically difficult to combine the discrete-time LT model with continuous-time simple contagion models like SI or SIR.

Methodology: The GLT Model

The authors propose the Generalized Linear Threshold (GLT) model, which treats infection as a continuous-time stochastic process. Each node is assigned a transition rate ($k_i$). If the fraction of a node's infected neighbors is below its personal threshold, its infection rate is 0; once the threshold is met, its rate becomes $k_i$.

To simulate this efficiently, the authors employ the Gillespie algorithm, a Monte Carlo method typically used in computational chemistry. The algorithm calculates exactly when the next infection will occur and which node will be infected using exponential waiting times. This approach allows the GLT model to simulate network evolution with an efficient $O(N)$ computational complexity.

Key Insights and Results

Spreading Speed and Accuracy

The traditional LT model artificially slows down simulations due to its batch updating rule. Because nodes are forced to wait for the next discrete "batch" to update, the cascading effect is throttled. The GLT model allows for instantaneous, continuous updates, revealing a much faster natural spreading speed.

Comparison of spreading speed. (a) SI models in continuous and discrete time match perfectly. (b) The GLT model aligns with the Monte Carlo baseline, whereas the traditional LT model significantly underestimates the spreading speed.

As shown in Figure 1, when time-scaled to match a Monte Carlo baseline, the GLT model tracks the infection curve perfectly. The traditional LT model visibly lags behind, confirming its tendency to underestimate spreading velocity.

Infection Rank and Randomness

Infection order is critical for tasks like tracing the source of a rumor. The LT model creates artificial "clumps" of nodes that share the exact same infection rank due to batching. The GLT model restores the natural randomness and smooth distribution of the spreading sequence, which is vital for realistic modeling.

Hybrid Spreading Dynamics

A significant advantage of the GLT model is its seamless compatibility with simple contagion models. In a hybrid network, simple contagion (random viral exposure) can accumulate the critical mass needed to trigger a complex contagion cascade.

Hybrid spreading dynamics. (a) At a high threshold, pure GLT fails to spread, but the hybrid model triggers a global cascade. (b) The hybrid spreading curve sits between the pure SI and pure GLT dynamics.

Figure 6 demonstrates a scenario where a high threshold prevents a pure complex contagion from spreading. However, the hybrid model successfully triggers a global cascade, with its spreading curve nesting perfectly between pure SI and pure GLT dynamics.

Conclusion

The GLT model addresses the temporal and sequential inaccuracies of the traditional LT model. By utilizing continuous-time stochastic processes, it provides a more realistic description of complex contagion and allows for the exploration of hybrid spreading phenomena. Future work will involve incorporating recovery processes (SIR) and applying the model to empirical real-world spreading data.

Summary updated

Abstract

Many spreading processes in our real-life can be considered as a complex contagion, and the linear threshold (LT) model is often applied as a very representative model for this mechanism. Despite its intensive usage, the LT model suffers several limitations in describing the time evolution of the spreading. First, the discrete-time step that captures the speed of the spreading is vaguely defined. Second, the synchronous updating rule makes the nodes infected in batches, which can not take individual differences into account. Finally, the LT model is incompatible with existing models for the simple contagion. Here we consider a generalized linear threshold (GLT) model for the continuous-time stochastic complex contagion process that can be efficiently implemented by the Gillespie algorithm. The time in this model has a clear mathematical definition and the updating order is rigidly defined. We find that the traditional LT model systematically underestimates the spreading speed and the randomness in the spreading sequence order. We also show that the GLT model works seamlessly with the susceptible-infected (SI) or susceptible-infected-recovered (SIR) model. One can easily combine them to model a hybrid spreading process in which simple contagion accumulates the critical mass for the complex contagion that leads to the global cascades. Overall, the GLT model we proposed can be a useful tool to study complex contagion, especially when studying the time evolution of the spreading.
BibTeX
@article{ran2020generalized,
  author = {Yijun Ran and Xiaomin Deng and Xiaomeng Wang and Tao Jia},
  title = {{A generalized linear threshold model for an improved description of the spreading dynamics}},
  journal = {Chaos: An Interdisciplinary Journal of Nonlinear Science},
  year = {2020},
  url = {https://openreview.net/forum?id=S9tuIbDm89},
}
Figure