Spreading Processes

<aside> 🌐

Outdated page — the Temporal Graph Wiki has moved. Read the wiki on temporalgraph.wiki.

</aside>

Spreading processes on temporal graphs model infections, information, opinions, and other states propagating through contacts that change over time. This overview separates the propagation rule from the computational task: papers with similar motivation can study substantially different problems.

<aside> 🚧

Preliminary content! — last checked 27 September 2026. Still to be proofread and properly layouted. Subpages still empty. Check for missing literature. Update:

general overview filled
concrete problem definitions filled </aside>

1. General overview: which choices define a problem?

A problem is specified by its process rule, temporal setting, available information, permitted decisions, and objective. For example, choosing seeds and choosing transmission times can use similar local dynamics but define different computational problems.

Choice	Alternatives	What must be specified?
Local propagation rule	One active neighbor; a threshold of active neighbors; zero forcing; other rules	Does the condition concern the receiving vertex or the transmitting vertex? Are neighbors counted in the current snapshot or across a time interval?
Persistence / recovery	Permanent activity; temporary activity followed by susceptibility; recovery followed by immunity	How long is a vertex infectious? Can it be reinfected? Can contact renew an already active vertex’s timer? SI/SIS/SIR labels alone do not settle these details.
Time and update order	Discrete or continuous time; simultaneous rounds or propagation to closure within a snapshot	When can a newly activated vertex transmit? Are transmission times strictly increasing or merely nondecreasing? When do protection, transmission, and recovery occur?
Determinism / randomness	Deterministic transmission; random transmission or recovery; adversarial choices	State the probability law or adversary’s power. A randomized algorithm does not itself make the spreading process stochastic.
Decision / intervention	Choose seed vertices; choose seed or transmission times; assign edge labels; delete or delay contacts; protect vertices; choose observations or experiments	Which objects are fixed input, which are chosen, and what budget or schedule constraints apply? Distinguish deleting one contact from deleting all appearances of an edge.
Sources and targets	A given source/set; a chosen set; a guarantee for every possible source/set; all vertices or designated targets	Keep the quantifiers explicit. A bound for a fixed source set differs from a bound that must hold for every possible source.
Objective	Coverage; seed cost; total ever active; peak activity; activity at a deadline; persistence; saved vertices; information learned	Specify the counted set, observation horizon, threshold, and whether the target is deterministic, expected, or probabilistic. “Spread” is not a unique objective.
Information and interaction	Whole temporal graph known; online revelation; unknown labels or edges; repeated experiments	What is known initially? What is returned by a query? What can change between experiments? Distinguish experiment rounds from time steps within one infection.
Spreading versus agent movement	Branching propagation of activity; one or several moving agents	Can activity persist and propagate along several contacts, or must visits lie on one chronological walk? State the number of agents and movement constraints.
Temporal-graph setting	Directed/undirected; repeated contacts; simple/proper/happy; finite/periodic lifetime; traversal durations	State the setting for each cited variant. Here “simple” means at most one appearance per edge; in the undirected setting “proper” means every snapshot is a matching; “happy” means both.

Task families. Seed selection and coverage; activation scheduling and persistence; network modification to increase or limit reachability; containment and intervention; inference and discovery; and process analysis/prediction. Threshold activation and zero forcing describe propagation rules that can be combined with a seed-selection task. Process analysis can ask about outbreak size, completion time, or survival even when no intervention is optimized.

Comment: “active” vs “reached” vertices

Comment: connection to temporal exploration

2. Concrete problems and their choices

Inspired by Temporal Reachability Dominating Sets: Contagion in Temporal Graphs, Table 1 (journal version, p. 2), this comparison adds propagation rules and information models. Names refer to the cited formulations.

Reading conventions. Each row specifies a cited formulation. Unmarked graphs are undirected; path shifting uses a directed temporal multigraph. Symbols are local to each row. A chosen seed set is $S\subseteq V$; $S_0\subseteq V$ denotes a prescribed source set. An additional restriction $S\subseteq C\subseteq V$ would mean that seeds must come from an explicitly given candidate set $C$; that restriction is not assumed here.

<aside> ❕

Notation. For a temporal graph $\mathcal G=(V,E,\lambda)$, let $[\tau]=\{1,\ldots,\tau\}$. Write $R_{\mathcal G}^{<}(S)$ and $R_{\mathcal G}^{\le}(S)$ for the vertices reached from some $s\in S$ by strict and nonstrict temporal paths, respectively; the seeds count as reached. Here $S\subseteq V$ is chosen, while $S_0\subseteq V$ denotes a prescribed source set. The deletion and delay rows use their cited traversal-duration convention.

For state processes, $A_t$ is the set currently active and $B_t$ the set burning at time $t$. The counter-process objectives concern $t\in[\tau]$; separate periodic and window-constrained variants require their own schedule restrictions.