Algorithmic Aspects of Temporal Betweenness

The betweenness centrality of a graph vertex measures how often this vertex is visited on shortest paths between other vertices of the graph. In the analysis of many real-world graphs or networks, betweenness centrality of a vertex is used as an indicator for its relative importance in the network. In particular, it is among the most popular tools in social network analysis. In recent years, a growing number of real-world networks is modeled as temporal graphs, where we have a fixed set of vertices and there is a finite discrete set of time steps and every edge might be present only at some time steps. While shortest paths are straightforward to define in static graphs, temporal paths can be considered"optimal"with respect to many different criteria, including length, arrival time, and overall travel time (shortest, foremost, and fastest paths). This leads to different concepts of temporal betweenness centrality and we provide a systematic study of temporal betweenness variants based on various concepts of optimal temporal paths. Computing the betweenness centrality for vertices in a graph is closely related to counting the number of optimal paths between vertex pairs. We show that counting foremost and fastest paths is computationally intractable (#P-hard) and hence the computation of the corresponding temporal betweenness values is intractable as well. For shortest paths and two selected special cases of foremost paths, we devise polynomial-time algorithms for temporal betweenness computation. Moreover, we also explore the distinction between strict (ascending time labels) and non-strict (non-descending time labels) time labels in temporal paths. In our experiments with established real-world temporal networks, we demonstrate the practical effectiveness of our algorithms, compare the various betweenness concepts, and derive recommendations on their practical use.


Introduction
Graph metrics such as betweenness centrality are studied and applied in many application areas, including social and technological network analysis [19,27], wireless routing [5], machine learning [24], and neuroscience [30]. The betweenness centrality of a vertex in a graph measures how often this vertex is visited by a shortest (or optimal) path. High betweenness centrality scores are strict non-strict Shortest O(n 3 · T 2 ) O(n 3 · T 2 ) Foremost #P-hard #P-hard Fastest #P-hard #P-hard Prefix-foremost O(n · M · log M ) #P-hard Shortest foremost O(n 3 · T 2 ) O(n 3 · T 2 ) Table 1: An overview of the computational complexity of the temporal betweenness variants we consider. Here, n refers to the number of vertices, M refers to the total number of time edges, and T refers to the number of time steps.
usually associated with vertices that can be seen as more important for the network. In static graphs, betweenness centrality is a well-studied concept. It is well-known that Brandes' algorithm [2] 1 computes the betweenness centrality of all vertices of a given static graph with n vertices and m edges in O(n · m) time and O(n + m) space.
In temporal graphs, that is, graphs with fixed vertex set and edge set(s) varying over discrete time steps, the notion of betweenness centrality can be defined in a similar fashion. However, there are more options how to choose "optimal" paths. Depending on the application, a path may be optimal if it minimizes the number of edges ("shortest"), the arrival time ("foremost"), or the overall travel time ("fastest"). For any of these path types we can define and study a variant of temporal betweenness centrality. In addition, combinations of optimality criteria such as shortest foremost temporal paths can be considered. Furthermore, we will distinguish between temporal paths with strictly or non-strictly ascending time labels on the edges. We investigate algorithmic aspects of temporal betweenness variants based on, strict and non-strict, shortest, foremost and fastest paths. In addition, we also consider two subtypes of foremost paths, namely shortest foremost, and prefix-foremost paths.
Our main research question is as follows: How hard-theoretically and practically-is the computation of the different variants of temporal betweenness centrality and what does this imply for their usefulness and applicability in practice?
The various betweenness variants show remarkable differences in their computational complexity: while some of them can be computed in polynomial time, others are computationally hard. Note that computing betweenness values is closely related to counting optimal paths since, informally speaking, the betweenness value of a vertex quantifies how many optimal paths go through this vertex. We show that counting foremost and fastest temporal paths is #P-hard, implying the same hardness result for the computation of corresponding betweenness concept. Since temporal betweenness based on foremost temporal paths is arguably the best motivated variant in many application [23,28] areas and we obtain intractability, we investigate to modifications, namely shortest foremost and (strict) prefix foremost temporal paths. For temporal betweeness based on these modified versions of foremost temporal paths as well as shortest temporal paths, we obtain tractability results.
In Table 1, we give an overview of our theoretical findings. We present formal (worst-case) computational hardness proofs. In the cases where we state polynomial-time computability, we provide algorithms that compute the temporal betweenness scores of all vertices in a given temporal . . . Then v 1 and v 2 are vertices with high temporal betweenness based on temporal paths whereas v 3 has very low temporal betweenness based on temporal paths. However for e.g. foremost temporal walks, v 3 would also have a high temporal betweenness.
graph. We remark that in contrast to the static setting, temporal walks (that visit a vertex multiple times) can also be optimal for certain optimality criteria. In our definition of temporal betweenness centrality we use the number of optimal temporal paths as opposed to the number of optimal temporal walks. This is natural for static graphs because static shortest walks are always paths. In the temporal case, this is not always true-it is possible that there is a non-path temporal walk (that visits a vertex multiple times) that arrives at the same time as the foremost temporal path, so the number of foremost temporal paths and foremost temporal walks between two vertices can be different. Consider the graph shown in Figure 1. Clearly, every walk from the left half to the right passes either v 1 or v 2 and since the edges on the right are only present at exactly one time step, every walk going from left to right is a foremost walk. Intuitively, v 1 and v 2 should have very similar, high betweenness scores, whereas v 3 should be close to zero. But if we use walks instead of paths for our definitions, we get a very high number of walks alternating between v 2 and v 3 before arriving on the right side, so v 2 and v 3 would get a high centrality score. We conclude that paths are more suitable than walks for defining temporal betweenness centrality. Furthermore, we distinguish between strict and non-strict temporal paths.
We provide a thorough formal study of the computational complexity landscape of temporal betweenness centrality, altogether obtaining a fairly complete picture concerning the computation of temporal betweenness. We implemented and compared several of our algorithms (in terms of running time, distribution of the betweenness values, and vertex rankings induced by the betweenness values). From our experimental results we derive conclusions for working with temporal betweenness centrality in applications. Our freely available implementations and the experimental investigations are based on our theoretical findings and provide guidelines for future work with one of the perhaps most fundamental network analysis concepts in a temporal context.

Related work.
There is an enormous amount of work on the concept of betweenness centrality in static graphs, as already indicated by the huge citation numbers concerning Brandes path-breaking algorithm [2]. Betweenness centrality was defined in 1977 by Freeman [7]. We refrain from further discussing the static case which is already discussed in many textbooks.
The theory of temporal graphs is comparatively young [12,13,14,20] but strongly grows in many directions. We focus our discussion of related work on temporal walks, paths, and the computation of temporal betweenness centrality.
Bui-Xuan et al. [3] did an early work on algorithms that find optimal temporal paths (called "journeys" there). In particular, they presented algorithms for shortest, fastest, and foremost temporal paths. Afterwards, Wu et al. [32] provided state-of-the-art algorithms for optimal temporal paths. Based on breadth-first search which finds shortest paths in static graphs, Wu et al. showed that shortest, foremost, fastest and reverse-foremost (strict) temporal paths can be found in a similar fashion. Himmel et al. [11] and Casteigts et al. [4] expanded on the work of Wu et al. and studied a more complex variation of temporal paths and walks with constraints on the waiting time in each vertex. Himmel et al. [11] contributed efficient algorithms to find optimal temporal walks but Casteigts et al. [4] showed that finding optimal temporal paths is NP-hard in settings with upper bounds on the waiting time.
While betweenness centrality in static graphs is a well studied concept, the study of betweenness centrality in temporal graphs is rather young. Tang et al. [28] argued that temporal graphs are more suitable to represent the dynamics of social and technical networks and introduced temporal variants of centrality metrics such as closeness and betweenness centrality based on foremost temporal paths. Building on this, Tang et al. [26] used their notion of temporal closeness to analyze the containment of malware in mobile phone networks. Nicosia et al. [21] also discussed temporal variants of betweenness and closeness centralities, as well as other temporal graph metrics. They mostly give an overview on different definitions. Kim and Anderson [16] defined the temporal betweenness centrality of a vertex based on shortest paths in the so-called static expansion, a static directed graph, and give a polynomial-time algorithm for computing the temporal betweeness values. Notably, a path in the static expansion may represent a non-path temporal walk in the corresponding temporal graph. Afrasiabi Rad et al. [23] studied foremost walk temporal betweenness and observed #P-hardness, presented an exponential-time algorithm and conducted corresponding experiments.
We finish with pointing to some more references of the meanwhile already rich literature on computing (variants of) temporal betweenness centrality. Note that the several temporal graph surveys [12,13,14,18] already provide some definitions of temporal betweenness centrality. As mentioned before, most works [1,10,16,23,28] work with temporal walks, not temporal paths. Also, they usually do not make the point of distinguishing between strict and non-strict paths. To the best of our knowledge, there is no work on systematically classifying the computational complexity of temporal betweenness computation.
Organization of the paper. In Section 2 we provide the basic notation used in this paper as well as some preliminary observations. In Section 3 we prove computational hardness for some variants of temporal betweenness (see Table 1) and in Sections 4 and 5 we provide theoretical foundations and algorithms for the remaining temporal betweenness concepts. In Section 6 we present our experimental evaluation of the algorithms described in Section 5. We conclude in Section 7.

Preliminaries & Basic Observations
In this section, we introduce the most important mathematical definitions and terminology used in this paper. We further present some basic observations.

Temporal Graphs and Paths
The fundamental mathematical object we are concerned with are temporal graphs. We only consider undirected temporal graphs. However, temporal paths and walks are implicitly directed because of the ascending time labels. Hence, we need a notion for directed transitions on a temporal path or walk which indicate not only which time edge is used but also in which direction. For any time edge e = ({v, w}, t) we call (v, w, t) the transition from v to w at time step t. We call v the starting point and w the endpoint of the transition. Using this, we can now define temporal walks and temporal paths.
Definition 2.2 (Temporal Walk). A temporal walk W on a temporal graph G from vertex s to vertex z is an ordered sequence of transitions (e 1 , . . . , e k ) ∈ E k such that the endpoint of e i is the starting point of e i+1 and t(e i ) ≤ t(e i+1 ) for each i ∈ {1, . . . , k − 1}. We call a temporal walk strict if t(e i ) < t(e i+1 ) for each i ∈ {1, . . . , k − 1}.
A temporal walk may visit the same vertex more than once. In contrast to that, a temporal path visits each vertex at most once. This is analogous to the definitions for static graphs. For readability, we use the notation v t → w instead of the triple (v, w, t). Since the endpoint of a transition is equal to the starting point of the next one for any walk, we use a shortened notation omitting the doubled vertices. For instance, we denote the "middle" temporal path from s to z in Figure 2 In this example, P is a temporal path since all involved vertices are visited only once. Moreover, P is a strict temporal path because the time labels are strictly ascending.

Optimality of Temporal Paths
In static graphs, shortest paths are a central concept. In temporal graphs, there are different concepts of optimal paths. Figure 2 illustrates three of the most common optimization criteria: shortest, foremost, and fastest [3].
→ z) is foremost, and More formally, we use the following definitions: Definition 2.4. Let G = (V, E, T ) be a temporal graph. Let s, z ∈ V and let W be a temporal walk from s to z.
• W is a shortest walk if there is no walk W ′ from s to z such that W ′ contains less transitions than W .
• W is a foremost walk if there is no walk W ′ from s to z such that W ′ has an earlier arrival time than W .
• W is a fastest walk if there is no walk W ′ from s to z such that the difference between arrival and start time is smaller for W ′ than it is for W .
A temporal path is shortest, foremost, or fastest if it is a shortest, foremost, or fastest temporal walk, respectively. Note that for the optimality criteria "foremost" and "fastest" optimal temporal walks are not necessarily temporal paths. Imagine a temporal graph where all time edges incident to s have the same time label and also all time edges incident to z have the same time label. Then every walk from s to z (if exists) is foremost and fastest, since all walks leave s at the same time and arrive at z at the same time.
Together with the distinction between strict and non-strict, this gives us six different types of optimal temporal paths. In the following, we use the term "⋆-optimal" temporal path, where ⋆ denotes the type.
Next, we introduce terminology and notation for counting optimal temporal paths.
sz is the number of ⋆-optimal temporal paths from s to z.
We define σ (⋆) vv := 1. We further introduce terminology and notation for counting optimal temporal paths that visit a certain vertex or a certain vertex appearance. Definition 2.6. Let v ∈ V be any vertex and let t ∈ [T ] be a time step. Then, is the number of ⋆-optimal paths that pass through v, and is the number of ⋆-optimal paths that pass through v exactly at time step t, i.e., the paths that contain the transition u t → v for some u ∈ V .
We set σ sz /T . Note that these are corner cases where the we can get non-integer values. This technically does not fit the intuition and description that we express numbers of paths with certain properties but this is rather done to keep certain proofs simpler by avoiding to discuss these corner cases explicitely.

