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 path 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. In 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 of temporal connected components