Temporal Networks

Most network diagrams lie a little. They draw a line between two nodes and let you imagine that the connection is permanent — as if a train route, a phone call, or a handshake lasted forever. Real contacts are nothing like that: they flicker on and off, each one tied to a moment in time.

Temporal networks fix that lie. Every edge carries a timestamp (or a list of them) that records when the contact happened. An edge active at time $t = 3$ cannot carry information at time $t = 7$ if it has already vanished.

The consequence is surprising: reachability changes entirely. In an ordinary graph, if you can reach B from A and C from B, you can reach C from A. In a temporal network that transitivity breaks down — you can only reach C from A if the A-to-B contact happens before the B-to-C contact. Miss the window, and the path doesn't exist, no matter how well connected the nodes look on a static map.

This temporal ordering turns the familiar graph into something much richer — and much harder to reason about.

The network below has six nodes and several edges, each labeled with the time at which it is active. Pick a source and a target, then click Find path to search for a time-respecting route — one where each hop departs no earlier than the previous hop arrived.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="controls">
  <label>{{lbl_source}} <select id="src"></select></label>
  <label>{{lbl_target}} <select id="tgt"></select></label>
  <button id="find" type="button">{{btn_find}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="canvas" width="460" height="260"></canvas>
<div class="status" id="status">{{msg_idle}}</div>

/* {{c_css_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .5rem; }
label { font-size: .88rem; display: flex; align-items: center; gap: .3rem; }
select { font-size: .88rem; border: 1px solid #aaa; border-radius: 6px; padding: .2rem .4rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border: 1px solid #d0d8e0; border-radius: 10px;
         background: #f7f9fb; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; margin-top: .5rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.idle { color: #555; }

// Code not found

Notice what happens when you choose pairs where the timestamps run "backwards." The nodes may look connected on a static map, yet no valid temporal path exists because every route requires traveling an earlier edge after a later one — and time does not allow that.

Adding timestamps to edges changes what is easy and what is hard — sometimes dramatically.

What stays easy. Deciding whether a temporal path exists from $u$ to $v$ (temporal reachability) can be answered in polynomial time: process edges in chronological order and propagate arrival times, much like Dijkstra's algorithm on a static graph. The foremost journey — the one that arrives at $v$ as early as possible — is also solvable efficiently.

What gets harder.

• Minimum-time-span journey: finding a path that minimises the difference between the last departure and the first arrival (the duration of the journey) is NP-hard in general temporal graphs.
• Temporal graph colouring and diameter: computing the temporal diameter — the latest earliest-arrival time over all reachable pairs — can be much harder than its static counterpart.
• Influence maximisation: choosing $k$ seed nodes to maximise the spread of information under temporal dynamics is NP-hard, and even approximating it well requires careful analysis.

The core insight. A temporal network on $n$ nodes and $m$ (timestamped) edges is really a sequence of static snapshots. The number of distinct paths explodes because path identity depends on timing, not just topology. Problems that look like simple graph coloring or max-flow on static graphs can become fundamentally harder when the edges come and go.

Temporal networks are an active research area. Many complexity questions — especially around optimal information spreading and temporal motif counting — remain open or have only recently been settled.

Any system where when a connection is active matters as much as whether it exists benefits from a temporal-network view:

• Epidemic spreading: a disease can only travel an edge if the contact happens while the host is infectious. Temporal models predict outbreak sizes far more accurately than static graphs — and identify the critical time windows for interventions like quarantine.
• Contact tracing: the chain of exposures is inherently ordered in time. A contact at 9 a.m. cannot infect someone whose infectious period ended at 8 a.m., even if static-graph tools would flag the link.
• Opportunistic (delay-tolerant) networks: in satellite swarms, vehicle-to-vehicle communication, or rural mesh networks, links exist only briefly. Routing must schedule messages to "meet" the next hop at the right moment — a classic temporal-path problem.
• Financial contagion: a bank that fails on Monday can drag down its counterparties on Tuesday; a bank that fails on Friday affects a different set. The order of defaults rewires who suffers.
• Social dynamics: influence, memes, and job referrals travel through contacts that are bursty and ordered. Graph coloring-style community detection on static snapshots misses the causal flow that temporal analysis reveals.

Temporal networks are to time-varying systems what ordinary graphs are to static ones — the natural language for questions about who can reach whom, and when.

Temporal networks make a simple but radical demand: take time seriously. The moment you attach a timestamp to each edge, the comfortable rule that "if A reaches B and B reaches C then A reaches C" can fail — and with it, many algorithms we rely on for routing, spreading, and search.

The payoff is realism. Epidemic models that respect contact times, routing protocols that schedule messages to catch fleeting links, and financial models that track the cascade of defaults in order — all of these are temporal-network problems in disguise.

The field is young and full of open questions, from the complexity of temporal motifs to the best ways to compress a time-varying graph without losing its essential dynamics. If ordinary graphs feel too static for the systems you care about, the right model may already be waiting — with timestamps attached.

For the foundations of computational hardness that underpin many of these questions, see P vs NP.