Temporal Betweenness Centrality
In static graphs, the betweenness centrality of a vertex measures how often this vertex is passed on shortest paths between pairs of vertices in the graph. Freeman [7] defines the betweenness centrality As we have seen above, there are different notions of optimal paths (i.e., fastest, shortest, foremost) in temporal graphs. Thus, there are several options how to define temporal betweenness centrality based on any of these notions. Moreover, we do not want to assume that there is a temporal path from any vertex to any other vertex in the graph. That is, we assume that there are vertex pairs s, z with σ sz = 0 which we want to leave out when summing over all vertex pairs. To formalize this, we use a connectivity matrix A of the temporal graph: Formally, temporal betweenness with respect to these different concepts of path optimality is defined as follows.
Definition 2.7 (Temporal Betweenness). The temporal betweenness of any vertex v ∈ V is given by: For this paper, we use a slightly different version of temporal betweenness which is defined for vertex appearances and show that the temporal betweenness as defined above can be easily computed from the modified version. This allows us to simplify some of our proofs. We drop the condition that when summing over all vertex pairs, these vertices have to be different from the vertex of which we want to know the betweenness. Formally, we definê We can observe that using the connectivity matrix A for the temporal graph, we can compute the temporal betweenness C Proof. We show the above claim as follows.

Computationally Hard Temporal Betweenness Versions
In this section, we state counting problems closely related to temporal betweenness, including the computation of temporal betweenness itself, and show that they are #P-hard. In particular, we will show that counting all temporal paths is #P-hard for both strict and non-strict paths. The same holds true for foremost and fastest temporal paths, but not for shortest temporal paths. Our hardness results are based on the following two counting problems for which Valiant [29] showed #P-completeness: 2

