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:
- Vague Time Steps: Discrete steps lack a clear physical meaning, making it difficult to measure the actual speed of a spreading event.
- Synchronous Updating: Nodes update in batches, which ruins the natural sequence and randomness of the infection order.
- 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.
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.
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