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. The edges are present only at specific points in time and reachability is defined via temporal paths which move through time and space. This notion is inherently directed because of the temporal order of the edges. As a consequence, temporal reachability is not transitive and there is no unique generalisation of the static concept of connected components. I'm general, “temporal connected components” need not partition the vertex set, may overlap, and can be exponentially many.

Two different perspectives on temporal connected components have emerged:

  1. Path-based, where components are defined in terms of temporal paths between vertices. Most prominently, open and closed temporal connected components and unilateral variants. Their behavior can be influenced by the setting of directed vs undirected edges and strict vs non-strict interpretations of temporal paths.
  2. Snapshot-based, where components are defined by requiring connected subsets of vertices across consecutive snapshots. A related but different concept is the temporal clique.

History on temporal connected components

Literature on temporal connected components

Notions of Temporal Connected Components

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: $u\curvearrowright v$ and $u\curvearrowleft v$.

Connected Component Basis Condition (concise) Notes
open 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$. 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$.
open TUCC Path-based Maximal $X\subseteq V$ s.t. for all $u,v\in X$ there exists a temporal path $u\curvearrowright v$ or $u\curvearrowleft v$. Unilateral
closed TUCC Path-based Maximal $X\subseteq V$ s.t. for all $u,v\in X$ there exists a temporal path $u\curvearrowright v$ or $u\curvearrowleft v$ whose intermediate vertices lie in $X$. Unilateral
$T$-interval CC Snapshot-based
Intersection over window of length $T$ Maximal $X\subseteq V$ and a time window $W$ of length $T$ s.t. 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) s.t. $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$ s.t. $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$ s.t. 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]$ s.t. $X$ is a static connected component in the static expansion of $\mathcal{G}$. As they 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]$.

Computational Complexity

There are three different questions in regards to these notions (note that a $\varphi$-tcc is a (1) maximal and (2) temporally $\varphi$-connected set):

  1. Given a temporal graph and an integer $k$. Does there exist a tcc of size at least $k$?
  2. Given a temporal graph and a subset $X\subseteq V$. Is $X$ a temporally $\varphi$-connected set?
  3. Given a temporal graph and a temporal $\varphi$-connected set $X$. Is $X$ maximal (i.e., a $\varphi$-tcc)?

Refer to the following pages for the state of the art for these three questions of path-based and snapshot-based tccs.

Path-Based Complexity:

Path-Based Temporal Connected Components (Computational Complexity)

Snapshot-Based Complexity:

Snapshot-Based Temporal Connected Components (Computational Complexity)