Paths
Input: A static graph G = (V, E), two vertices s, z ∈ V . Task: Count the number of different paths from s to z in G.

Imperfect Matchings
Input: A bipartite static graph. Task: Count the number of different matchings (of any size) in G.
We use polynomial-time counting reductions 3 from the two problems above to prove that counting problems related to temporal betweennes are #P-hard. More specifically, we show the #Phardness of the following problems: (Strict) Temporal Paths Input: A temporal graph G = (V, E, T ), two vertices s, z ∈ V . Task: Count the number of (strict) temporal paths from s to z in G.

Foremost (Strict) Paths
Input: A temporal graph G = (V, E, T ), two vertices s, z ∈ V . Task: Count the number of foremost (strict) temporal paths from s to z in G.

Fastest (Strict) Paths
Task: Count the number of fastest (strict) temporal paths from s to z in G.
Task: Compute the betweenness centrality of v in G.
As also observed by Afrasiabi Rad et al. [23], for non-strict paths the #P-hard problem Paths is contained as a special case in Temporal Paths, since any static graph can be transformed into an equivalent temporal graph with lifetime T = 1. Furthermore, each temporal path in this instance is also foremost and fastest. Hence, we have the following: The counting problem Strict Temporal Paths is #P-hard as well, but the proof is more technical since strict paths are fundamentally different from static paths, whereas non-strict paths could be regarded as a generalization of static paths, allowing for the simple argument used above. We show the #P-hardness of Strict Temporal Paths by a polynomial-time counting reduction from Imperfect Matchings.
Proof. We reduce from the #P-complete problem Imperfect Matchings [29]. Given a bipartite graph such that the number of non-empty matchings in G is equal to the number of strict temporal paths from a ′ to b ′ in G. An example for the transformation is shown in Figure 3 and it is easy to check that the transformation can be computed in polynomial time.
The temporal edge set E is constructed as follows: For each edge {a i , b j } ∈ E, we create a temporal edge ({a i , b j }, 2 · i). These edges are meant to represent the edges of the original graph and will be called forward-edges. The vertices a i ∈ A are connected to a ′ at time step 2 · i − 1. All b j ∈ B are connected to b at the last time step T . For i > 1 we connect each a i to each b j at time step 2 · i − 1; these edges are drawn dashed in orange in Figure 3 and we will refer to them as back-edges.
We justify the terms forward-edge and back-edge by showing that for any temporal path from a ′ to b ′ , every transition with an even time label goes from an a ∈ A to a b ∈ B (forward) and exactly : Given a static bipartite graph G, we construct a temporal graph G such that the number of matchings in G equals the number of strict paths from a ′ to b ′ in G. In this example, the matching the other way from a b ∈ B to an a ∈ A (back ) for every transition with an odd time label. By construction, each vertex a i ∈ A is incident to time edges with at most two time labels: 2 · i − 1 and 2 · i. Hence, any temporal path containing a transition b j 2·i → a i ends in a i since no time edge with a higher time label will be available. By an anologous argument, back-edges cannot be used forwardly because it is impossible to arrive in a i before time 2 · i − 1.
As a consequence, on any temporal path from a ′ to b ′ , every back-edge is followed by a forwardedge and every forward-edge is followed either by a back-edge or by the final edge to b ′ . Thus, for any matching M = {{a i 1 , b j 1 }, . . . , {a im , b jm }} of size m ∈ N + there is exactly one temporal path from a ′ to b ′ containing exactly the forward edges corresponding to M , and conversely, for each temporal path P from a ′ to b ′ there is exactly one matching corresponding to the forward-edges in P . Thus, the number of non-empty matchings in G equals the number of temporal paths from a ′ to b ′ in G which implies that we have a polynomial-time counting reduction.
Analogously to the case of non-strict paths, the #P-hardness of Strict temporal paths implies the #P-hardness of Strict Foremost Paths and Strict Fastest Paths. We have shown that counting strict and non-strict temporal paths is #P-hard. This allows us to prove this section's main result. Proof. We prove the #P-hardness by a polynomial-time counting reduction from (Strict) Temporal Paths. Let G = (V, E, T ) be a temporal graph with vertices a and b. Let p be the number of (strict) temporal paths from a to b. We construct a temporal graph The construction is illustrated in Figure 4 and can clearly be computed in polynomial time.
By construction, every temporal path from a ′ to b ′ is both fastest and foremost and there are exactly four (fastest/foremost) temporal paths going through v ′ , connecting the pairs (a, b), (a, b ′ ), (a ′ , b), and (a ′ , b ′ ), respectively: T + 2 Figure 4: Given a temporal graph G, we construct a temporal graph G ′ such that we can compute the number of a-b-paths in G from the betweenness of v in G ′ .
We observe that for each of these four pairs, there are p + 1 foremost (and fastest) (strict) temporal paths, and for any other pair of vertices, no temporal path goes through v at all. This allows us to compute p from the temporal betweenness centrality based on foremost (fm) or fastest (fa) temporal paths of v: This implies that we have a polynomial-time counting reduction.

