🌀 nonlinear sciences

The Structure of Spreading on Temporal Networks

This paper establishes a theoretical and computational framework that maps spreading dynamics on temporal networks to reachability in temporal event graphs, enabling the derivation of epidemic thresholds and prevalence for complex processes like the SIS model without the need for explicit simulations.

Original authors: Omar Henderson, Mikko Kivelä, Márton Karsai

Published 2026-08-07

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Omar Henderson, Mikko Kivelä, Márton Karsai

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the world as a giant, bustling city where people are constantly moving, talking, and sharing things. Sometimes, they share a joke, a rumor, or a new dance trend; other times, they might accidentally share a cold or a flu. In the old days, scientists tried to understand how these things spread by pretending everyone was standing in a giant, perfectly mixed soup, bumping into each other at random. It was a useful idea, but it missed the real magic: the fact that we don't all mix at once. We have schedules. We have bursts of activity followed by long quiet periods.

To understand how things actually travel through this messy, time-varying city, scientists use something called "networks." Think of a network as a map of who knows whom. But a normal map is static—it shows the roads, but not when the cars are driving on them. Real life is a "temporal network," where connections happen at specific times. If you want to know if a rumor will go viral, you can't just look at the map; you have to know when the messages were sent. The big question for scientists has been: How do we predict if a message (or a virus) will take over the whole city without having to run a million slow, boring computer simulations to watch it happen?

This is where a new paper by Omar Henderson, Mikko Kivelä, and Márton Karsai comes in. They found a clever shortcut. Instead of watching the virus spread step-by-step in a simulation, they realized you can turn the entire timeline of interactions into a single, static "event graph." Imagine taking a movie of all the handshakes in a room and freezing them into a single, giant flowchart. In this flowchart, every handshake is a dot, and the lines connecting them show the order in which they happened. The authors discovered that for certain types of spreading (like a rumor that keeps getting reinforced by repeated exposure), you can solve the puzzle of "how far will this go?" just by looking at the shape of this flowchart.

They showed that this method is like having a superpower. Instead of running expensive, time-consuming simulations, you can use math to look at the "out-components" of this event graph—basically, counting how many dots you can reach starting from one point. This allows them to calculate exactly when an outbreak will start (the "epidemic threshold") and how big it will get, even for complex, real-world networks like Twitter replies, global flight schedules, or public transport in Helsinki.

The paper introduces a few specific models to test this. One is the "lrSIS" model, which is a bit like a rumor that gets stronger every time you hear it. If you hear a rumor, you believe it for a while. But if you hear it again from a different friend before your belief fades, your belief timer resets, and you keep spreading it. This "reinforcement" makes the process fit perfectly into their event graph method. They also looked at a more standard "SIS" model (where you get sick, recover, and can get sick again) and found that while it's slightly different, the "reinforced" version acts as a perfect upper limit, helping them predict the standard version's behavior with great accuracy.

The researchers didn't just stop at theory. They tested their ideas on real data. They looked at how people reply to each other on Twitter, how planes fly between cities, and how people take buses in Helsinki. In all these cases, their "event graph" math predicted the start of an outbreak almost exactly as well as the slow, heavy computer simulations did, but much faster. They found that the "burstiness" of the network—how clumpy the interactions are—matters a lot. If people interact in wild bursts followed by silence, it's harder for a disease to spread unless it can hang around for a long time.

In short, this paper gives us a new lens to see how things spread through time. It turns a chaotic, moving target into a static puzzle that can be solved with a ruler and a calculator. By mapping the flow of time onto a simple graph, the authors show us that we can predict the fate of spreading processes without needing to simulate every single second of the journey. It's a powerful tool that turns the complex, messy reality of time into something we can understand, measure, and predict.

Technical Summary: The Structure of Spreading on Temporal Networks

Problem Statement
Spreading processes on static networks are well-understood through mappings to percolation theory, allowing for the analytical computation of epidemic thresholds and final sizes without explicit simulation. However, real-world systems are characterized by time-varying interactions (temporal networks), where bursty contact patterns, event durations, and causal ordering fundamentally alter spreading dynamics. While the importance of these temporal features is recognized, analytical tools for temporal networks remain scarce. Existing approaches rely heavily on computationally expensive stochastic simulations or limited analytical models (e.g., spectral methods on supra-adjacency matrices or schematic random network models) that fail to capture the full complexity of arbitrary degree and inter-event time distributions. The central challenge is to establish a theoretical framework that links temporal network connectivity to spreading outcomes with the same analytical power and computational efficiency found in static percolation.

Methodology
The authors propose mapping spreading dynamics on temporal networks to reachability in temporal event graphs (EGs).

