TL;DR
The traditional Linear Threshold (LT) model, widely used to simulate "complex contagions" like the spread of social trends or rumors, suffers from unrealistic batch updating and poorly defined discrete time steps. This paper introduces a Generalized Linear Threshold (GLT) model that uses continuous-time stochastic processes driven by the Gillespie algorithm. The GLT model provides a more accurate, faster spreading dynamic, realistic infection ordering, and seamless integration with standard epidemic models like SI and SIR.
What Problem Does This Paper Address?
In network science, spreading processes are generally divided into two categories: simple contagion (like a virus, where a single exposure can infect you) and complex contagion (like a social movement or new technology, where you need a "critical mass" of exposures from neighbors before adopting it).
The Linear Threshold (LT) model is the standard mathematical tool for complex contagion. However, it has three major flaws:
- Vague Time Steps: It relies on discrete time steps that lack a clear physical meaning, making it hard to measure the actual speed of a spreading event.
- Synchronous Updating: Nodes in the LT model update in batches. If Node A infects Node B, and Node B crosses the threshold to infect Node C, Node C is "frozen" and cannot be infected until the next arbitrary time step. This ruins the natural sequence and randomness of the infection order.
- Incompatibility: Because of its rigid discrete-time nature, it is mathematically clunky to combine the LT model with continuous-time simple contagion models (like the SI or SIR models) to study hybrid spreading behaviors.
Methods
The authors propose the Generalized Linear Threshold (GLT) model. Instead of discrete steps, the GLT model treats infection as a continuous-time stochastic (random) process.
Each node is assigned a specific 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 borrow the Gillespie algorithm, a famous Monte Carlo method typically used in computational chemistry to simulate chemical reactions. The algorithm calculates exactly when the next infection will occur (using exponential waiting times) and which node will be infected. With some optimization, this allows the GLT model to simulate the entire network's evolution with an efficient $O(N)$ computational complexity.
Datasets
The authors evaluate their model using synthetic Erdős-Rényi (ER) random networks (specifically, networks with $N=1000$ nodes and an average degree of 4). No real-world empirical datasets were used; the paper focuses on theoretical modeling and algorithmic behavior.
Key Insights and Ideas
- Batching artificially slows down simulations: The traditional LT model systematically underestimates how fast a contagion spreads. Because nodes are forced to wait for the next discrete "batch" to update, the cascading effect is artificially throttled. The GLT model allows instantaneous, continuous updates, revealing a much faster natural spreading speed.
- Infection order matters, and LT gets it wrong: In tasks like tracing the source of a rumor, the exact order of infections is critical. The LT model creates artificial "clumps" of nodes that share the exact same infection rank. The GLT model restores the natural randomness and smooth distribution of the spreading sequence.
- Simple contagions can "unlock" complex cascades: Because the GLT model uses continuous time, it can be seamlessly combined with the SI (Susceptible-Infected) model. The authors demonstrate a hybrid network where simple contagion (random viral exposure) accumulates the critical mass needed to trigger the complex contagion (social reinforcement), causing a global cascade even when the threshold is normally too high for a cascade to start on its own.
Key Results
- Spreading Speed: When time-scaled to match a Monte Carlo baseline, the GLT model perfectly tracks the baseline's rapid infection curve. The traditional LT model visibly lags behind, confirming it underestimates spreading speed.
- Rank Distribution: When tracking the infection rank of a specific node across 10,000 simulations, the LT model produced highly segregated, spiked distributions (due to batching). The GLT model yielded a smooth, realistic probability distribution for the node's infection rank.
- Hybrid Dynamics: In a hybrid network where nodes follow either SI or GLT rules, a high threshold ($\phi^* = 0.25$) prevents the pure GLT model from spreading at all. However, the hybrid model successfully triggers a global cascade, with its spreading curve nesting perfectly between pure SI and pure GLT dynamics.
Limitations and Future Work
Limitations: The GLT model is memoryless (a Poisson process). It only looks at the current number of exposures from neighbors to determine if a threshold is met, ignoring any historical memory effects (e.g., past exposures that might influence a person's current likelihood to adopt a behavior).
Future Work: The authors suggest using percolation theory to study the exact mathematical equivalence between the GLT model and simple contagion models. Furthermore, because the GLT model easily supports continuous-time recovery processes, they plan to combine it with the SIR (Susceptible-Infected-Recovered) model and apply it to real-world empirical spreading data.
Summary updated