Counting Temporal Paths and Temporal Dependencies
In the previous section, we have shown that computing the temporal betweenness centrality based on fastest or foremost paths is #P-hard. Now we investigate ways to extend the approach of Brandes' algorithm [2] for static graphs to variants of temporal betweenness based on types of optimal temporal paths for which the counting problem is not intractable. In this section we provide the theoretical foundations for designing efficient algorithms to compute temporal betweenness centrality.

Counting Shortest Temporal Paths
We first show how we can count shortest temporal paths efficiently. Our results from Section 3 indicate that this is not possible for the case of foremost and fastest temporal paths.
As it turns out, what we need to count is a slightly different version of shortest temporal paths, which we call t-shortest temporal paths. A temporal path P from s to z is a t-shortest temporal path if it arrives at time t and if there is no temporal path P ′ from s to z which arrives at time t and is shorter than P . We show that similarly to the static case, t-shortest temporal paths P have the property that every prefix is a t ′ -shortest temporal path, where t ′ is the time when the prefix arrives at its last vertex. Formally, we show the following.
be a t-shortest temporal path from s to z.
Proof. Assume that P = (s is not a t ′ -shortest temporal path. Then there is a shorter temporal path P ′′ = (s Lemma 4.1 allows us to formulate a recursive relation of the number of shortest temporal paths. To do this, we need to define the predecessor of a vertex appearance (v, t) on a temporal path as the vertex appearance (w, t ′ ) where the path arrived last, that is, (w, t ′ ) is predecessor of (v, t) on P if and only if P contains the transitions s (v, t) denotes the set of predecessors of (v, t) on ⋆-optimal temporal paths starting at s.
If we want to use the predecessor relation to formulate recursive function, then we need that the relation behaves acyclicly. To show this formally, we define the directed predecessor graph for ⋆-optimal temporal paths starting at some vertex s ∈ V as follows. Given a temporal graph G, the vertex set of the predecessor graph is the set of vertex appearances in G. The arc set is given by the ordered pairs of vertex appearances such that there is a ⋆-optimal temporal path starting at s that arrives in these vertex appearances in that order, that is, we add an arc from a vertex appearance (v, t) to another vertex appearance (w, t ′ ) if (v, t) ∈ P  where It is easy to observe that the predecessor graph is acyclic for all strict optimal temporal path versions, since the time stamps of the vertex appearances are strictly increasing along the arcs of the graph. In the case of t-shortest temporal paths, we show next that this also holds in the non-strict case. Proof. Proof by contradiction. Let G = (V, E, T ) be a temporal graph with source s. Let dist : V × [T ] → N be the function that returns the length of the shortest path in the predecessor graph G (n-t-sh) pre (s) from s to any vertex appearance. Note that for any vertex appearance (v, t ′ ) we have that dist(v, t ′ ) is also the length of a t ′ -shortest temporal path from s to v. Hence, for any vertex appearances (v, t ′ ) and (w, t ′′ ), if the predecessor graph contains the arc ((v, t ′ ), (w, t ′′ )), then dist(v, t ′ ) < dist(w, t ′′ ). Assume that G (n-t-sh) pre (s) contains a cycle C = ((v, t ′ ), . . . , (v, t ′ )). Then dist(v, t ′ ) < dist(v, t ′ ), a contradiction.
By an analogous argument, we get the following, which we need in the next subsection. With the help of this notation and Lemma 4.1 (and Lemma 4.4 for the non-strict case), we can formulate the following recursion for the number of t-shortest temporal paths. Corollary 4.6 (Counting of t-Shortest Temporal Paths). Let s be a source and let z be a vertex with s = z. The number of t-shortest temporal paths (t-sh) from s to z is given by:

Temporal Dependencies
Similar to Brandes [2] we introduce so-called dependencies to obtain an alternative formulation for the betweenness which we then use for the actual computation. Recall the definition of (static) betweenness centrality where σ sz is the number of all shortest paths from s to z and σ sz (v) is the fraction of these paths which pass through v. Brandes [2] calls the latter the pair-dependency of s and z on v. Brandes' central observation is that the betweenness centrality can be computed faster by first computing partial sums of the form the dependency of s on v. He showed that the dependencies obey a recursive relation which can be exploited algorithmically. Both concepts, dependencies and pair-dependencies, naturally generalize to optimal paths in temporal graphs. In some cases, we may be interested in the dependency on a vertex at a specific time instead of the whole lifetime. Hence, we introduce temporal dependencies of vertex appearances: From our definition of the modified temporal betweenness of a vertex appearance it follows that we can use the temporal dependencies to compute it.
Now we state our central result allowing us to design algorithms to compute the temporal betweenness centrality based on shortest temporal paths.
Proof. We start by rewriting the pair-dependency of a vertex appearance as the summed fractions of shortest temporal paths using a specific transition from v to some vertex w at some time step: where δ (sh) sz ((v, t), ({v, w}, t ′ )) is the fraction of shortest temporal paths from vertex s to z that use the transitions v ′ t → v t ′ → w for some v ′ . Note that for the case that z = v there is no vertex appearance (w, t ′ ) such that (v, t) ∈ P sh s (w, t ′ ), hence we need δ (sh) sv (v, t) as an additional summand. Furthermore, we have that Inserting these cases into the double sum above yields the following: The lemma statement now follows immediately.
Lemma 2.8 together with Observation 4.8 show that we can use temporal dependencies to compute temporal betweenness centrality. Lemma 4.9 shows that the temporal dependencies obey a recursive relation and Lemma 4.5 shows that it is cycle-free. This together with Corollary 4.6 allows us to design a polynomial-time algorithm to compute temporal betweenness centrality based on shortest temporal paths. Before we give the specific algorithm description and running time analysis, we describe some other temporal betweenness concepts that can be computed in a similar fashion.

Specialized Optimality Concepts
So far, our results allow us to efficiently compute the temporal betweenness for strict and non-strict shortest temporal paths. For all other of the six canonical variants we have shown computational hardness results in Section 3. In the following, we show that for some specialized optimality concepts for temporal paths, we can also efficiently compute the corresponding temporal betweenness. Specifically, we consider shortest foremost temporal paths and prefix-foremost temporal paths.
Shortest foremost temporal paths. A shortest foremost path is a foremost temporal path that is not longer than any other foremost temporal path. It may not be a shortest temporal path overall, however, as even shorter temporal paths with higher arrival times may exist. Shortest foremost temporal paths can be regarded as temporal paths that prioritize a low arrival time and use a low edge count as a tie-breaker. Definition 4.10. Let s, z ∈ V . A temporal path P from s to z is a shortest foremost temporal path if P is a foremost temporal path from s to z and for all foremost temporal paths P ′ from s to z it holds: |P | ≤ |P ′ |.
We observe that a shortest foremost temporal path is a t-shortest temporal path for the earliest possible arrival time. Hence, our findings in the previous subsection translate very easily to shortest foremost temporal paths.
Prefix foremost temporal paths. Now we consider the class of foremost temporal paths for which every prefix of the temporal path is foremost as well. That is, every vertex that is visited by such a temporal path is visited as soon as possible. These temporal paths are called prefix foremost paths.
Definition 4.11. Let s, z ∈ V . A path P = (e 1 , . . . , e k ) from s to z is a prefix foremost temporal path if P is a foremost path and every prefix P ′ = (e 1 , . . . , e k ′ ), k ′ ≤ k is a foremost temporal path as well.
Wu et al. [32] showed that there is always at least one prefix foremost path between any pair of vertices s and z unless z is not reachable from s at all. We can observe that in the straightforward reduction from Paths that yields Proposition 3.1 we also get that counting nonstrict prefix foremost temporal paths is computationally hard. The main difference between strict and non-strict prefix foremost paths foremost paths is that in the former case, the predecessor relation is acyclic, and in the latter it is not. Intuitively, this is the reason why we get hardness in the non-strict case and tractability for the strict version.
For strict prefix foremost paths, one can show that the counting problem and the computation of the corresponding betweenness are solvable in polynomial time by very similar arguments as for shortest temporal paths. The main difference is that the time stamp of a predecessor is unique, hence we can define the set of predecessors as a set of vertices as opposed to a set of vertex appearances, otherwise the arguments are analogous to the ones used in the proof of Lemma 4.9. This allows us to simplify the recursive function for the temporal dependency for prefix foremost temporal paths which also results in a faster computation.
Proof. We start by rewriting the pair-dependency of a vertex appearance as the summed fractions of prefix foremost temporal paths using a specific transition from v to some vertex w at some time step: , w}) is the fraction of prefix foremost temporal paths from vertex s to z that use the transitions v t → w for some t. Note that for the case that z = v there is no vertex w such that v ∈ P (pfm) s (w), hence we need δ (pfm) sv (v) as an additional summand. Furthermore, we have that Inserting these cases into the double sum above yields the following: The lemma statement now follows immediately.