Event Graph Construction: A temporal network is represented as a static directed acyclic graph (DAG) where nodes correspond to time-stamped events of the original network. Directed links between events encode temporal adjacency (i.e., event $e_j$ follows $e_i$ chronologically and shares a node).
Pruning for Dynamics: To model specific spreading processes, the EG is pruned based on process constraints. For a process with a finite recovery time $\delta t$ , links with waiting times $\Delta t \ge \delta t$ are removed. This transforms the problem into a bond percolation problem on the EG.
Global Consistency: The paper introduces the concept of "globally consistent" spreading processes, where the spreading structure can be represented by a single EG regardless of initial conditions.
- lrSIS (Last-Contact Reinforcing SIS): A variant where an infected node's recovery clock resets upon every new infection event from a neighbor. This process maps exactly to reachability on a single EG.
- frSIS (First-Contact Reinforcing SIS): A variant where a node can infect a specific neighbor only once before its recovery clock resets. This maps to a constrained EG.
- Standard SIS: The paper notes that standard SIS with fixed recovery times is globally inconsistent but is bounded by the lrSIS process.
Analytical Derivation: Assuming locally tree-like EGs and random temporal link dynamics, the authors use generating functions to derive the degree distribution of the emerging EG. This allows for the calculation of the basic reproduction number ( $R_0$ ) and the epidemic threshold ( $R_0=1$ ) for networks with arbitrary degree distributions and inter-event time distributions (including bursty Lomax/Pareto Type II distributions).

Key Contributions

Theoretical Mapping: The paper establishes that spreading on temporal networks is analogous to percolation on static networks, specifically mapping to reachability in temporal event graphs. This provides a unified framework for processes like SIS variants.
Analytical Thresholds: The authors derive an analytical epidemic threshold condition for random temporal networks with arbitrary degree and inter-event time distributions. The threshold is expressed as $F_R(\delta t_c) = (R_0^{stat})^{-1}$ , where $F_R$ is the residual waiting time distribution and $R_0^{stat}$ is the static network reproduction number.
Computational Efficiency: The framework demonstrates that epidemic outcomes (prevalence and thresholds) can be computed via component analysis of pruned event graphs. This avoids the need for expensive repeated numerical simulations, offering significant computational advantages, particularly when analyzing multiple initial conditions.
Characterization of Burstiness: The study quantifies how temporal heterogeneity (burstiness) affects the epidemic threshold. It shows that as inter-event time distributions become more bursty (tail exponent $\alpha \to 2$ ), the critical recovery time $\delta t_c$ diverges, requiring longer recovery times for an epidemic to sustain.

Results

Phase Diagrams: Theoretical phase diagrams for lrSIS, frSIS, and SIR processes on $k$ -regular temporal networks show that the epidemic transitions are characterized by similar contours, with the lrSIS process providing an upper bound for the standard SIS dynamics.
Validation on Synthetic Networks: Analytical predictions for $R_0$ and critical thresholds ( $\delta t_c$ ) on synthetic networks (both $k$ -regular and degree-heterogeneous) with bursty link dynamics (Lomax distribution) show close agreement with numerical simulation results. The analysis reveals that the dependence of the threshold on burstiness is weak in dense or degree-heterogeneous networks but significant in sparse, degree-homogeneous networks.
Empirical Validation: The framework was applied to three empirical temporal networks: Twitter replies, global flight networks, and Helsinki public transport.
- The numerical condition $R_0=1$ derived from the EG accurately predicted the onset of infection in the Twitter and flight networks.
- For the Helsinki network, the EG method slightly overestimated the critical point, likely due to local supercritical regions within a globally fragmented network.
- In all cases, the frSIS process served as a tight upper bound for the standard SIS process.
Performance: Runtime comparisons indicate that while constructing the event graph has an initial cost, calculating spreading outcomes for all initial conditions via a single sweep is significantly faster than running multiple explicit simulations as the number of realizations increases.

Significance
The paper claims that this work provides a "theoretical and computational framework" for a class of spreading processes on temporal networks, analogous to the role percolation plays in static networks. By identifying globally consistent processes (like lrSIS), the authors enable the direct computation of epidemic outcomes from network connectivity rather than simulation. This approach extends the analytical tractability of static network theory to complex temporal structures, allowing for the study of how arbitrary degree and inter-event time distributions jointly influence spreading. The authors assert that this mapping not only aids in understanding epidemic thresholds but also constrains other dynamical processes (e.g., random walks, opinion dynamics) wherever globally consistent variants can be formulated, transforming them into structural reachability problems.

Technical Summary: The Structure of Spreading on Temporal Networks

More like this