Centrality Metrics

TODO: input definitions and check for duplicates

</aside>

Vital tools in network analysis, designed to measure the importance of nodes within temporal graphs.

Unlike traditional centrality measures that consider static snapshots of networks, temporal centrality metrics incorporate the dimension of time, enabling more nuanced insights into the dynamic interactions within networks.

These metrics, including temporal closeness, betweenness, and degree centrality, help in identifying key nodes and understanding their roles over time, providing crucial information for fields ranging from epidemiology to communication network analysis. By integrating temporal data, these metrics offer a more comprehensive view of the structural and functional significance of nodes in evolving networks.

Builds on the initial work by Kempe, Kleinberg, Kumar who proposed the temporal network model and temporal distance. Note that both temporal graphs and temporal distance (computing temporal paths) have been studied decades before, but in a less structured way and not under the name of ‘temporal graphs’. Refer to History and Names of “Temporal Graphs”.

Untitled

We give a quick summary of optimal temporal paths. For more details refer to Temporal Paths/Trips/Journeys.

Definition: A temporal path between vertices $u$ and $v$ in a temporal graph $\mathcal{G}$, is a sequence of adjacent temporal edges respecting time: $P=((v_0,v_1,t_1), (v_1,v_2,t_2), \dots, (v_{\ell-1},v_\ell,t_\ell))$ with $v_0=u,v_\ell=v$ and $t_i\leq t_{i+1}$ for $i\in[0]$.

A temporal path is called strict if $t_i<t_{i+1}$, otherwise it is non-strict.

An optimal temporal path can be defined in multiple ways:

earliest arrival / foremost path
latest departure
shortest travel time
shortest hop distance </aside>

Definition: The temporal distance between two vertices is defined as the shortest travel time on any temporal path.

</aside>