Algorithms and Running Time Analysis
In the following we give detailed descriptions of the algorithms we use to compute the temporal betweenness variants discussed above. Brandes' algorithm [2] (for static graphs without edge weights) is based on breadth-first search. For each vertex, the Single-Source Shortest Paths problem is solved once. At the end of each iteration, the dependency of the respective s on all other vertices v is added to the betweenness score of s. Our algorithms for temporal betweenness will follow roughly the same structure. Instead of breadth-first search, the appropriate algorithm for the respective temporal path class is used as the base for the algorithm. To describe our algorithm formally, we need the notion of temporal neighborhoods. Shortest (foremost) temporal betweenness. We have shown that the temporal dependencies for shortest (foremost) paths follow a similar recursion as for static graphs.
Algorithm 1 uses a |V | × T -table to store the number of shortest temporal paths to all vertex appearances. The overall structure of the algorithm is similar to Brandes' algorithm [2]-a singlesource-all-shortest-paths traversal from each vertex to all vertex appearances is performed and the count of shortest temporal paths is stored in the aforementioned table. At the end of each iteration, we add the dependencies found for each vertex appearance to the betweenness score of the respective vertex.
In order to count shortest foremost temporal paths instead of shortest temporal paths, only the dependency accumulation needs to be changed: instead of checking whether the paths have minimal length, the algorithm checks for minimal arrival time. Proof. The correctness of Algorithm 1 follows from Lemma 2.8 together with Observation 4.8, which show that we can use temporal dependencies to compute the temporal betweenness, and from Corollary 4.6 and Lemma 4.9 (with Lemma 4.5) since our algorithm dynamically computes the values given by the recursive formulas stated in the lemmas.
It is easy to check that the running time of Algorithm 1 is upper-bounded by |V | (the outer loop in Line 1) times the total number of elements in Q (the loop from Line 10) times the maximum size of a temporal neightborhood (the loop from Line 12). Both the total number of elements in Q and the maximum size of a temporal neightborhood is in O(|V | · T ). The claimed running time follows.
The space consumption of Algorithm 1 is in O(|V | · T + |E|), since we need to store matrices of size |V | · T for the temporal path counts and the temporal dependencies.
Strict prefix foremost temporal betweenness. Algorithm 2 modifies Brandes' algorithm [2] to count strict prefix foremost temporal paths. The overall structure of the algorithm remains the same. Instead of iterating over all neighbors, however, we add add all temporal edges of a vertex into a priority queue (prioritizing early time labels). This allows us to traverse the graph in a time-respecting manner and find the prefix foremost temporal paths.
Notably, since the time labels of predecessors are unique in prefix foremost temporal paths, we do not have to consider vertex appearances in this case. Intuitively, this is the main reason why we can achieve both a faster running time a lower space consumption. Proof. The proof is essentially analogous to the correctness proof for Algorithm 1 but uses Lemma 4.13.
It is easy to check that the running time of Algorithm 2 is upper-bounded by |V | (the outer loop in Line 1) times the size of Q (the loop from Line 9) times the time necessary to dequeue (Line 10). The size of Q is in O(|E|) and the time to dequeue is in O(log |E|). Here, we assume that |V | ≤ |E|. The claimed running time follows.
The space consumption of Algorithm 2 is in O(|E|+|V |) the arrays for the temporal path counts and the temporal dependencies used in the algorithm are all of size |V |.

