Temporal connected components are generalisations of static connected components to temporal graphs, aiming to capture which vertices remain mutually reachable when edges are only available at specific points in time.
In static graphs, connectivity and corresponding communities are straightforward: connected components form a partition of the vertex set. In undirected graphs, any two vertices in the same component can reach one another by consecutive undirected edges (path). In directed graphs, one distinguishes between strongly connected components, where every pair of vertices in the component can reach each other via directed paths, and weakly connected components, where directions are ignored and vertices are connected if they lie in the same connected component of the underlying undirected graph.
In temporal graphs, however, connectivity behaves quite differently. Since edges are only available at certain times, reachability is defined via temporal paths (also called journeys). This notion is inherently directed because of the temporal order of the edge. As a consequence, temporal reachability is not transitive, and there is no unique generalisation of the static concept of connected components. “Temporal connected components” need not partition the vertex set, may overlap, and can be exponentially many in number.
Two different perspectives on temporal connected components have emerged.
The first is path-based, where components are defined in terms of temporal paths between vertices. This includes notions such as open and closed temporal connected components, and its behavior can be influenced by the setting of directed vs undirected edges and strict vs non-strict interpretations of temporal paths.
The second is snapshot-based, where components are defined by requiring subsets of vertices to remain connected across a sequence of consecutive snapshots. One of these notions is nowadays studied as temporal clique.
Conventions. A temporal graph $\mathcal{G}=(V,E, \lambda)$ contains one snapshot $G_t$ per time step $t\in[\Lambda]$. A temporal path from $u$ to $v$ ($u \curvearrowright v$) is a time-respecting path through the footprint using edges available at nondecreasing times (strict: $<$; non-strict: $\le$). “Mutual reachability” or “compatibility” means: journey $u\curvearrowright v$ and $u\curvearrowleft v$.
| Connected Component | Basis | Condition (concise) | Notes |
|---|---|---|---|
| open TCC | Path-based | Maximal $X\subseteq V$ such that for all $u,v\in X$ there exist temporal paths $u\curvearrowright v$ and $u\curvearrowleft v$. | Temporal paths may visit vertices outside $X$. |
| closed TCC | Path-based | Maximal $X\subseteq V$ s.t. for all $u,v\in X$ there exist temporal paths $u\curvearrowright v$ and $u\curvearrowleft v$ whose intermediate vertices lie in $X$. | Equivalently: |
| temporal paths inside the induced temporal subgraph on $X$. | |||
| $T$-interval CC | Snapshot-based | ||
| Intersection over window of length $T$ | Maximal $X\subseteq V$ and a time window $W$ of length $T$ such that the same connected spanning subgraph on $X$ is present in every snapshot of $W$ | Equivalently: | |
| $\bigcap_{t\in W} G_t[X]$ contains a connected spanning subgraph | |||
| persistent CC (PCC) | Snapshot-based | Maximal $X\subseteq V$ and a time window $W$ (maximum length) such that $G_t[X]$ is a static connected component for each $t\in W$. | The connected spanning subgraph may vary with $t$. |
| Note: two optimization criteria: size and length. | |||
| window-CC | Snapshot-based | ||
| Union over window $W$ | Maximal $X\subseteq V$ such that $X$ forms a static connected component in the union graph $G^{\cup W}=\;\bigcup_{t\in W} G_t$ for a given window $W$. | Ignores temporal order; useful as a coverage baseline. | |
| $\delta$-CC | Windowed path-based | Maximal $X\subseteq V$ such that for every window $W$ of length $\delta$, $X$ is an open/closed TCC inside $W$ (temporal paths use only time steps in $W$). | Special case of open/closed TCC |
| temporal-vertex CC | Time-expanded graph | Maximal $X\subseteq V\times [\Lambda]$ such that $X$ is a static connected component in the static expansion of $\mathcal{G}$. | Since these are static cc in a static graph, they partition $V\times[\tau]$. |
Notes.
• For directed temporal graphs, replace “connected” by “strongly connected” where appropriate.
• Temporal reachability is directed by time even if the temporal graph is undirected.
• open/closed TCCs can overlap and need not partition $V$; temporal-vertex CCs do partition $V\times[\Lambda]$.