Introduction

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=3t = 3 cannot carry information at time t=7t = 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.

Try It

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.

<!-- Temporal network path finder — edges carry timestamps; a path is valid only if timestamps are non-decreasing. -->
<p class="hint">Each edge is labeled with the time it is active. A valid temporal path must use edges in non-decreasing time order. Choose a source and target, then click <b>Find path</b>.</p>
<div class="controls">
  <label>Source: <select id="src"></select></label>
  <label>Target: <select id="tgt"></select></label>
  <button id="find" type="button">Find path</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<canvas id="canvas" width="460" height="260"></canvas>
<div class="status" id="status">Choose source and target, then find a path.</div>

/* Layout and visual styling for the temporal network demo. */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Temporal graph definition: nodes with fixed positions, edges with timestamps.
// Node positions on the 460x260 canvas (id, x, y).
const NODES = [
  { id: 'A', x: 60,  y: 130 },
  { id: 'B', x: 170, y: 55  },
  { id: 'C', x: 170, y: 205 },
  { id: 'D', x: 290, y: 55  },
  { id: 'E', x: 290, y: 205 },
  { id: 'F', x: 400, y: 130 }
];
// Directed edges with timestamps. Each edge is traversable at time t or later.
// Format: { u: source, v: target, t: active time }
const EDGES = [
  { u: 'A', v: 'B', t: 1 },
  { u: 'A', v: 'C', t: 3 },
  { u: 'B', v: 'D', t: 2 },
  { u: 'C', v: 'E', t: 5 },
  { u: 'D', v: 'F', t: 4 },
  { u: 'E', v: 'F', t: 6 },
  { u: 'B', v: 'E', t: 7 },
  { u: 'C', v: 'D', t: 1 }
];

const nodeMap = {};
NODES.forEach(n => { nodeMap[n.id] = n; });

// BFS over temporal edges: only use edge (u,v,t) if t >= current arrival time.
function findTemporalPath(src, tgt) {
  // Start at source at time 0.
  const queue = [{ node: src, time: 0, path: [src] }];
  const visited = {};
  visited[src + ':0'] = true;
  while (queue.length) {
    const { node, time, path } = queue.shift();
    if (node === tgt) return path;
    // Expand neighbors reachable via edges active at or after current time.
    for (const e of EDGES) {
      let next = null;
      if (e.u === node && e.t >= time) next = e.v;
      else if (e.v === node && e.t >= time) next = e.u;
      if (!next) continue;
      const key = next + ':' + e.t;
      if (!visited[key]) {
        visited[key] = true;
        queue.push({ node: next, time: e.t + 1, path: [...path, next] });
      }
    }
  }
  return null;
}

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

// Draw the network on the canvas, highlighting the found path if any.
function draw(highlightPath, highlightEdges) {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  // Draw edges first so nodes appear on top.
  for (const e of EDGES) {
    const a = nodeMap[e.u], b = nodeMap[e.v];
    const onPath = highlightEdges && highlightEdges.some(
      he => (he.u === e.u && he.v === e.v && he.t === e.t) ||
            (he.u === e.v && he.v === e.u && he.t === e.t)
    );
    ctx.beginPath();
    ctx.moveTo(a.x, a.y);
    ctx.lineTo(b.x, b.y);
    ctx.strokeStyle = onPath ? '#0a7d33' : '#b0bec5';
    ctx.lineWidth   = onPath ? 3 : 1.5;
    ctx.stroke();
    // Draw timestamp label at midpoint of each edge.
    const mx = (a.x + b.x) / 2;
    const my = (a.y + b.y) / 2;
    ctx.font = 'bold 11px system-ui';
    ctx.fillStyle = onPath ? '#0a7d33' : '#607d8b';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText('t=' + e.t, mx, my - 8);
  }
  // Draw node circles with labels.
  for (const n of NODES) {
    const onPath = highlightPath && highlightPath.includes(n.id);
    ctx.beginPath();
    ctx.arc(n.x, n.y, 18, 0, Math.PI * 2);
    ctx.fillStyle   = onPath ? '#1d3557' : '#e8eef3';
    ctx.strokeStyle = onPath ? '#1d3557' : '#90a4ae';
    ctx.lineWidth = 2;
    ctx.fill();
    ctx.stroke();
    ctx.font = 'bold 14px system-ui';
    ctx.fillStyle = onPath ? '#fff' : '#1d3557';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(n.id, n.x, n.y);
  }
}

// Populate source/target dropdowns with node ids.
const srcEl = document.getElementById('src');
const tgtEl = document.getElementById('tgt');
NODES.forEach(n => {
  const a = document.createElement('option'); a.value = n.id; a.textContent = n.id; srcEl.appendChild(a);
  const b = document.createElement('option'); b.value = n.id; b.textContent = n.id; tgtEl.appendChild(b);
});
tgtEl.value = 'F';

function setStatus(t, cls) {
  const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls;
}

document.getElementById('find').addEventListener('click', () => {
  const src = srcEl.value, tgt = tgtEl.value;
  if (src === tgt) { setStatus('Source and target are the same node.', 'idle'); draw(null, null); return; }
  const path = findTemporalPath(src, tgt);
  if (!path) {
    setStatus(i18nFmt('No temporal path from %src% to %tgt% — the timestamps do not line up.', { src: src, tgt: tgt }), 'bad');
    draw(null, null);
  } else {
    // Collect the earliest valid edge for each hop in the path.
    const hEdges = [];
    for (let i = 0; i < path.length - 1; i++) {
      const u = path[i], v = path[i + 1];
      const candidates = EDGES.filter(e =>
        (e.u === u && e.v === v) || (e.u === v && e.v === u)
      );
      candidates.sort((a, b) => a.t - b.t);
      if (candidates.length) hEdges.push(candidates[0]);
    }
    draw(path, hEdges);
    setStatus(i18nFmt('Path: %path%', { path: path.join(' → ') }), 'ok');
  }
});

document.getElementById('reset').addEventListener('click', () => {
  srcEl.value = 'A'; tgtEl.value = 'F';
  setStatus('Choose source and target, then find a path.', 'idle');
  draw(null, null);
});

draw(null, null);
setStatus('Choose source and target, then find a path.', 'idle');
Result
Console

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.

The Real Complexity

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

What stays easy. Deciding whether a temporal path exists from uu to vv (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 vv 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 kk 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 nn nodes and mm (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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/temporal-networks/Content licensed under CC BY-NC 4.0.