Experimental Evaluation
In this section, we analyze the running time of our implementations of Algorithm 1 (computing strict and non-strict shortest and shortest foremost temporal betweenness) and Algorithm 2 (computing strict prefix foremost temporal betweenness) on several real-world temporal graphs and we investigate the differences between the five different betweenness concepts our algorithms can compute.

Setup and Statistics
We implemented 4 Algorithm 1 and Algorithm 2 in C++ and carried out experiments on an Intel Xeon E5-1620 computer with four cores clocked at 3.6 GHz and with 64 GB RAM. We did not utilize the parallel-processing capabilities. The operating system was Debian GNU/Linux 6.0.
We used the following freely available data sets for temporal graphs: Physical-proximity net-

Experimental Results
We now discuss the results of our experiments. We analyzed the influence of the temporal betweenness type on the running time, the distribution of the temporal betweenness values, and the ranking of the ten vertices with the hightest temporal betweenness values.
Running time. As indicated by our theoretical running time bounds (see Table 1), Algorithm 1 (computing shortest and foremost shortest betweenness) is several orders of magnitudes slower than Algorithm 2 (computing prefix foremost betweenness). Algorithm 1 solved all instances except for "karlsruhe" and "infectious" (which where not solved within the timeout of three hours) within 45 minutes (keep in mind that Algorithm 1 computes shortest and foremost shortest temporal be- Table 2: Statistics for the data sets used in our experiments. The lifetime T of a graph is the difference between the largest and smallest time stamp on an edge in the graph. The resolution r indicates how often edges were measured. The last three columns state the running times in seconds of our implementation. A -1 indicates that the instance was not solved within three hours.  tweenness simultaneously). Algorithm 2 solved all instances except "karlsruhe" within 30 seconds. We show the specific running times in Table 2.
Impact of temporal betweenness type on the temporal betweenness distribution. In Figure 5 we exemplarily show histograms of the temporal betweenness values of the "highschool-2013" data set, the "facebook-like" data set, and the "primaryschool" data set. We can observe that the temporal betweenness centrality has a power-law-like distribution and the temporal betweenness type does not have a strong influence on the distribution in the "highschool-2013" data set and the "facebook-like" data set (which is the case in most data sets). In the "primaryschool" data set however, the distributions for non-strict shortest and strict shortest temporal betweenness are very similar but the other ones are quite different from each other.
Impact of temporal betweenness type on the vertex ranking. In Table 3 we present Kendall's tau correlation measure 6 [17] for each pair of vertex rankings induced by the different temporal betweenness versions. For the temporal betweennes variants "shortest" and "shortest foremost" we can observe that their respective non-strict and strict variants produce very similar rankings. We can further see that the betweenness variants "non-strict shortest foremost", "strict Middle: Temporal betweenness histogram of "facebook-like" data set. The y-axis is on a log-scale. Bottom: Temporal betweenness histogram of "primaryschool" data set. The temporal betweenness types from left to right are: non-strict shortest, non-strict shortest foremost, strict shortest, strict shortest foremost, strict prefix foremost. Table 4: Size of the intersection of each pair of sets containing the ten vertices with highest temporal betweenness values.
These findings are supported by the pairwise comparisons of the sets of the ten vertices with the largest temporal betweenness values, which are presented in Table 4. Notably, the "primaryschool" has quite different top ten vertex sets for all pairs of betweenness variants that do not fall into the above mentioned pairings. We can also observe that "non-strict shortest" and "strict prefix foremost" produce the most dissimilar vertex rankings and top ten sets.

Conclusion
We investigated several variants of temporal betweenness centrality based on the various optimization criteria for temporal paths. We have shown a surprising discrepancy in their computational complexity: while some variations are #P-hard, others can be computed in polynomial time. More specifically, we found that counting foremost, and thus fastest paths, is #P-hard, and in turn, the computation of the corresponding betweenness centrality scores is #P-hard as well. In contrast to that, one can count shortest and shortest foremost temporal paths in polynomial time both for strict and non-strict paths. In the case of prefix-foremost paths, however, we found a polynomialtime algorithm for the strict version, whereas the non-strict version is again #P-hard. An intuitive explanation for this behavior might be that our algorithms strongly rely on a recursive formulation for the so-called temporal dependencies, which in turn requires that the predecessor relation of optimal temporal paths is acyclic and that prefixes of optimal temporal paths are also optimal. For all optimal temporal path types for which we show computational hardness of the corresponding counting problem, one of the two mentioned requirements is not given.
As to challenges for future research, one direction is to attack the temporal betweenness centrality variants which we have shown to be computationally hard by means of approximation algorithms or the development of fixed-parameter algorithms (e.g. for some structural graph parameters of the underlying graph). Roughly in the same direction would be to undertake a closer study of the special structures of real-world networks that might be algorithmically exploitable. A line of research directly motivated by our experiments would be to explore how to decrease the memory consumption of our algorithms-the practical limitations seem to mainly come from the high space consumption, at some point leading our algorithms to do a lot of paging. Specifically, our algorithm for shortest and shortest foremost temporal betweenness stores dependency and path count values for every vertex-time step combination. This is major difference to the static algorithm of Brandes [2] which is less vulnerable in this respect.
On the experimental side, we can observe that the temporal betweenness type does not have a strong impact on the distribution of the betweenness values. When comparing the vertex rankings produced by the betweenness values we can observe that there is little difference between strict and the respective non-strict variants. Furthermore, "shortest foremost" and "prefix foremost" yield similar results, while the strict prefix foremost temporal betweenness values can be computed significantly faster.
It would also be interesting to compare our results to results obtained by static expansion based temporal betweenness algorithms (both in terms of running time and betweenness values). We also believe it would be very enlightening to compare the betweenness values of the two tractable variants of temporal betweenness based on foremost paths (shortest foremost and prefix foremost) to the betweenness values for temporal betweenness based on foremost temporal paths (which is intractable).