<figure><img src="image_1.png" /></figure>

HAL
open science

# Making Temporal Betweenness Computation Faster and Restless

Filippo Brunelli, Pierluigi Crescenzi, Laurent Viennot

► To cite this version:

Filippo Brunelli, Pierluigi Crescenzi, Laurent Viennot. Making Temporal Betweenness Computation Faster and Restless. KDD '24: The 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Aug 2024, Barcelona, Spain. pp.163-174, 10.1145/3637528.3671825. hal-04901946

HAL Id: hal-04901946

https://hal.science/hal-04901946v1

Submitted on 21 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Making Temporal Betweenness Computation Faster and Restless

Filippo Brunelli¹, Pierluigi Crescenzi², and Laurent Viennot³

¹European Commission — JRC, Seville, Spain

²Gran Sasso Science Institute, L’Aquila, Italy

³Inria, DI ENS, Paris, France

January 21, 2025

## Abstract

Buß et al [KDD 2020] recently proved that the problem of computing the betweenness of all nodes of a temporal graph is computationally hard in the case of foremost and fastest paths, while it is solvable in time $O(n^3T^2)$ in the case of shortest and shortest foremost paths, where *n* is the number of nodes and *T* is the number of distinct time steps. A new algorithm for temporal betweenness computation is introduced in this paper. In the case of shortest and shortest foremost paths, it requires $O(n+M)$ space and runs in time $O(nM) = O(n^3T)$, where *M* is the number of temporal edges, thus significantly improving the algorithm of Buß et al in terms of time complexity (note that *T* is usually large). Experimental evidence is provided that our algorithm performs between twice and almost 250 times better than the algorithm of Buß et al. Moreover, we were able to compute the exact temporal betweenness values of several large temporal graphs with over a million of temporal edges. For such size, only approximate computation was possible by using the algorithm of Santoro and Sarpe [WWW 2022]. Maybe more importantly, our algorithm extends to the case of *restless* walks (that is, walks with waiting constraints in each node), thus providing a polynomial-time algorithm (with complexity $O(nM)$) for computing the temporal betweenness in the case of several different optimality criteria. Such restless computation was known only for the shortest criterion (Rymar et al [JGAA 2023]), with complexity $O(n^2MT^2)$. We performed an extensive experimental validation by comparing different waiting constraints and different optimisation criteria. Moreover, as a case study, we investigate six public transit networks including Berlin, Rome, and Paris. Overall we find a general consistency between the different variants of betweenness centrality. However, we do measure a sensible influence of waiting constraints, and note some cases of low correlation for certain pairs of criteria in some networks.

**Keywords:** node centrality, betweenness, temporal graphs, graph mining

## 1 Introduction

Social network analysis is usually considered to start with the book of Moreno [32], where *sociograms* (that is, graphs) are used to study the relationships between kids from kindergarten to the 8th grade. Successively, Bavelas [1] used sociogram analysis (that is, graph mining) techniques to identify the most important members of a group. Several notions of node importance were successively introduced until Freeman [22] proposed precise different definitions of *node centrality*, such as the degree centrality, the closeness centrality, and the *betweenness centrality*. This latter centrality, which measures how often a node participates in an optimal path, has been repeatedly applied in different research contexts, such as, for example, the analysis of brain, collaboration, citation and, in general, social networks. From a computational point of view, Brandes [7] proposed an algorithm for computing the betweenness centrality of all nodes in time $O(nm)$, where *n*
is the number of nodes and *m* is the number of edges. Due to the huge size of some real-world networks, several approximation algorithms for computing the betweenness centrality have also been proposed in the last twenty years (such as, for example, the ABRA and KADABRA algorithms described in [35, 6]), mostly based on sampling techniques.

More recently, the notion of betweenness centrality has been also applied to the case of tem-
poral graphs. Indeed, many real-world complex networks evolve over time, in the sense that edges
can appear and disappear at specific time instants. As observed in [28], this is due to the fact
that interactions between nodes take place over time, as it happens, for example, in the case of
collaboration, communication, user-product, and transport networks. Many different modeliza-
tions of these evolving networks have been proposed in the literature, such as the *evolving graph*
model analysed in [20], the *time-dependent graph* model studied in [21], the time-varying graph
model [12], or the *link stream* model introduced in [28], and the temporal graph model [31]. A
*temporal graph* is a collection of *temporal edges* over a fixed set of nodes. Each temporal edge is
an edge (u, v) with an associated *availability* or *departure* time τ and a *traversal* or *travel* time
λ. A temporal edge e = (u, v, τ, λ) can then be traversed starting from u at time τ and arriving
in v at time τ + λ. The notion of walk (or of path, if node repetitions are not allowed) can be
easily adapted to the case of temporal graphs by imposing the natural condition of traversing the
temporal edges in ascending time: that is, for any two consecutive temporal edges (u, v, τ₁, λ₁)
and (v, w, τ₂, λ₂) in the walk, τ₂ ≥ τ₁ + λ₁.<fnref n="1" /> However, introducing the temporal dimension arises
different notions of optimal walks or paths, the most common used being the *shortest one* (with
the fewest number of temporal edges), the *foremost one* (with the earliest arrival time), and the
fastest one (with the smallest total travel time). Once a notion of optimal walk or path is adopted,
the corresponding notion of betweenness can be analysed in terms of its computational complexity.
Indeed, this has been done in [11] in the case of paths, where the authors proved that computing
the shortest betweenness of all nodes can be done in time *O*(n³T²), where *n* is the number of nodes
and *T* is the number of distinct time steps in the temporal graph, while computing the foremost
and the fastest betweenness is #P-hard, that is, most likely computationally intractable. These
cases are also studied in [38], where, among other results, the authors proved that the restless
shortest betweenness (in the case of walks) can be computed in time *O*(n²MT²), where *M* is the
number of temporal edges (interestingly, the #P-hardness result does not hold when considering
walks rather than paths). A *restless* walk (or path) is a walk in which we do not “wait” at the same
node more than *β* time units, where *β* is a constant: that is, for any two consecutive temporal
edges (u, v, τ₁, λ₁) and (v, w, τ₂, λ₂) in the walk, τ₂ ≤ τ₁ + λ₁ + *β* in addition to τ₂ ≥ τ₁ + λ₁. Note
that, in the restless case, even deciding whether there exists a path between two specific nodes is
NP-complete [13]. Hence, in this case, we are forced to consider walks instead of paths. Our main
contributions are the following.

* We propose an algorithm for computing the betweenness in time $O(nM) = O(n^3T)$ in the case of shortest and shortest foremost paths (note that, in these cases, optimal non-restless walks are always paths). Our algorithm significantly outperforms the previously known algorithm (whose complexity was $O(n^3T^2)$) for computing the shortest and the shortest foremost betweenness [11].

* We propose an algorithm for computing the betweenness in time $O(nM)$ in the case of fastest, foremost, shortest, shortest fastest, and shortest foremost restless walks. The only previously known polynomial-time algorithm (with complexity $O(n^2MT^2)$) was in the case of shortest restless walks [38]: our algorithm significantly improves this algorithm. As far as we know, in all the other cases our algorithm is the first polynomial-time one and we conjecture it is optimal. Indeed, the algorithm is based on a new way of counting the number of optimal walks from a given source in time $O(M)$. This complexity is clearly optimal.

* We perform an extensive experimental evaluation of our non-restless algorithm, based on a diverse set of real-world networks that includes all publicly available networks from the

<footnote n="1">¹In this paper, we assume that the traversal time is always positive, which corresponds to the case called *strict* in the literature.</footnote>
works of [11, 39, 2]. In particular, we compare the execution time of our algorithm and of the
algorithm proposed in [11] for computing the shortest and the shortest foremost betweenness.
It turns out that our algorithm is between twice and almost 250 faster than the algorithm
of [11].

* By using our non-restless algorithm, we are able to compute in a reasonable amount of time the shortest betweenness of all nodes of three quite large temporal graphs analysed in [39], for which only approximate values were available so far by making use of the ONBRA approximation algorithm proposed in that paper and based on a sampling technique. From the results reported in [39], it also follows that our algorithm is almost always significantly faster than ONBRA.

* We apply our restless algorithm for computing the fastest, foremost, shortest, shortest foremost, and shortest fastest betweenness of all nodes of the temporal graphs considered in the first experiment. By referring to the (weighted) Kendall's $\tau$ correlation and to the intersection of the top-50 node sets, we compare the node rankings produced by the different betweenness measures and by different waiting constraints and we observe that there exists a general consistency between the different variants of betweenness centrality. We do also measure a sensible influence of waiting constraints, and note some cases of low correlation for certain pairs of criteria in some networks.

* As a case study, we apply our algorithm to the analysis of several public transport networks among the ones published in [26, 15]. In particular, we compare the execution time, the (weighted) Kendall's $\tau$, and the size of the intersection of the top-100 node sets for two different notions betweenness, that is, the shortest fastest and the shortest foremost betweenness. We observe a strong consistency between the two different variants of betweenness centrality, and a much lower consistency with the rankings produced by the betweenness of the static underlying graph, thus suggesting that this latter measure cannot be used as a 'proxy' of the shortest fastest and the shortest foremost betweenness.

Both our algorithm and the algorithm proposed in [11] follow a two phase approach (that is a path counting forward phase and a betweenness accumulation backward phase) and are both inspired by Brandes' algorithm [7]. A first difference between our algorithm and the algorithm of [11] is that the latter focuses on temporal vertices and explore their temporal neighbors, while our algorithm focuses on temporal edges and explore their temporal extensions. A second (and maybe, main) difference is that we leverage on two orderings of the temporal edges to overall consider each temporal edge (both in the forward phase and in the backward phase) a constant number of times, rather than considering a temporal neighbor for each of its predecessors. Third, our data structure allows to store predecessors in linear space with respect to the number of temporal edges. Finally, we note that the approach used in [39] is different as it is an approximation algorithm and it works through sampling. However, the way the paths are counted is similar to [11].

## 2 Related work

The literature on centrality measures being vast (as demonstrated by the clever periodic table of network centrality developed by David Schoch [43, 42]), we restrict our attention to approaches that are closest to ours, that is, to the realm of temporal graphs. Several introductions to temporal graphs also include surveys on temporal centrality measures (see, e.g., [24, 28, 41]). Clearly related to our work is the literature on the efficient computation of temporal paths and walks, such as the seminal paper of Bui-Xuan, Ferreira, and Jarry [10] and the more recent paper by Wu et al [49] (the reader may also refer to the quite exhaustive analysis of this literature appeared in [9]). Besides the references given in the introduction, our paper is mostly related to all work on the definition and computation of different temporal centrality measures, such as (in order of appearance) the temporal pagerank defined in [37], the temporal Katz centrality introduced in [4], the temporal
reachability used in [19], the *f*-PageRank centrality defined in [30], the temporal betweenness centrality defined in [47], the temporal closeness centrality treated in [16, 33], the temporal walk centrality introduced in [34], and the temporal betweenness centrality analysed in [44], just to mention the most recent ones. Finally, more "local" notions of centrality in temporal graphs have also been analysed such as the temporal version of ego betweenness introduced in Ghanem [23] and the pass-through degree defined in [2]: these centralities are clearly more efficient in terms of execution time, but not always satisfying in terms of the quality of their rankings.

# 3 Basic definitions and results

**Temporal graphs.** A temporal graph is a tuple $G = (V, E, \beta)$, where $V$ is the set of nodes, $E$ is the set of temporal edges, and $\beta \in \mathbb{N} \cup \{+\infty\}$ is the maximum waiting-time (we say that *waiting is unrestricted* when $\beta = +\infty$). A temporal edge $e$ is a quadruple $(u, v, \tau, \lambda)$, where $u \in V$ is the tail of $e$, $v \in V$ is the head of $e$, $\tau \in \mathbb{N}$ is the departure (or availability) time of $e$, and $\lambda \in \mathbb{N}^+$ is the travel (or traversal) time of $e$. We also define the arrival time of $e$ as $\tau + \lambda$, and we let $\text{dep}(e) = \tau$ and $\text{arr}(e) = \tau + \lambda$ denote the departure time and arrival time of $e$, respectively. We let $n = |V|$ and $M = |E|$ denote the number of nodes and temporal edges, respectively, and $T$ denote the number of distinct availability times. Finally, for any node $v$, $E_v^h$ will denote the set of temporal edges whose head is $v$.

**Temporal graph representation.** We use a doubly-sorted representation of a temporal graph $(V, E, \beta)$, which consists of two lists $E^{\text{arr}}$ and $E^{\text{dep}}$, each containing $|E|$ quadruples representing the temporal edges in $E$: $E^{\text{arr}}$ is a list sorted by non-decreasing arrival time and $E^{\text{dep}}$ is a list sorted by non-decreasing departure time. More precisely, we assume that $E^{\text{dep}}$ is specified through implicit pointers from $E^{\text{dep}}$ to $E^{\text{arr}}$, that link each (logical) quadruple in $E^{\text{dep}}$ to the (physical) quadruple in $E^{\text{arr}}$ representing the same temporal edge.

**Temporal walks.** Given a temporal graph $G = (V, E, \beta)$, a walk $W$ from (a source) $s$ to (a target) $t$, or a st-walk for short, is a sequence of temporal edges $e_i = (u_i, v_i, \tau_i, \lambda_i)$ for $i \in [k]$, such that $s = u_1, v_k = t$, and, for each $i \in [k-1]$, $^2 u_{i+1} = v_i$ and $\text{arr}(e_i) \le \tau_{i+1} \le \text{arr}(e_i) + \beta$ ($W$ is also called a *se$_k$-walk). A walk is said to be a path if, for any $i, j \in [k]$ with $i \neq j$, $u_i \neq u_j$ and $u_i \neq v_k$. Note that, since travel times are positive, walks are strict in the sense that $\tau_i < \tau_{i+1}$, for $i \in [k-1]$. The *departure time* $\text{dep}(W)$ of $W$ is defined as $\text{dep}(e_1)$, while the *arrival time* $\text{arr}(W)$ of $W$ is defined as $\text{arr}(e_k)$. The *duration* of $W$ is defined as $\text{arr}(W) - \text{dep}(W)$. We say that a temporal edge $e = (t, w, \tau, \lambda)$ * extends* $W$ if $\text{arr}(W) \le \tau \le \text{arr}(W) + \beta$. When $e$ extends $W$, we can indeed define the *sw-walk* $W.e = (e_1, \dots, e_k, e)$ from $s$ to $w$. Moreover, we also say that $e$ extends $e_k$ as it indeed extends any *se$_k$-walk*. Finally, we say that a temporal edge $e$ is *s-reachable* when there exists a *se-walk*.

Given a temporal graph $G = (V, E, \beta)$, a st-walk $W$ is a *shortest* (respectively, *foremost, latest, and fastest*) walk, if there is no st-walk that contains less temporal edges than $W$ (respectively, has an earlier arrival time, has a later departure time, and has a smaller duration). Moreover, a *shortest foremost* (respectively, *latest and fastest*) walk is a foremost (respectively, latest and fastest) temporal walk that is not longer than any other foremost (respectively, latest and fastest) temporal walk. In the following we will focus on shortest (Sh) and shortest foremost (SFo) walks, since these walks will allow us to introduce our algorithms in an easier way, without hiding the generality of our approach. In the appendix, we show how our algorithms can be adapted to the other types of walks by introducing the notions of cost and target cost structure (for the sake of brevity, all the proofs are included in Appendix 8).

**Two basic facts of Sh and SFo walks.** The following two results are easy to be proved, since they immediately follows from the definition of Sh and SFo walks.

**Fact 1.** Let $G = (V, E, \beta)$ be a temporal graph. For any node $s \in V$, if a walk $W$ with last temporal edge $f \in E$ is a Sh one among the sf-walks, and $e \in E$ is a temporal edge of $W$, then the prefix of $W$ up to the temporal edge $e$ is a Sh walk among the se-walks.

<footnote n="2">²In the following, for any non-negative integer $n$, $[n]$ will denote the set $\{1, 2, \dots, n\}$, with $[0] = \emptyset$.</footnote>
**Fact 2.** Given a temporal graph $G = (V, E, \beta)$, let $W$ be a SFo st-walk (for some $s, t \in V$) and let $e$ be the last temporal edge of $W$. Then, $W$ is a Sh walk among the se-walks.

**SFo betweenness.** Given a temporal graph $G = (V, E, \beta)$, two nodes $s, t \in V$ with $s \neq t$, and a temporal edge $e \in E$, we let $\sigma_{s,e,t}^*$ denote the number of SFo walks from $s$ to $t$ that contain $e$. We also denote by $\sigma_{s,t}^* = \sum_{e \in E_t^h} \sigma_{s,e,t}^*$ the number of SFo walks from $s$ to $t$.

We define the s-SFo betweenness of a temporal edge $e$ as $b_{s,e} = \sum_{v \in V: \chi_{s,t}=1} \sigma_{s,e,t}^* / \sigma_{s,t}^*$, where $\chi_{s,t} = 1$ if $s \neq t$ and there exists a st-walk (and, hence, $\sigma_{s,t}^* \neq 0$), and $\chi_{s,t} = 0$ otherwise.

Given three pairwise-distinct nodes $s, u$, and $t$ we denote by $\sigma_{s,u,t}^* = \sum_{e \in E_u^h} \sigma_{s,e,t}^*$ the number of SFo walks from $s$ to $t$ that contain $u$. Note that a walk where $u$ appears $\mu$ times is counted with multiplicity $\mu$.<fnref n="3" /> The SFo betweenness of a vertex $u$ is defined as $b_u = \sum_{s,t \in V \setminus \{u\}: \chi_{s,t}=1} \sigma_{s,u,t}^* / \sigma_{s,t}^*$. The SFo betweenness of any vertex $u$ can easily be computed from the s-SFo betweenness $b_{s,e}$ of all temporal edges $e$ entering $u$.

**Fact 3.** Given a temporal graph $G = (V, E, \beta)$ and a node $u \in V$, the following holds: $b_u = \sum_{s \in V \setminus \{u\}} (\sum_{e \in E_u^h} b_{s,e} - \chi_{s,u})$.

Given a temporal graph $G = (V, E, \beta)$ and a temporal edge $e \in E$, let $\sigma_{s,e}$ (respectively, $\sigma_{s,e}^*$) denote the number of Sh (respectively, SFo) se-walks, where a se-walk $W$ is SFo if there is no se-walk $X$ such that $(\text{arr}(X), |X|) \triangleleft (\text{arr}(W), |W|)$ (in the following, for any $a, b, c, d \in \mathbb{N}$, $(a, b) \triangleleft (c, d)$ if and only $(a < c) \lor (a = c \land b < d)$). Moreover, given two nodes $s, t \in V$ with $s \neq t$, let $W_{s,e,t}$ denote the set of SFo st-walk containing $e$ (hence, $|W_{s,e,t}| = \sigma_{s,e,t}^*$). Each walk $W \in W_{s,e,t}$ can be decomposed into a prefix $W_1$ (from $s$ to $v$) ending with $e$ and a suffix $W_2$ (from $v$ to $t$). Let $\theta_{s,e,t}$ denote the number of distinct suffixes of walks in $W_{s,e,t}$ (eventually including the empty suffix).

**Fact 4.** Given a temporal graph $G = (V, E, \beta)$, two nodes $s, t \in V$ with $s \neq t$, and a temporal edge $e = (u, v, \tau, \lambda)$, the following hold: $\sigma_{s,e,t}^* = \sigma_{s,e} \cdot \theta_{s,e,t}$.

**Successors, predecessors, and edge betweenness recursive formulation.** Given a temporal graph $G = (V, E, \beta)$, two nodes $s, t \in V$ with $s \neq t$, and a temporal edge $e \in E$, let $\text{succ}_{s,e,t}$ denote the set of temporal edges $f$ such that $e$ and $f$ are one after the other in a walk $W \in W_{s,e,t}$. Moreover, let $\text{succ}_{s,e} = \bigcup_{t \in V \setminus \{s\}} \text{succ}_{s,e,t}$. In the following, if $f \in \text{succ}_{s,e}$, we say that $f$ is successor of $e$ and that $e$ is a predecessor of $f$.

**Lemma 5.** Given a temporal graph $G = (V, E, \beta)$ and a temporal edge $e = (u, v, \tau, \lambda)$, the following hold:

$$b_{s,e} = \sigma_{s,e} \sum_{f \in \text{succ}_{s,e}} \frac{b_{s,f}}{\sigma_{s,f}} + \begin{cases} \frac{\sigma_{s,e}^*}{\sigma_{s,v}^*} & \text{if } \sigma_{s,e}^* > 0, \\ 0 & \text{otherwise.} \end{cases}$$

The above lemma will be used in the backward phase of our algorithms in order to compute the s-SFo betweenness of a temporal edge $e$ having already computed the s-SFo betweenness of all successors $f$ of $e$. In Appendix 3.1 we show an example of a temporal graph and of the centrality values of its nodes with respect to the different notions of optimal walks.

## 3.1 An example of temporal graph

Let us consider the temporal graph in the left part of Figure 1. The first list in the figure shows $E^{\text{arr}}$ (that is, the list of temporal edges sorted by non-decreasing arrival time), while the second list in the figure shows $E^{\text{dep}}$ (that is, the list of temporal edges sorted by non-decreasing departure time), which is specified by identifying the temporal edges by their position in the list $E^{\text{arr}}$ (the third and four lists are used by our algorithms and are explained in the main text). By assuming $\beta = 1$

<footnote n="3">³It is quite natural to take into account how many times a node appears in a walk when considering walks rather than paths in the betweenness definition.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 1: An example of a temporal graph, where $n = 8$, $M = 13$, $T = 11$. The lower part of the label of each temporal edge indicates its availability time $\tau$ and its traversal time $\lambda$ (hence, the arrival time of the temporal edge is $\tau+\lambda$). The (overlined) upper part of the label of each temporal edge indicates its position in the $E^{\text{arr}}$ list. The $E^{\text{dep}}$, $E_{\text{node}}^{\text{dep}}$, $E_{\text{dep}}^{\text{arr}}$ lists also refer to the (overlined) indexes of $E^{\text{arr}}$. The underlined indices, instead, indicate the position of the corresponding edge in $E^{\text{arr}}$ into the list $E_{\text{node}}^{\text{dep}}$ of its tail.</figcaption></figure>

and by identifying the temporal edges by their (overlined) position in the list $E^{\text{arr}}$, we have that $\langle \bar{1}, \bar{2}, \bar{4}, \bar{6}, \bar{9} \rangle$ is a $v_1v_5$-walk which can be extended by either the temporal edge $\overline{11}$ or the temporal edge $\overline{13}$. On the contrary, $\langle \bar{1}, \bar{5} \rangle$ is not a $v_1v_5$-walk since $\tau_2 = 4 > 3 = \text{arr}(e_1)+\beta$. We also have that $\langle \bar{7} \rangle$ is the only shortest $v_1v_5$-walk (with 1 temporal edge) and the only (shortest) foremost $v_1v_5$-walk (with arrival time equal to 7), and $\langle \bar{3}, \bar{9} \rangle$ is the only (shortest) latest $v_1v_5$-walk (with departure time equal to 4 and 2 temporal edges). Finally, both $\langle \bar{7} \rangle$ and $\langle \bar{3}, \bar{9} \rangle$ are fastest $v_1v_5$-walks (with duration equal to 5), and only $\langle \bar{7} \rangle$ is also a shortest fastest $v_1v_5$-walk. By considering foremost walks, we have that $\sigma_{v_1, \bar{9}, v_6}^* = 2$, since the temporal edge $(v_2, v_5, 6, 3)$ (whose index in $E^{\text{arr}}$ is $\bar{9}$) is contained in the two foremost $v_1v_6$-walks $\langle \bar{3}, \bar{9}, \overline{11} \rangle$ and $\langle \bar{1}, \bar{2}, \bar{4}, \bar{6}, \bar{9}, \overline{11} \rangle$. By setting $\beta = 0$ and by considering latest walks, instead, we have that $\sigma_{v_1, v_2}^* = \sigma_{v_1, \bar{1}, v_2}^* + \sigma_{v_1, \bar{3}, v_2}^* + \sigma_{v_1, \bar{6}, v_2}^* = 1+0+1=2$: as we can see, the latest $v_1v_2$-walk $\langle \bar{1}, \bar{2}, \bar{4}, \bar{6} \rangle$ is counted with multiplicity 2 since it passes twice through $v_2$, once via the temporal edge $(v_1, v_2, 1, 1)$ (whose index in $E^{\text{arr}}$ is $\bar{1}$) and once via the temporal edge $(v_4, v_2, 5, 1)$ (whose index in $E^{\text{arr}}$ is $\bar{6}$).

<table><caption>Table 1: The set of shortest st-walks in the graph of Figure 1, for any pair of nodes $s$ and $t$</caption><thead><tr><th></th><th>$v_1$</th><th>$v_2$</th><th>$v_3$</th><th>$v_4$</th><th>$v_5$</th><th>$v_6$</th><th>$v_7$</th><th>$v_8$</th></tr></thead><tbody><tr><th>$v_1$</th><td>$\langle\langle 1\rangle, \langle 3\rangle\rangle$</td><td>$\langle\langle 1, 2\rangle\rangle$</td><td>$\langle\langle 1, 2, 4\rangle\rangle$</td><td>$\langle\langle 1, 2, 4\rangle\rangle$</td><td>$\langle\langle 7\rangle\rangle$</td><td>$\langle\langle 3, 9, 11\rangle\rangle$</td><td>$\langle\langle 7, 8\rangle\rangle$</td><td>$\langle\langle 7, 8, 12\rangle, \langle 3, 9, 13\rangle\rangle$</td></tr><tr><th>$v_2$</th><td>$\emptyset$</td><td>$\langle\langle 2\rangle\rangle$</td><td>$\langle\langle 2, 4\rangle\rangle$</td><td>$\langle\langle 2, 4\rangle\rangle$</td><td>$\langle\langle 5\rangle, \langle 9\rangle$</td><td>$\langle\langle 5, 10\rangle, \langle 9, 11\rangle\rangle$</td><td>$\langle\langle 5, 8\rangle\rangle$</td><td>$\langle\langle 9, 13\rangle\rangle$</td></tr><tr><th>$v_3$</th><td>$\emptyset$</td><td>$\langle\langle \bar{4}, \bar{6}\rangle\rangle$</td><td>$\langle\langle \bar{4}\rangle\rangle$</td><td>$\langle\langle \bar{4}, \bar{6}, \bar{9}\rangle\rangle$</td><td>$\langle\langle \bar{4}, \bar{6}, \bar{9}, \overline{11}\rangle\rangle$</td><td>$\langle\langle \bar{4}, \bar{6}, \bar{9}, \overline{11}\rangle\rangle$</td><td>$\emptyset$</td><td>$\langle\langle \bar{4}, \bar{6}, \bar{9}, \overline{13}\rangle\rangle$</td></tr><tr><th>$v_4$</th><td>$\emptyset$</td><td>$\langle\langle \bar{6}\rangle\rangle$</td><td>$\emptyset$</td><td>$\langle\langle \bar{6}, \bar{9}\rangle\rangle$</td><td>$\langle\langle \bar{6}, \bar{9}, \overline{11}\rangle\rangle$</td><td>$\langle\langle \bar{6}, \bar{9}, \overline{11}\rangle\rangle$</td><td>$\emptyset$</td><td>$\langle\langle \bar{6}, \bar{9}, \overline{13}\rangle\rangle$</td></tr><tr><th>$v_5$</th><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\langle\langle \overline{10}\rangle, \langle\langle \overline{11}\rangle\rangle$</td><td>$\langle\langle \bar{8}\rangle\rangle$</td><td>$\langle\langle \bar{13}\rangle\rangle$</td><td>$\emptyset$</td></tr><tr><th>$v_6$</th><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\langle\langle \overline{12}\rangle\rangle$</td></tr><tr><th>$v_7$</th><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\langle\langle \overline{12}\rangle\rangle$</td></tr><tr><th>$v_8$</th><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\emptyset$</td><td>$\langle\langle \overline{12}\rangle\rangle$</td></tr></tbody></table>

The shortest walk from $v_1$ to $v_6$ varies in length depending on the value of $\beta$: with $\beta = 0$ it is 6 (which is the length of $\langle \bar{1}, \bar{2}, \bar{4}, \bar{6}, \bar{9}, \overline{11} \rangle$), with $\beta = 1$ it is 3 (which is the length of $\langle \bar{3}, \bar{9}, \overline{11} \rangle$), and with $\beta \ge 2$ it is 2 (which is the length of $\langle \bar{7}, \overline{11} \rangle$). By setting $\beta = 2$ and by considering shortest walks, let us compute the $v_1$-temporal betweenness of the temporal edge $(v_4, v_2, 5, 1)$ (whose index in $E^{\text{arr}}$ is $\bar{6}$). Since $\sigma_{v_1, \bar{6}, v}^* = 0$ for any $v \ne v_1$, we have that $b_{v_1, \bar{6}} = 0$. However, if we set $\beta = 0$, then we have that $\sigma_{v_1, \bar{6}, v_6}^* = 1$ (since the temporal edge is contained in the unique shortest
$v_1v_6$-walk $\langle \overline{1}, \overline{2}, \overline{4}, \overline{6}, \overline{9}, \overline{11} \rangle$), while $\sigma_{v_1, \bar{6}, v}^* = 0$ for any $v \notin \{v_1, v_6\}$: hence, in this case, $b_{v_1, \bar{6}} = 1$. If $\beta = 1$, we have that the temporal betweenness vectors are pairwise distinct depending on the chosen measure, as shown in Table 2.

<table><caption>Table 2: The temporal betweenness vectors with different types of optimal walks for the temporal graph of Figure 1.</caption><thead><tr><th></th><th>v<sub>1</sub></th><th>v<sub>2</sub></th><th>v<sub>3</sub></th><th>v<sub>4</sub></th><th>v<sub>5</sub></th><th>v<sub>6</sub></th><th>v<sub>7</sub></th><th>v<sub>8</sub></th></tr></thead><tbody><tr><td>Shortest</td><td>0.0</td><td>9.5</td><td>2.0</td><td>4.0</td><td>10.0</td><td>0.0</td><td>0.5</td><td>0.0</td></tr><tr><td>Foremost</td><td>0.0</td><td>9.5</td><td>2.5</td><td>4.5</td><td>10.0</td><td>0.0</td><td>3.0</td><td>0.0</td></tr><tr><td>Latest</td><td>0.0</td><td>13.5</td><td>6.0</td><td>8.0</td><td>10.0</td><td>0.0</td><td>0.0</td><td>0.0</td></tr><tr><td>Fastest</td><td>0.0</td><td>10.5</td><td>2.0</td><td>4.0</td><td>10.0</td><td>0.0</td><td>0.0</td><td>0.0</td></tr><tr><td>Shortest foremost</td><td>0.0</td><td>9.0</td><td>2.0</td><td>4.0</td><td>10.0</td><td>0.0</td><td>3.0</td><td>0.0</td></tr><tr><td>Shortest latest</td><td>0.0</td><td>12.0</td><td>3.0</td><td>5.0</td><td>10.0</td><td>0.0</td><td>0.0</td><td>0.0</td></tr><tr><td>Shortest fastest</td><td>0.0</td><td>10.0</td><td>2.0</td><td>4.0</td><td>10.0</td><td>0.0</td><td>0.0</td><td>0.0</td></tr></tbody></table>

Let us, for example, compute the temporal betweenness of node $v_2$ in the case of shortest walks. Table 1 shows, for any pair of nodes $s$ and $t$, the set of shortest st-walks. Node $v_2$ is contained as an inner node in the following walks: the $v_1v_3$-walk $\langle \overline{1}, \overline{2} \rangle$, the $v_1v_4$-walk $\langle \overline{1}, \overline{2}, \overline{4} \rangle$, the $v_1v_6$-walk $\langle \overline{3}, \overline{9}, \overline{11} \rangle$, the $v_1v_8$-walk $\langle \overline{3}, \overline{9}, \overline{13} \rangle$, the $v_3v_5$-walk $\langle \overline{4}, \overline{6}, \overline{9} \rangle$, the $v_3v_6$-walk $\langle \overline{4}, \overline{6}, \overline{9}, \overline{11} \rangle$, the $v_3v_8$-walk $\langle \overline{4}, \overline{6}, \overline{9}, \overline{13} \rangle$, the $v_4v_5$-walk $\langle \overline{6}, \overline{9} \rangle$, the $v_4v_6$-walk $\langle \overline{6}, \overline{9}, \overline{11} \rangle$, and the $v_4v_8$-walk $\langle \overline{6}, \overline{9}, \overline{13} \rangle$. All these 10 walks are the only shortest paths from their corresponding sources to their corresponding destinations, apart from the $v_1v_8$-walk $\langle \overline{3}, \overline{9}, \overline{13} \rangle$ (there is also the $v_1v_8$-walk $\langle \overline{7}, \overline{8}, \overline{12} \rangle$). Hence, each of them contribute 1 to the temporal betweenness of $v_2$ apart from the $v_1v_8$-walk which contributes 0.5. In conclusion, the temporal betweenness of $v_2$ is 9.5 (as shown in the Table 2).

# 4 Computing the SFo betweenness

In this section we describe an algorithm to compute the s-SFo betweenness $b_{s,e}$ of all temporal edges $e$, for a given source node $s$, which runs in time linear in $M$, that is, the number of temporal edges. By repeating the computation for each source and by using Fact 3, it is then possible to aggregate these s-SFo betweennesses to obtain the SFo betweenness of all nodes in time $O(nM)$. The algorithm consists of three phases, a forward, an intermediate, and a backward one. The goal of the forward phase is to count, for each temporal edge $e$, the number of Sh se-walks and, at the same time, to identify the set of its successors, that is, the set of edges $f$ that can follow $e$ in a Sh st-walk, for some target node $t$. During the intermediate phase we compute, for each node $v$, the number of SFo sv-walks and their cost (that is, the pair including the arrival time and the number of edges in the walk). Finally, the goal of the backward phase is to report the s-SFo betweenness of the edges following the successor dependencies.

In the following, given a temporal graph $G = (V, E, \beta)$, we assume that $G$ is represented through its $E^{\text{arr}}$ and $E^{\text{dep}}$ lists (recall that the temporal edges in $E^{\text{dep}}$ are identified by their position in the list $E^{\text{arr}}$). We also assume that, by using these two lists, the following two other lists have been pre-computed, where, once again, each temporal edge is identified by its position in $E^{\text{arr}}$ (see also the examples in Appendices 3.1 and 11): $E_{\text{node}}^{\text{dep}}$, which, for every $v \in V$, contains the list $E_{\text{node}}^{\text{dep}}[v]$ of temporal edges whose tail is $v$, sorted in non-decreasing order with respect to their departure time, and $E_{\text{node}}^{\text{arr}}$, which, for every $e = (u, v, \tau, \lambda) \in E$, contains the position of $e$ in $E_{\text{node}}^{\text{dep}}[u]$ (more precisely, if $e$ is the $i$-th temporal edge in $E^{\text{arr}}$ and the $j$-th temporal edge in $E_{\text{node}}^{\text{dep}}[u]$, then $E_{\text{node}}^{\text{arr}}[i] = j$). Note that both $E_{\text{node}}^{\text{dep}}$ and $E_{\text{node}}^{\text{arr}}$ can easily be computed in linear-time starting from $E^{\text{arr}}$ and $E^{\text{dep}}$.
## 4.1 The non-restless case

We first introduce the algorithm for computing the SFo betweenness in the case $\beta = \infty$, that is, *without waiting constraints* or *non-restless* (see Algorithm 1), whose forward phase is built upon the algorithm of [9] for computing single-source minimum-cost walks.

<caption>**Algorithm 1:** Compute non-restless SFo $b_{s,e}$, for all $e \in E$</caption>

input : $G = (V, E, \infty)$ (represented by $E^{\text{dep}}$ and $E^{\text{arr}}$) and $s \in V$
output : s-SFo betweenness $b_{s,e}$, for all $e \in E$
1 Compute the lists $E_{\text{node}}^{\text{dep}}$ and $E_{\text{dep}}^{\text{arr}}$;
2 **foreach** $v \in V$ **do** $l[v] := 1$; $c[v] := \infty$; $\sigma[v] := 0$;
3 **foreach** $e \in E$ **do** $L[e] := 0$; $C[e] := \infty$; $\Sigma[e] := 0$;
4 **foreach** $e = (u, v, \tau, \lambda) \in E^{\text{arr}}$ **do**
5 **if** $E_{\text{dep}}^{\text{arr}}[e] \ge l[u]$ **then** **Finalize**($u, E_{\text{dep}}^{\text{arr}}[e]$);
6 **if** $u = s$ **then** $C[e] := 1$; $\Sigma[e] := 1$;
7 **if** $C[e] \ne \infty$ **then**
8 **if** $C[e] \le c[v]$ **then**
9 $a = l[v]$; $D := E_{\text{node}}^{\text{dep}}[v]$;
10 **while** $a \le |D| \land \text{dep}(E^{\text{arr}}[D[a])) < \tau + \lambda$ **do** $a := a + 1$;
11 **Finalize**($v, a - 1$);
12 **if** $C[e] < c[v]$ **then** $c[v] := C[e]$; $\sigma[v] := 0$;
13 $\sigma[v] := \sigma[v] + \Sigma[e]$; $L[e] := a$;
14 **foreach** $v \in V$ **do** $c^*[v] := [\infty, \infty]$; $\sigma^*[v] := 0$; $\delta[v] := 0$;
15 **foreach** $e \in E$ **do** $\Sigma^*[e] := 0$; $b[e] := 0$;
16 **foreach** $e = (u, v, \tau, \lambda) \in E^{\text{arr}}$ **do**
17 **if** $C[e] < \infty \land [\text{arr}(e), C[e]] \subset c^*[v]$ **then**
18 $c^*[v] := [\text{arr}(e), C[e]]$;
19 **foreach** $e = (u, v, \tau, \lambda) \in E^{\text{arr}}$ **do**
20 **if** $[\text{arr}(e), C[e]] = c^*[v]$ **then**
21 $\Sigma^*[e] := \Sigma[e]$; $\sigma^*[v] := \sigma^*[v] + \Sigma[e]$;
22 **foreach** $e = (u, v, \tau, \lambda) \in \text{reverse}(E^{\text{arr}})$ : $L[e] > 0$ **do**
23 **if** $c^*[v] \subset [\text{arr}(e), C[e]]$ **then**
24 $\delta[v] := 0$; $c^*[v] := [\text{arr}(e), C[e]]$;
25 **for** $f \in E_{\text{node}}^{\text{dep}}[v][L[e] : l[v] - 1]$ **do** $\delta[v] := \delta[v] + b[f]/\Sigma[f]$;
26 $l[v] := L[e]$; $b[e] := \Sigma[e]\delta[v]$;
27 **if** $\Sigma^*[e] > 0$ **then** $b[e] := b[e] + \Sigma^*[e]/\sigma^*[v]$;
28 **return** $b$
29 **Finalize**($u, j$):
30 **if** $c[u] \ne \infty$ **then**
31 **foreach** $f \in E_{\text{node}}^{\text{dep}}[l[u], j]$ **do** $C[f] := c[u] + 1$; $\Sigma[f] := \sigma[u]$;
32 $l[u] := j + 1$;

**Forward phase (lines 4-13).** Let $G_k = (V, E_k, \infty)$ be the temporal graph containing only the first $k$ temporal edges in $E^{\text{arr}}$. The algorithm scans the edges in $E^{\text{arr}}$ one after the other and after scanning $k$ edges, for each node $v \in V$, it updates the following three values: the length $c[v]$ of any Sh sv-walk in $G_k$, the number $\sigma[v]$ of these walks in $G_k$, and the position $l[v]$ in $E_{\text{node}}^{\text{dep}}[v]$ such that all temporal edges in $E_{\text{node}}^{\text{dep}}[v]$ starting from this position can extend a Sh sv-walk in $G_k$. Note that $c[v]$ can only decrease as $k$ increases, while $l[v]$ can only increase.

At the beginning, for each node $v$, $c[v] = \infty$, $\sigma[v] = 0$, and $l[v] = 1$. Suppose that the first $k-1$ temporal edges have been scanned, and that the edge $e_k = (u, v, \tau, \lambda)$ has now to be analysed (the reader can also refer to the figure shown in Appendix 9). Let us first analyse $e_k$ from the point of view of its tail, that is, $u$. Clearly, $e_k$ is included in $E_{\text{node}}^{\text{dep}}[u]$; suppose that it appears in position $i$. If $i \ge l[u]$, then all temporal edges between position $l[u]$ and $i$, which have a departure time not greater than $\text{dep}(e_k)$, cannot extend any su-walk ending with a temporal edge following $e_k$ in $E^{\text{arr}}$, since such a temporal edge has arrival time greater than $\text{dep}(e_k)$. Each such edge $f$ can then
be “finalised” (lines 30-32), that is, the length $C[f]$ of any Sh sf-walk (in $G_k$) can be set equal to $c[u] + 1$ and the number $\Sigma[f]$ of these walks (in $G_k$) can be set equal to $\sigma[u]$. We use the term “finalise” to emphasise that $C[f]$ will be the same in $G_{k'}$ for $k' \ge k$. We can also set $l[u] = i + 1$, since all temporal edges in $E_{\text{node}}^{\text{dep}}[u]$ starting from position $i + 1$ can still extend a Sh su-walk in $G_{k'}$ for $k' \ge k$. Moreover, if $u = s$, then we can set $C[e_k]$ equal to 1 (since we are considering Sh walks from $s$) and the number of Sh walks ending with $e_k$ is equal to 1 (since there is only one such walk, that is, $\langle e_k \rangle$).

Let us now analyse the temporal edge $e_k$ from the point of view of its head, that is, $v$, by assuming that there exists at least one Sh walk ending with $e_k$ in $G_k$. If $C[e_k]$ is not greater than $c[v]$ (that is, $e_k$ ends a Sh sv-walk), we first compute the first position $a$ in $E_{\text{node}}^{\text{dep}}[v]$ of a temporal edge whose departure time is at least equal to $\tau + \lambda$ (that is, a temporal edge which can extend an se-walk in $G_k$). All the temporal edges in $E_{\text{node}}^{\text{dep}}[v]$ between the position $l[v]$ and the position $a-1$ can now be finalised, since they cannot be the successor of any temporal edge of $E^{\text{arr}}$ following $e_k$. We then set $l[v] = a$, since all temporal edges in $E_{\text{node}}^{\text{dep}}[v]$ starting from position $a$ can still extend a Sh sv-walk in $G_{k'}$ for $k' \ge k$ (in particular, they extend Sh se-walks). Moreover, if adding the temporal edge $e_k$ to $G_{k-1}$ reduces the length $c[v]$ of the Sh sv-walks (that is, $C[e_k] < c[v]$), then we have to update $c[v]$, by setting it equal to $C[e_k]$ (that is, the length of the Sh se$_k$-walks), and $\sigma[v]$ by setting it equal to the number $\Sigma[e_k]$ of Sh se$_k$-walk in $G_k$. Otherwise (that is, $C[e_k] = c[v]$ and adding the temporal edge $e_k$ to $G_{k-1}$ does not change the length $c[v]$ of the Sh sv-walks), the number $\Sigma[e_k]$ of Sh se$_k$-walk in $G_k$ has to be added to $\sigma[v]$ (since all Sh se$_k$-walks are also Sh sv-walks). Finally, we store in $L[e_k]$ the position $a$ in $E_{\text{node}}^{\text{dep}}[v]$, which is the first position of the successors of $e$ (to be used in the backward phase).

**Intermediate phase (lines 16-21).** Once we have computed, for each $e \in E$, the length $C[e]$ of any Sh se-walk and the number $\Sigma[e]$ of these walks, it is easy to compute, for each $v \in V$, $c^*[v]$, where $c^*[v]$ specifies both the arrival time $c^*[v][1]$ and the length $c^*[v][2]$ of any SFo sv-walk. Indeed, it suffices to scan the temporal edges in $E^{\text{arr}}$ and, for each edge $e = (u, v, \tau, \lambda)$, to verify whether $(\text{arr}(e), C[e]) \triangleleft c^*[v]$ in which case $c^*[v]$ has to be set equal to $(\text{arr}(e), C[e])$ (lines 16-18). Once $c^*[v]$ has been computed for each $v \in V$, the number $\sigma^*[v]$ of SFo sv-walks can also be computed. Indeed, it suffices to scan again the temporal edges in $E^{\text{arr}}$ and, for each edge $e = (u, v, \tau, \lambda)$, to verify whether $(\text{arr}(e), C[e]) = c^*[v]$ in which case $\sigma^*[v]$ has to be increased by the value $\Sigma[e]$ (lines 19-21). Note that, at the same time, we can also compute the number $\Sigma^*[e]$ of SFo se-walks.

**Backward phase (lines 22-27).** The backward phase simply applies Lemma 5 in a “reverse” way, by scanning the temporal edges in $E^{\text{arr}}$ from the last to the first one and, for each scanned edge $e$, by accumulating on its head $v$ the contribution to $b_{s,e}$ of each successor of $e$. More precisely, we store in $\delta[v]$ the partial sum $\sum_{f \in E_{\text{node}}^{\text{dep}}[v][l[v]:z]} \frac{b[f]}{\Sigma[f]}$ where $z$ denotes the last index when the sum was zeroed. It can be updated in constant time per edge $f \in E_{\text{node}}^{\text{dep}}[v]$ each time we encounter an edge $e$ with head $v$. Note that each such edge $e$ has successors $E_{\text{node}}^{\text{dep}}[v][L[e] : r]$, where $r$ is the position of the last edge $f$ in $E_{\text{node}}^{\text{dep}}$ such that $C[f] = C[e] + 1$ and the index $L[e]$ of the first successor can only decrease as we scan edges $e$ with lower arrival times.<fnref n="4" /> As we scan the $k$th edge $e$ in $E^{\text{arr}}$, we also maintain in $c^*[v]$ the arrival time and the length of any SFo sv-walk in $G_k$. Whenever $c^*[v] \triangleleft (\text{arr}(e), C[e])$, the index $r$ for $e$ is indeed $l[v] - 1$ and the quantity accumulated on $v$ has to be zeroed while $c^*[v]$ has to be updated to $(\text{arr}(e), C[e])$.

**Theorem 6.** For any temporal graph $G = (V, E, \infty)$ and for any $s \in V$, Algorithm 1 correctly computes the s-SFo betweenness $b_{s,e}$ in time $O(M)$.

In Appendix 10 we prove the above theorem, while in Appendix 11 we describe an example of execution of Algorithm 1 on a simple temporal graph, and in Appendix 12 we show how this algorithm can be easily simplified in order to compute the non-restless Sh betweenness.

<footnote n="4">⁴As it is common in several programming languages, given a sequence *A* and two positive integers *l* and *r* both not greater than the length of *A* and such that *l* ≤ *r*, we denote by *A*[*l* : *r*] the sub-sequence of *A* from position *l* to position *r*, both included. Moreover, *A*[*l* :] = *A*[*l* : |*A*|].</footnote>
## 4.2 The restless case

We now briefly describe how Algorithm 1 has to be modified in order to deal with the general case (that is, $\beta \le \infty$): the new algorithm manages the increased complexity of the restless constraint through appropriate lists of interval quintuples which correspond to windows of time with temporal edges from a node that extend the same optimal walks. Once again, we execute a forward phase (in order to compute, for each temporal edge $e$, the length $C[e]$ of any Sh se-walk and the number $\Sigma[e]$ of these walks), followed by the same intermediate phase and a backward phase in which Lemma 5 is applied. Note that in Algorithm 1, during the forward phase, in order to correctly apply the lemma in the backward phase, it sufficed to memorize, for each temporal edge $e$, the position $L[e]$ in the list $E_{\text{node}}^{\text{dep}}[v]$ of the first temporal edge which could extend a Sh se-walk. This was due to the fact that, in the non-restless case, if an en edge $f$ in $E_{\text{node}}^{\text{dep}}[v]$ extends a se-walk, then all edges following $f$ in $E_{\text{node}}^{\text{dep}}[v]$ also extend the walk. In the general case, this is not true anymore (because of the waiting constraints) and the forward phase of the algorithm has to maintain additional information to be used during the backward phase. In particular, given a temporal graph $G = (V, E, \beta)$, for each node $v \in V$, the general algorithm maintains a list $\mathcal{I}_v$ of interval quintuples $Q = (l, r, c, P, \eta)$ where $1 \le l, r \le |E_{\text{node}}^{\text{dep}}[v]|$, $c \in \mathbb{N}$, $\eta \in \mathbb{N}$, and $P \subseteq E$ is a list of predecessor edges. The semantic of an interval quintuple $Q$ is the following.

* $l$ and $r$ are the left and right extremes of an interval $Q.I$ of edges in $E_{\text{node}}^{\text{dep}}[v]$ (that is, $Q.I = E_{\text{node}}^{\text{dep}}[v][l:r]$).

* $c$ is the length of any Sh walk from the source $s$ (in the temporal graph induced by the edges scanned so far), such that edges in $Q.I$ extend it.

* The edges ending these walks are predecessors of edges in $Q.I$ and are stored in the ordered list $P$ (sorted by arrival times). More precisely, for any edge $f = Q.I[i]$, with $1 \le i \le r-l+1$, the set of edges $P_i$, that precede $f$ in the above mentioned Sh walks, is a subset of $P$. We rely on the fact that edges with the same predecessors partition $Q.I$ into consecutive intervals. Indeed, $P_{i+1}$ is included in $P_i$ if $i \le r-l$. The ordering of $P$ respect the inclusion ordering $P_1 \supseteq P_2 \supseteq \dots$ so that each $P_i$ is a suffix of $P$.

* $\eta$ is the total number of Sh walks that end with an edge in $P$ (they all have length $c$).

The forward and backward phase of the general algorithm as well as the finalisation of an edge are more complicated than in the case of the non-restless case, in order to deal with the list of interval quintuples. A detailed description of these modifications along with the pseudo-code of the algorithm and the correctness and complexity analysis are presented in Appendix 13.

# 5 Computing other betweennesses

In Appendix 14 we introduce a general cost framework and we show how it can encompass the following optimality criteria: fastest (Fa), foremost (Fo), Sh, and shortest fastest (SFa). Other criteria (such as latest) can also be dealt with by the framework (we leave to the reader the freedom of choosing other such criteria). In the same appendix we then prove that the algorithm for the restless SFo case can be extended to any criteria that fits in the framework.

# 6 The experiments

In this section we perform several experimental analysis in order to compare the performance of our algorithms with respect to the ones previously proposed in the literature, and in order to apply the algorithms themselves to a specific case study in the field of public transport networks. Our experimental study includes the following three algorithms.
* BMNR: this is the algorithm proposed in [11] to compute the exact values of the Sh and SFo betweenness of all nodes.

* ONBRA: this is the approximation algorithm proposed in [39], which is based on a sampling technique for obtaining an absolute approximation of the Sh betweenness values (both in the non restless and in the restless case).

* FAST: this is the algorithm described in the previous sections, that we use here to compute the exact values of the Sh (Algorithm 2) and SFo (Algorithm 1) betweenness of all nodes.

In order to analyse the correlation between different centrality rankings, we used three different metrics: the Kendall's τ correlation coefficient [25], a weighted version of this coefficient [48], and the intersection of the top-1000 ranked nodes (note that the latter metric is directly translatable into the Jaccard similarity of the top ranked nodes). For the weighted Kendall's τ coefficient, we used the hyperbolic weighting scheme, that gives weights to the positions in the ranking which decay harmonically with the ranks, i.e., the weight of rank r is $1/(r + 1)$. Both the Kendall's τ correlation coefficient and its weighted version has been computed by using the Java code available at the Laboratory for Web Algorithmics [5].

## 6.1 Comparing algorithms execution times

First, we compare the running time of BMNR, of ONBRA, and of FAST. We present here the results concerning only the computation of the Sh betweenness: however, the results are similar in the case of the SFo betweenness (see the table in Section 15 in the appendix). We used the Julia implementation of BMNR associated to [2] and available at [3].<fnref n="5" /> We also implemented FAST in Julia: our code is available at https://github.com/piluc/TWBC/. A Rust implementation is also available at https://github.com/lviennot/tempograph/. Finally, we made use of the results reported in [39] which, in turn, made use of the C implementation of ONBRA available at [40]. We executed the experiments on a server running Ubuntu 20.04.5 LTS 112 with processors Intel(R) Xeon(R) Gold 6238R CPU @ 2.20GHz and 112GB RAM.

**Dataset.** In this first experiment, we execute the algorithms on the set of temporal graphs used in [2], which includes almost all the networks of [11] and of [39]. As stated in [2], this set does not include one temporal graph used in [11], because it does not appear to be available anymore, and it replaces one temporal graph used in [39] by a bigger one from a different domain to make the set of analyzed temporal graphs more diverse. This latter network excluded in [2] and the two larger temporal graphs analyzed in [39], which were excluded in [2] because of the excessive amount of time needed to compute their exact temporal betweenness values, will be analysed in our second experiment. The properties of these networks are summarized in the first five columns of Table 3.

**Results.** The execution times of BMNR and of FAST are shown in the 6th and 7th columns of Table 3. As it can be seen, FAST is between approximately two and almost 250 times faster than BMNR (see the eighth column). It is worth observing that the execution time of our Julia implementation of FAST is significantly lower than the execution time (reported in [39]) of the C implementation of ONBRA, which was executed on an architecture not very different from ours. Indeed, on the four temporal graphs of our dataset that have also been used in the experimental analysis of [39] (that is, College msg, Email EU, Facebook wall, and SMS), the execution time of ONBRA is approximately 6, 25, 2, and 3 times slower than our algorithm (note that ONBRA computed the estimates of the Sh betweenness values, by using a sample of node pairs whose size was less than 1% of the number of all node pairs).

<footnote n="5">⁵As stated in [2], the original C implementations of BMNR caused overflow (indicated by negative centralities) and out of memory errors.</footnote>
<table><caption>Table 3: The temporal graphs used in our first experiment, where *n* denotes the number of nodes, *M* the number of temporal edges, *T* the number of unique time steps, *t<sub>BMNR</sub>* the execution time of BMNR, and *t<sub>FAST</sub>* the execution time of FAST.</caption><thead><tr><th>Network</th><th>n</th><th>M</th><th>T</th><th>URL</th><th>t<sub>BMNR</sub></th><th>t<sub>FAST</sub></th><th>t<sub>BMNR</sub>/t<sub>FAST</sub></th></tr></thead><tbody><tr><td>Infectious</td><td>10972</td><td>831824</td><td>76944</td><td>[14]</td><td>3111.19</td><td>1603.53</td><td>1.94</td></tr><tr><td>DiggReply</td><td>30360</td><td>86203</td><td>82641</td><td>[36]</td><td>1190.41</td><td>506.53</td><td>2.35</td></tr><tr><td>FacebookWall</td><td>35817</td><td>198028</td><td>194904</td><td>[36]</td><td>3410.98</td><td>1317.76</td><td>2.59</td></tr><tr><td>SMS</td><td>44090</td><td>544607</td><td>467838</td><td>[36]</td><td>12476.04</td><td>4721.05</td><td>2.64</td></tr><tr><td>SlashdotReply</td><td>51083</td><td>139789</td><td>89862</td><td>[36]</td><td>4489.14</td><td>1643.77</td><td>2.73</td></tr><tr><td>WikiElections</td><td>7115</td><td>106985</td><td>101012</td><td>[29]</td><td>521.11</td><td>113.68</td><td>4.58</td></tr><tr><td>CollegeMsg</td><td>1899</td><td>59798</td><td>58911</td><td>[29]</td><td>242.81</td><td>23.20</td><td>10.47</td></tr><tr><td>Topology</td><td>16564</td><td>198038</td><td>32823</td><td>[27]</td><td>8704.15</td><td>792.82</td><td>10.98</td></tr><tr><td>Hypertext09</td><td>113</td><td>41636</td><td>5246</td><td>[14]</td><td>83.63</td><td>0.80</td><td>104.37</td></tr><tr><td>HighSchool11</td><td>126</td><td>57078</td><td>5609</td><td>[14]</td><td>132.33</td><td>1.18</td><td>111.86</td></tr><tr><td>HighSchool12</td><td>180</td><td>90094</td><td>11273</td><td>[14]</td><td>394.70</td><td>2.93</td><td>134.89</td></tr><tr><td>PrimarySchool</td><td>242</td><td>251546</td><td>3100</td><td>[14]</td><td>1895.45</td><td>12.92</td><td>146.67</td></tr><tr><td>EmailEU</td><td>986</td><td>327336</td><td>207880</td><td>[29]</td><td>11942.84</td><td>72.24</td><td>165.32</td></tr><tr><td>HighSchool13</td><td>327</td><td>377016</td><td>7375</td><td>[14]</td><td>7131.86</td><td>29.63</td><td>240.67</td></tr><tr><td>HospitalWard</td><td>75</td><td>64848</td><td>9453</td><td>[14]</td><td>204.43</td><td>0.83</td><td>247.49</td></tr></tbody></table>

<table><caption>Table 4: The temporal graphs used in our second experiment, where *t<sub>BMNR</sub>* denotes the execution time of BMNR, *t<sub>FAST</sub>* the execution time of FAST, and *t<sub>ONBRA</sub>* the execution time of ONBRA reported in [39]. The last two columns show the sample size used by ONBRA and the weighted Kendall *τ* coefficient of the ranking produced by ONBRA with this sample size, respectively.</caption><thead><tr><th>Temporal graph</th><th>n</th><th>M</th><th>T</th><th>Source</th><th>t<sub>BMNR</sub></th><th>t<sub>FAST</sub></th><th>t<sub>BMNR</sub>/t<sub>FAST</sub></th><th>t<sub>ONBRA</sub></th><th>Sample size</th><th>Weighted τ</th></tr></thead><tbody><tr><td>MathOverflow</td><td>24759</td><td>390414</td><td>389952</td><td>[29]</td><td>46594</td><td>2117</td><td>22.01</td><td>36983</td><td>30650</td><td>0.88</td></tr><tr><td>AskUbuntu</td><td>157222</td><td>726639</td><td>724715</td><td>[29]</td><td>421781</td><td>32280</td><td>13.07</td><td>35585</td><td>14831</td><td>0.86</td></tr><tr><td>SuperUser</td><td>192409</td><td>1108716</td><td>1105102</td><td>[29]</td><td>972104</td><td>63553</td><td>15.30</td><td>41856</td><td>11106</td><td>0.86</td></tr></tbody></table>

## 6.2 Analysing three larger temporal graphs

In the experimental analysis of [39], the authors consider three other temporal graphs, whose properties are summarised in the first five columns of Table 4. According to the authors, on these temporal graphs the algorithm BMNR was not able to conclude the computation on their machine since it required too much memory, while ONBRA could provide estimates of the Sh betweenness centrality values in the time indicated in the eighth column of the table. The memory problems of BMNR have been already solved in the Julia implementation of BMNR, by using dictionaries instead of matrices. Hence, we have been able to execute the algorithm BMNR with input these three temporal graphs. By using FAST, the computation of the *exact* Sh betweenness values requires approximately 0.6, 9, and 17.7 hours, thus significantly improving over BMNR (very similar results hold in the case of the SFo betweenness). Moreover, the execution time of our Julia implementation of FAST on the three networks is significantly less than, comparable with, and approximately 1.5 bigger than the reported execution time of the C implementation of ONBRA (recall that ONBRA computes estimates of the betweenness values). The second to last column of Table 4 shows the sample size used by ONBRA, which is the one reported in [39], while the last column shows the weighted Kendall *τ* coefficient between the ranking produced by FAST and the one produced by ONBRA with this sample size. As it can be seen, in order to be competitive in terms of execution time, ONBRA produces centrality values which are quite imprecise in terms of rankings.

**Comparing Sh and SFo betweennesses.** Once we have computed the Sh and SFo betweenness values of the nodes of the above three larger temporal graphs, we analysed the correlation between
<figure><img src="image_4.png" /><figcaption>Figure 2: The quartiles of the weighted Kendall τ over 14 networks, for all pairs of betweenness measures, with $\beta = 2400$.</figcaption></figure>

these two measures. These correlations are very high, especially if we consider the weighted Kendall's τ coefficient or the intersection of the top-1000 ranked nodes, whose values are 0.97, 0.98, and 0.98, and 949, 960, and 962, respectively. In other words, if we are interested in the top nodes in the rankings, then there is not so much difference between using the Sh and the SFo betweenness measure.

## 6.3 Analysing ranking correlations

<figure><img src="image_5.png" /><figcaption>Figure 3: The average weighted Kendall τ over 14 networks, for all pairs of betweenness measures, as a function of the value of β.</figcaption></figure>

Our third experiment consists of comparing the rankings of the nodes of a temporal graph when sorted according to their betweenness values, computed with different waiting constraints and for different walk optimality criteria. In particular, we considered the following values of $\beta$: 300, 600, 1200, 2400, and $\infty$. Moreover, we computed the Fa, Fo, Sh, SFa, and SFo betweenness values (by using the general FAST algorithm, that is, Algorithm 4 in the appendix). However, we
did not compute the Fo and the Fa betweenness values in the case $\beta = \infty$, due to the huge number of optimal walks: this involves using Julia number data structures which causes our algorithm to take an excessive amount of time needed to calculate the exact betweenness values. For the very same reason (for different values of $\beta$), we excluded the **Topology** network from the dataset used in this experiment, which otherwise is the same as the one used in the first experiment.

The values of the Kendall $\tau$ correlation, of its weighted variant, and of the top-50 intersection are shown in the tables included in Appendices 16: we here discuss the weighted Kendall $\tau$ results only. From the tables in the appendix, we can conclude that all the betweenness measures are highly correlated, with the Sh and the SFa betweenness being the two more correlated (see the box plot of Figure 2, which show the quartiles of the correlation values for $\beta = 2400$). In particular, in half of the networks in the dataset the weighted Kendall $\tau$ for this pair of betweenness measures with $\beta = 2400$ is at least 0.97 and the minimum weighted Kendall $\tau$ is 0.84. This minimum value is reached in correspondence of the **Primary school** network, for which the weighted Kendall $\tau$ is the minimum one for all the pairs of betweenness measures.

Another interesting observation is that the weighted Kendall $\tau$ values seem to depend on the waiting constraints. In particular, we can observe that these values tend to decrease as the value of $\beta$ increases, as shown in the left part of Figure 3 where the average weighted Kendall $\tau$ values over the fourteen networks is shown as a function of the value of $\beta$. This behaviour might be justified by the fact that when $\beta$ increases the set of optimal walks with respect to different betweenness measures may be quite different: that is, the more stringent are the waiting constraints the more similar are the sets of optimal walks.

## 6.4 Analysing public transport networks

All the networks analysed so far are “uniform” temporal graphs, in the sense that the traversal time of all temporal edges is equal to 1. In this last experiment, instead, we use a subset of the dataset published in [26] and used [15]. This dataset includes 25 cities’ public transport networks and is available in multiple formats including the temporal edge list for a specific working day (note that each temporal edge has a travel time usually much greater than 1). The list of the cities that we used in our experiment is summarized in Table 5, where, for each city, we provide, in the first two columns, the number of nodes (that is, the number of stops) and the number of temporal edges. In this experiment, we focus on the SFa and the SFo betweenness values, because of two main reasons. First, each temporal edge of the temporal graph relates to the connection between two stations of a transport trip: hence, counting the number of temporal edges in a walk does not indicate the number of transfers (which instead should be more interesting to analyse in the case of a public transport network). For this reason, we have not analysed the Sh betweenness measure. Secondly, focusing on walks which are the shortest among the fastest and the foremost ones allows us to analyse walks which are the closest to being paths in the case of waiting constraints (which are both desirable properties in the case of public transport trips).

Given a temporal graph $G = (V, E, \beta)$, the *underlying graph* of G is the graph whose set

<table><caption>Table 5: The six cities analysed in our case study. The value *m* denotes the number of edges in the underlying graph, while the value *t<sub>B</sub>* denotes the execution time of the Brandes’ algorithm on this graph.</caption><thead><tr><th>City</th><th>n</th><th>M</th><th>m</th><th>M/m</th><th>t<sub>FAST</sub></th><th>t<sub>B</sub></th></tr></thead><tbody><tr><td>Berlin</td><td>4601</td><td>1048209</td><td>12359</td><td>85</td><td>35555</td><td>8.03</td></tr><tr><td>Bordeaux</td><td>3435</td><td>236595</td><td>4040</td><td>59</td><td>2336</td><td>2.95</td></tr><tr><td>Kuopio</td><td>549</td><td>32117</td><td>979</td><td>33</td><td>126</td><td>0.07</td></tr><tr><td>Paris</td><td>11950</td><td>1823871</td><td>16704</td><td>109</td><td>121157</td><td>33.51</td></tr><tr><td>Rome</td><td>7869</td><td>1051211</td><td>10143</td><td>104</td><td>70236</td><td>18.77</td></tr><tr><td>Venice</td><td>1874</td><td>118480</td><td>3464</td><td>34</td><td>439</td><td>0.67</td></tr></tbody></table>
<figure><img src="image_6.png" /><figcaption>Figure 4: The weighted Kendall τ between the SFa and the SFo betweenness rankings (solid) and between the SFo betweenness and the betweenness rankings (dashed), for each public transport network and for $\beta = 300, 600, 1200, 2400, \infty$.</figcaption></figure>

of nodes is $V$ and whose set of edges contains all pairs $(u, v)$ such that $(u, v, \tau, \lambda) \in E$, for some $\tau$ and $\lambda$. The main goal of this experiment is to verify how much the SFa and the SFo betweenness measures of a temporal graph are correlated to the (classical) betweenness measure of the corresponding underlying graph. In the second to last column of the table we show the average execution time of the FAST algorithm computing the SFa and the SFo betweenness with $\beta = 300, 600, 1200, 2400, \infty$, while the last column shows the execution time for computing the betweenness values of the underlying graph by using the Brandes' algorithm [7] (as implemented in the Julia Graphs package [18]). As it can be seen, this latter algorithm is significantly faster than the FAST algorithm. Actually, we might expect an additional multiplicative factor close to the ratio $M/m$, where $m$ denotes the number of edges in the underlying graph. In practice, this factor is between 20 and 50 times bigger because of two main reasons: on the one hand, our code for the general case is not as optimised as the code for the non-restless case thus leading to a code around ten times slower, on the other hand we are forced to use big data structures in order to deal with the huge number of optimal walks (which is not the case with the underlying graphs).

Since computing the betweenness of the underlying graph is significantly faster than our algorithm, it is worth determining the correlation between this betweenness and the SFa and the SFo betweenness. As it is shown in Figure 4, the weighted Kendall $\tau$ between the SFa and the SFo betweenness rankings is very high for all values of $\beta$. On the contrary, the weighted Kendall $\tau$ between the SFo betweenness and the betweenness rankings is significantly lower, especially when $\beta = 300$ or $\beta = 600$, which correspond to five and ten minutes of waiting time, respectively (similar results hold for the SFa betweenness). These results thus suggest that the betweenness of the underlying graph cannot be used as a proxy of the SFa and the SFo betweenness, whenever waiting constraints have to be satisfied. This contrasts with what has been shown in [2], where the authors found high correlations between the SFo betweenness with $\beta = \infty$ (that is, when no waiting constraint are used) and the betweenness of the underlying graph.

# 7 Further research

As we follow the framework of [9], our algorithm can support (with the same complexity and with exact computation) more general waiting constraints (such as minimum waiting time and maximum waiting time varying for each node), and edge weights/costs with appropriate cost
and target-cost structures. From a theoretical point of view, it would be interesting to look for conditional lower bound on the computation of the betweenness in the restless case. From an experimental point of view, instead, it would be worth enriching the temporal graph model and appropriately modify our algorithms in order to take into account the number of transfers in public transport networks, and, thus, focusing on the betweenness values based on the walks with the minimum number of transfers. Finally, we think it would be interesting to experimentally compare our algorithm with more recent papers that propose new exact [50] and approximation [17] algorithms for computing the temporal betweenness in the non-restless case.

# Appendix

## 8 Proofs of Section 3

The proofs of Facts 1 and 2 immediately follows from the definition of Sh and SFo walks.

**Proof of Fact 3** From the previous definitions, we have that

$$
\begin{align*}
b_u &= \sum_{s,t \in V \setminus \{u\} : \chi_{s,t} = 1} \frac{\sigma_{s,u,t}^*}{\sigma_{s,t}^*} = \sum_{s \in V \setminus \{u\}} \sum_{t \in V \setminus \{u\} : \chi_{s,t} = 1} \frac{\sigma_{s,u,t}^*}{\sigma_{s,t}^*} \\
&= \sum_{s \in V \setminus \{u\}} \sum_{t \in V \setminus \{u\} : \chi_{s,t} = 1} \frac{1}{\sigma_{s,t}^*} \sum_{e \in E_u^h} \sigma_{s,e,t}^* \\
&= \sum_{s \in V \setminus \{u\}} \sum_{e \in E_u^h} \sum_{t \in V \setminus \{u\} : \chi_{s,t} = 1} \frac{\sigma_{s,e,t}^*}{\sigma_{s,t}^*} \\
&= \sum_{s \in V \setminus \{u\}} \sum_{e \in E_u^h} \left( \sum_{t \in V : \chi_{s,t} = 1} \frac{\sigma_{s,e,t}^*}{\sigma_{s,t}^*} - \chi_{s,u} \frac{\sigma_{s,e,u}^*}{\sigma_{s,u}^*} \right) \\
&= \sum_{s \in V \setminus \{u\}} \sum_{e \in E_u^h} \left( b_{s,e} - \chi_{s,u} \frac{\sigma_{s,e,u}^*}{\sigma_{s,u}^*} \right) = \\
&= \sum_{s \in V \setminus \{u\}} \left( \sum_{e \in E_u^h} b_{s,e} - \chi_{s,u} \sum_{e \in E_u^h} \frac{\sigma_{s,e,u}^*}{\sigma_{s,u}^*} \right) \\
&= \sum_{s \in V \setminus \{u\}} \left( \left( \sum_{e \in E_u^h} b_{s,e} \right) - \chi_{s,u} \right),
\end{align*}
$$

where the last equality is due to the fact that $\sigma_{s,u}^* = \sum_{e \in E_u^h} \sigma_{s,e,u}^*$. The fact thus follows. $\square$

**Proof of Fact 4** Since the st-walks in $W_{s,e,t}$ are SFo, from Facts 2 and 1 it follows that any $W \in W_{s,e,t}$, whose last temporal edge is $f$, is a shortest sf-walk, and that the prefix of $W$ up to the temporal edge $e$ is a shortest se-walk. As a consequence, the total number of distinct prefixes of walks in $W_{s,e,t}$ is equal to $\sigma_{s,e}$ and each such prefix has the same length, say $c$, which is the length of a Sh se-walk. Let $W_1$ be the prefix of a walk $W \in W_{s,e,t}$ up to the temporal edge $e$, $X_2 = \langle e_1 e_2 \cdots e_k \rangle$ be the suffix of a walk $X \in W_{s,e,t}$ following the temporal edge $e$, and $Y = W_1 \cdot e_1 \cdot e_2 \cdots \cdot e_k$. Then $\gamma(Y) = \gamma(X)$ since all prefixes have length $c$. Moreover, both $X$ and $Y$ ends with the temporal edge $e_k$. Hence, $\mathrm{TC}(e_k, \gamma(X)) =^F \mathrm{TC}(e_k, \gamma(Y))$. Since $X \in W_{s,e,t}$, then also $Y \in W_{s,e,t}$. This implies that we can combine any prefix with any suffix and obtain a SFo st-walk. We thus have $\sigma_{s,e,t}^* = \sigma_{s,e} \cdot \theta_{s,e,t}$ and the fact follows. $\square$
**Proof of Lemma 5** From Fact 4 it follows that

$$b_{s,e} = \sum_{t \in V: \chi_{s,t} = 1} \frac{\sigma_{s,e,t}^*}{\sigma_{s,t}^*} = \sigma_{s,e} \sum_{t \in V: \chi_{s,t} = 1} \frac{\theta_{s,e,t}}{\sigma_{s,t}^*} \quad (1)$$

By distinguishing the case in which $t = v$, we have

$$b_{s,e} = \sigma_{s,e} \sum_{t \in V: \chi_{s,t} = 1} \frac{\theta_{s,e,t}}{\sigma_{s,t}^*} = \sigma_{s,e} \left( \sum_{t \in V \setminus \{v\}: \chi_{s,t} = 1} \frac{\theta_{s,e,t}}{\sigma_{s,t}^*} + \frac{\theta_{s,e,v}}{\sigma_{s,v}^*} \right) \\ = \sigma_{s,e} \left( \sum_{t \in V \setminus \{v\}: \chi_{s,t} = 1} \frac{\theta_{s,e,t}}{\sigma_{s,t}^*} + \frac{\hat{\theta}_{s,e,v}}{\sigma_{s,v}^*} \right) + \left\{ \begin{array}{ll} \frac{\sigma_{s,e}^*}{\sigma_{s,v}^*} & \text{if } \sigma_{s,e}^* > 0, \\ 0 & \text{otherwise,} \end{array} \right.$$

where

$$\hat{\theta}_{s,e,t} = \begin{cases} \theta_{s,e,t} & \text{if } v \neq t \lor \sigma_{s,e}^* = 0, \\ \theta_{s,e,t} - 1 & \text{otherwise,} \end{cases}$$

and the second inequality is due to the fact that $\sigma_{s,e} = \sigma_{s,e}^*$ whenever $\sigma_{s,e}^* > 0$. We hence have that

$$b_{s,e} = \sigma_{s,e} \sum_{t \in V: \chi_{s,t} = 1} \frac{\hat{\theta}_{s,e,t}}{\sigma_{s,t}^*} + \left\{ \begin{array}{ll} \frac{\sigma_{s,e}^*}{\sigma_{s,v}^*} & \text{if } \sigma_{s,e}^* > 0, \\ 0 & \text{otherwise.} \end{array} \right.$$

Note that $\hat{\theta}_{s,e,t}$ counts only non-empty suffixes of $\Theta$-optimal st-walks containing $e$ (which exist only if $v = t$ and $\sigma_{s,e}^* > 0$). In such walks the first temporal edge $f$ of the non-empty suffix is a successor of $e$. This implies

$$\hat{\theta}_{s,e,t} = \sum_{f \in \mathrm{succ}_{s,e,t}} \theta_{s,f,t},$$

which yields:

$$b_{s,e} = \sigma_{s,e} \sum_{t \in V: \chi_{s,t} = 1} \frac{\sum_{f \in \mathrm{succ}_{s,e,t}} \theta_{s,f,t}}{\sigma_{s,t}^*} + \left\{ \begin{array}{ll} \frac{\sigma_{s,e}^*}{\sigma_{s,v}^*} & \text{if } \sigma_{s,e}^* > 0, \\ 0 & \text{otherwise} \end{array} \right. \\ = \sigma_{s,e} \sum_{f \in \mathrm{succ}_{s,e}} \sum_{t \in V: \chi_{s,t} = 1} \frac{\theta_{s,f,t}}{\sigma_{s,t}^*} + \left\{ \begin{array}{ll} \frac{\sigma_{s,e}^*}{\sigma_{s,v}^*} & \text{if } \sigma_{s,e}^* > 0, \\ 0 & \text{otherwise,} \end{array} \right. \\ = \sigma_{s,e} \sum_{f \in \mathrm{succ}_{s,e}} \frac{b_{s,f}}{\sigma_{s,f}} + \left\{ \begin{array}{ll} \frac{\sigma_{s,e}^*}{\sigma_{s,v}^*} & \text{if } \sigma_{s,e}^* > 0, \\ 0 & \text{otherwise,} \end{array} \right.$$

where the second equality is due to the fact the $f \in \mathrm{succ}_{s,e}$ if and only there exists $t \in V \setminus \{s\}$ such that $f \in \mathrm{succ}_{s,e,t}$, and the last equality follows from Equation 1. The lemma is thus proved. $\square$

## 9 An iteration of Algorithm 1

In Figure 5 (where we use over-lined integers to denote the position of a temporal edge in $E^{\mathrm{arr}}$), we show the iteration of the forward phase of Algorithm 1, in which the edge $e_{\bar{k}} = (u, v, \tau, \lambda)$ is analysed. The gray temporal edges in $E^{\mathrm{arr}}$ are the temporal edges already scanned, while the gray temporal edges in $E_{\mathrm{node}}^{\mathrm{dep}}[u]$ and in $E_{\mathrm{node}}^{\mathrm{dep}}[v]$ are the temporal edges which have been finalised. The figure shows these two lists at the beginning of the iteration (upper copy) and at the end of the iteration (lower copy): between the two copies, the finalisation of the involved temporal edges is shown.
<figure><img src="image_7.png" /><figcaption>Figure 5:</figcaption></figure>

## 10 Proof of Theorem 6

As it can be seen in Algorithm 1, our algorithm executes a constant number of cycles on all nodes and on all temporal edges. More precisely, both the forward phase and the backward phase scan once each edge in $E^{\text{arr}}$ and each index in $E_{\text{node}}^{\text{dep}}$. Hence, overall the time complexity of the algorithm is linear in the number of temporal edges. For what concerns the correctness of the algorithm, let us consider the forward and the backward phase separately.

* During the forward phase, the following invariant is maintained after scanning $k$th edge in $E^{\text{arr}}$: $\forall v \in V$, $c[v]$ is the shortest length of an sv-walk in $G_k$, $\sigma[v]$ is the number of shortest sv-walks in $G_k$ (with length $c[v]$), and all edges in $E_{\text{node}}^{\text{dep}}[v][l[v]:r]$ extend such walks. The proof follows easily by induction on $k$ and the fact that any walk in $G_k$ which is not in $G_{k-1}$ must end with $e_k$. This comes from the fact that any temporal walk is strict since we assume positive travel times, and its temporal edges must appear in order in $E^{\text{arr}}$ which is sorted by arrival times.

* During the backward phase, the following invariant is maintained after scanning backward the $k$th edge in $E^{\text{arr}}$: $\delta[v] = \sum_{f \in E_{\text{node}}^{\text{dep}}[v][l[v]:r]} \frac{b_{s,f}}{\sigma_{s,f}}$, where $r$ denotes the last index of an edge $f \in E_{\text{node}}^{\text{dep}}[v]$ such that a shortest sf-walk in $G$ can be obtained by extending a walk in $G_k$. This follows from Lemma 5 and an easy induction on $k$ as the index $r$ can only decrease as $k$ decreases. Similarly as in the forward phase, we use the fact that $E^{\text{arr}}$ is a topological ordering for the successor relation: if $f$ is successor of $e$, then $f$ appears after $e$ in $E^{\text{arr}}$.

The theorem is then proved. □

## 11 Execution of Algorithm 1

Let us consider the temporal graph of Figure 6, where the four lists $E^{\text{arr}}$, $E^{\text{dep}}$, $E_{\text{node}}^{\text{dep}}$, and $E_{\text{node}}^{\text{arr}}$ are also depicted. In Table 6, the execution of the forward phase (lines 4-13), with source node $v_1$, is represented by showing the values of the main variables of the algorithm at the end of the analysis of each temporal edge in $E^{\text{arr}}$. Let us analyse two specific consecutive iterations of this phase.

**The temporal edge $e = (v_1, v_3, 3, 1)$ is scanned.** This is the second and last temporal edge in $E_{\text{node}}^{\text{dep}}[v_1]$. Since $l[v_1]$ has been set equal to 2 while scanning the first temporal edge, all temporal edges in $E_{\text{node}}^{\text{dep}}[v_1]$ are now finalised. However, $c[v_1] = \infty$, so that the effect of the finalisation is just to set $l[v_1] = 3$ (indeed, there are no more temporal edges with the tail equal to $v_1$). The tail of $e$ is the source node: hence, $C[e]$ and $\Sigma[e]$ are set equal to 1
<figure><img src="image_8.png" /><figcaption>Figure 6: An example of a temporal graph, where $n = 6$, $M = 7$, $T = 6$.</figcaption></figure>

because $\langle e \rangle$ is, indeed, the unique shortest se-walk. Since, now, $C[e] = 1 < 2 = c[v_3]$ and since the first temporal edge in $E_{\text{node}}^{\text{dep}}[v_3]$ that can extend $e$ is the second one (that is, $e_5$), the first edge of $E_{\text{node}}^{\text{dep}}[v_3]$ (that is, $e_4$) is finalised, by setting $C[e_4] = c[v_3] + 1 = 3$ and $\Sigma[e_4] = \sigma[v_3] = 1$: as we will see, this will allow the algorithm to assign the correct value to $c[v_4]$ in the next iteration. Finally, since $C[e] < c[v_3]$, this implies that the algorithm has found a shorter $v_1v_3$-walk: for this reason, $c[v_3]$ is set equal to $C[e] = 1$ and $\sigma[v_3]$ is set equal to $\Sigma[e] = 1$. Finally, the algorithm sets $L[e]$ equal to $2$, in order to remember, during the backward phase, that the first temporal edge in $E_{\text{node}}^{\text{dep}}[v_3]$, that can extend $e$ and result in a Sh walk, is the second one.

<table><caption>Table 6: The evolution of the main variables of Algorithm 1 during the forward phase.</caption><thead><tr><th>e = (u, v, τλ)</th><th>L[e]</th><th>C[e]</th><th>Σ[e]</th><th>E<sup>dep</sup><sub>node</sub>[u]</th><th>l[u]</th><th>c[u]</th><th>σ[u]</th><th>E<sup>dep</sup><sub>node</sub>[v]</th><th>l[v]</th><th>c[v]</th><th>σ[v]</th></tr></thead><tbody><tr><td>1̄ = (v<sub>1</sub>, v<sub>2</sub>, 1, 1)</td><td>1̄</td><td>1</td><td>1</td><td>[1, 3]</td><td>2̄</td><td>∞</td><td>0</td><td>[2]</td><td>1̄</td><td>1</td><td>1</td></tr><tr><td>2̄ = (v<sub>2</sub>, v<sub>3</sub>, 2, 1)</td><td>1̄</td><td>2</td><td>1</td><td>[2]</td><td>2̄</td><td>1</td><td>1</td><td>[4, 5, 7]</td><td>1̄</td><td>2</td><td>1</td></tr><tr><td>3̄ = (v<sub>1</sub>, v<sub>3</sub>, 3, 1)</td><td>2̄</td><td>1</td><td>1</td><td>[1, 3]</td><td>3̄</td><td>∞</td><td>0</td><td>[4, 5, 7]</td><td>2̄</td><td>1</td><td>1</td></tr><tr><td>4̄ = (v<sub>3</sub>, v<sub>4</sub>, 3, 1)</td><td>1̄</td><td>3</td><td>1</td><td>[4, 5, 7]</td><td>2̄</td><td>1</td><td>1</td><td></td><td>1̄</td><td>3</td><td>1</td></tr><tr><td>5̄ = (v<sub>3</sub>, v<sub>5</sub>, 4, 1)</td><td>1̄</td><td>2</td><td>1</td><td>[4, 5, 7]</td><td>3̄</td><td>1</td><td>1</td><td>[6]</td><td>1̄</td><td>2</td><td>1</td></tr><tr><td>6̄ = (v<sub>5</sub>, v<sub>6</sub>, 5, 1)</td><td>1̄</td><td>3</td><td>1</td><td>[6]</td><td>2̄</td><td>2</td><td>1</td><td></td><td>1̄</td><td>3</td><td>1</td></tr><tr><td>7̄ = (v<sub>3</sub>, v<sub>6</sub>, 6, 1)</td><td>1̄</td><td>2</td><td>1</td><td>[4, 5, 7]</td><td>4̄</td><td>1</td><td>1</td><td></td><td>1̄</td><td>2</td><td>1</td></tr></tbody></table>

<table><caption>Table 7: The evolution of the main variables of Algorithm 1 during the backward phase.</caption><thead><tr><th>e = (u, v, τλ)</th><th>L[e]</th><th>C[e]</th><th>Σ[e]</th><th>Σ*[E]</th><th>b[e]</th><th>E<sup>dep</sup><sub>node</sub>[v]</th><th>l[v]</th><th>c[v]</th><th>σ*[v]</th><th>δ[v]</th></tr></thead><tbody><tr><td>7̄ = (v<sub>3</sub>, v<sub>6</sub>, 6, 1)</td><td>1̄</td><td>2</td><td>1</td><td>0</td><td>0.0</td><td></td><td>1̄</td><td>2</td><td>1</td><td>0.0</td></tr><tr><td>6̄ = (v<sub>5</sub>, v<sub>6</sub>, 5, 1)</td><td>1̄</td><td>3</td><td>1</td><td>1</td><td>1.0</td><td></td><td>1̄</td><td>2</td><td>1</td><td>0.0</td></tr><tr><td>5̄ = (v<sub>3</sub>, v<sub>5</sub>, 4, 1)</td><td>1̄</td><td>2</td><td>1</td><td>1</td><td>2.0</td><td>[6]</td><td>1̄</td><td>2</td><td>1</td><td>1.0</td></tr><tr><td>4̄ = (v<sub>3</sub>, v<sub>4</sub>, 3, 1)</td><td>1̄</td><td>3</td><td>1</td><td>1</td><td>1.0</td><td></td><td>1̄</td><td>3</td><td>1</td><td>0.0</td></tr><tr><td>3̄ = (v<sub>1</sub>, v<sub>3</sub>, 3, 1)</td><td>2̄</td><td>1</td><td>1</td><td>0</td><td>2.0</td><td>[4, 5, 7]</td><td>2̄</td><td>1</td><td>1</td><td>2.0</td></tr><tr><td>2̄ = (v<sub>2</sub>, v<sub>3</sub>, 2, 1)</td><td>1̄</td><td>2</td><td>1</td><td>1</td><td>2.0</td><td>[4, 5, 7]</td><td>1̄</td><td>1</td><td>1</td><td>1.0</td></tr><tr><td>1̄ = (v<sub>1</sub>, v<sub>2</sub>, 1, 1)</td><td>1̄</td><td>1</td><td>1</td><td>1</td><td>3.0</td><td>[2]</td><td>1̄</td><td>1</td><td>1</td><td>2.0</td></tr></tbody></table>

**The temporal edge e = (v<sub>3</sub>, v<sub>4</sub>, 3, 1) is scanned.** This is the first temporal edge in $E_{\text{node}}^{\text{dep}}[v_3]$. Since $l[v_3]$ has been set equal to 2 in the previous iteration, no finalisation has to be executed (indeed, the cost $c[v_3] = 1$ refers to the path $\langle e_3 \rangle$ which is not extendable by e). Recall that, in the previous iteration, the algorithm has set $C[e] = 0$ to 3, which is less than $\infty = c[v_4]$. Since $E_{\text{node}}^{\text{dep}}[v_4]$ is empty, no finalisation takes place, but, due to the fact that $C[e] < c[v_4]$, $c[v_4]$ is set equal to 3 and $\sigma[v_4]$ is set equal to 1. That is, the algorithm has correctly computed the length of the unique Sh $v_1v_4$-walk. Finally, the algorithm sets $L[e]$ equal to $1$:
since $|E_{\text{node}}^{\text{dep}}[v_4]| = 0$, this implies that no temporal edge can extend e.
Note how, at the end of the forward phase, the value of $l[v]$ is equal to $|E_{\text{node}}^{\text{dep}}[v]| + 1$, for each node $v$ (since all indices of $E_{\text{node}}^{\text{dep}}[v]$ have been scanned for finalizing the corresponding temporal edges). This guarantees that, in the following backward phase, all temporal edges in $E_{\text{node}}^{\text{dep}}[v]$ will be considered. Before starting the backward phase, the algorithm computes, for each node $v$, the values $c^*[v]$ (lines 16-18): to this aim, it just look for the temporal edge with head $v$ such that the pair $(\text{arr}(e), C[e])$ is 'lexicographically' minimum (that is, minimum with respect to the $\triangleleft$ relation). In lines 19-21, the algorithm also computes, for each temporal edge $e = (u, v, \tau, \lambda)$, the number $\Sigma^*[e]$ of SFo $sv$-walks ending with $e$ and, for each node $v$, the number $\sigma^*[v]$ of SFo $sv$-walks (which is the sum of the values $\Sigma^*[e]$ for all temporal edges $e$ with head $v$).

In Table 7, the execution of the backward phase (lines 22-27), with source node $v_1$, is represented by showing the values of the main variables of the algorithm at the end of the analysis of each temporal edge in $E^{\text{arr}}$ (in reverse order). Let us analyse one specific iteration of this phase, that is, the one corresponding to the temporal edge $e = (v_2, v_3, 2, 1)$, which is the terminal temporal edge of a SFo $v_1v_3$-walk and an intermediate temporal edge of the SFo $v_1v_4$-walk. Note that, at the end of the previous iteration, node $v_3$ has accumulated in $\delta[v_3] = 2$ the two SFo walks from $v_1$ to $v_5$ and from $v_1$ to $v_6$. However, these walks do not use the temporal edge $e$: hence, $\delta[v_3]$ should not be "transmitted" to $e$. That is why, at line 24, the algorithm checks whether $c^*[v_3] \triangleleft (\text{arr}(e), C[e])$. Since this is the case, the value of $\delta[v_3]$ is zeroed and the current value of $c^*[v_3]$ is set equal to $(\text{arr}(e), C[e])$. The algorithm then continues, as we already said, by simply applying Lemma 5. Note that, at each iteration, the algorithm "moves" left the right extreme of the sub-list of $E_{\text{node}}^{\text{dep}}[v]$ to be considered by the following iterations, by assigning to $l[v]$ the value $L[e]$ of the currently scanned temporal edge $e$.

# 12 Computing the Sh betweenness

It is easy to see that Fact 2 can be adapted to the case in which we consider Sh walks as follows.

**Fact 7.** Given a temporal graph $G = (V, E, \beta)$, let $W$ be a Sh st-walk (for some $s, t \in V$) and let $e$ be the last temporal edge of $W$. Then, $W$ is a Sh walk among the se-walks.

Moreover, all the definitions concerning the SFo betweenness can be appropriately adapted to the Sh case and all the results proved for the SFo betweenness can be proved also for the Sh betweenness. The forward phase of the algorithm for computing the non-restless Sh betweenness can then be the same as in the case of the SFo betweenness, as shown in lines 4-13 of Algorithm 2 (note that also the finalisation function is exactly the same). The intermediate phase of the algorithm can be even simplified since the values $c^*[v]$ are now integers values representing the length of Sh $sv$-walks (we are not interested anymore in the arrival time of the walks). Finally, the backward phase is exactly the same as in the case of the SFo betweenness apart from the fact that the $\delta$-value of a node is zeroed only if the currently scanned edge with head $v$ is not a terminal edge of a Sh $sv$-walk. In particular, at line 19, the algorithm checks whether, for the currently scanned edge $e$ with head $v$, $C[e] > c[v]$: if this the case, then $e$ is not a terminal edge of a Sh $sv$-walk, but, since $L[e] > 0$, $e$ is an intermediate edge of a Sh $su$-walk, for some other node $u$.

Similarly to what we have done in Appendix 10, we can then prove the following result.

**Theorem 8.** For any temporal graph $G = (V, E, \infty)$ and for any $s \in V$, Algorithm 2 correctly computes the s-Sh betweenness $b_{s,e}$ in time $O(M)$.

# 13 The restless algorithm for SFo

To better understand the data structure introduced in Section 4.2 and why we need a list of interval quintuples, let us suppose that the list $E_{\text{node}}^{\text{dep}}[v]$ has been processed in previous iterations up to its index $p$, and that $\mathcal{I}_v$ contains only one interval quintuple $Q_1 = (l_1, r_1, c_1, \{e'_1, e''_1\}, \eta_1)$ (see the left
<caption>**Algorithm 2:** Compute non-restless Sh $b_{s,e}$ for all $e \in E$</caption>

input : $G = (V, E, \infty)$ (represented by $E^{\text{dep}}$ and $E^{\text{arr}}$) and $s \in V$
output : $s$-Sh betweenness $b_{s,e}$, for all $e \in E$
1 Compute the lists $E_{\text{node}}^{\text{dep}}$ and $E_{\text{node}}^{\text{arr}}$;
2 **foreach** $v \in V$ **do** $l[v] := 1$; $c[v] := \infty$; $\sigma[v] := 0$;
3 **foreach** $e \in E$ **do** $L[e] := 0$; $C[e] := \infty$; $\Sigma[e] := 0$;
4 **foreach** $e = (u, v, \tau, \lambda) \in E^{\text{arr}}$ **do**
5 **if** $E_{\text{dep}}^{\text{arr}}[e] \ge l[u]$ **then** **Finalize**($u, E_{\text{dep}}^{\text{arr}}[e]$);
6 **if** $u = s$ **then** $C[e] := 1$; $\Sigma[e] := 1$;
7 **if** $C[e] \ne \infty$ **then**
8 **if** $C[e] \le c[v]$ **then**
9 $a = l[v]$; $D := E_{\text{node}}^{\text{dep}}[v]$;
10 **while** $a \le |D| \land \text{dep}(E^{\text{arr}}[D[a])) < \tau + \lambda$ **do** $a := a + 1$;
11 **Finalize**($v, a - 1$);
12 **if** $C[e] < c[v]$ **then** $c[v] := C[e]$; $\sigma[v] := 0$;
13 $\sigma[v] := \sigma[v] + \Sigma[e]$; $L[e] := a$;
14 **foreach** $v \in V$ **do** $c^*[v] := c[v]$; $\sigma^*[v] := \sigma[v]$; $\delta[v] := 0$;
15 **foreach** $e \in E$ **do** $\Sigma^*[e] := 0$; $b[e] := 0$;
16 **foreach** $e = (u, v, \tau, \lambda) \in E^{\text{arr}}$ **do**
17 **if** $C[e] = c^*[v] < \infty$ **then** $\Sigma^*[e] := \Sigma[e]$;
18 **foreach** $e = (u, v, \tau, \lambda) \in \text{reverse}(E^{\text{arr}})$ : $L[e] > 0$ **do**
19 **if** $c[v] < C[e]$ **then** $\delta[v] := 0$; $c[v] := C[e]$;
20 **for** $f \in E_{\text{node}}^{\text{dep}}[v][L[e]:l[v] - 1]$ **do** $\delta[v] := \delta[v] + b[f]/\Sigma[f]$;
21 $l[v] := L[e]$; $b[e] := \Sigma[e]\delta[v]$;
22 **if** $\Sigma^*[e] > 0$ **then** $b[e] := b[e] + \Sigma^*[e]/\sigma^*[v]$;
23 **return** $b$
24 **Finalize**($u, j$):
25 **if** $c[u] \ne \infty$ **then**
26 **foreach** $f \in E_{\text{node}}^{\text{dep}}[l[u], j]$ **do** $C[f] := c[u] + 1$; $\Sigma[f] := \sigma[u]$;
27 $l[u] := j + 1$;

<figure><img src="image_9.png" /><figcaption>Figure 7: Status of the list $E_v^{\text{dep}}$ before and after the update in the restless algorithm.</figcaption></figure>

part of Figure 7). This means that, for each edge $f \in Q_1.I = E_{\text{node}}^{\text{dep}}[v][l_1, r_1]$, the length of the Sh sv-walk found so far, which is extended by $f$, is $c_1$, that there are $\eta_1$ sv-walks with length $c_1$ that are extended by $f$, and that the edges preceding $f$ in these walks are $e'_1$ or $e''_1$. Let us suppose that the next temporal edge to be scanned is $e = (u, v, \tau, \lambda)$ and that the minimum length of any se-walk is $c$. The edges in $Q_1.I$ with departure time earlier than $\text{arr}(e)$ do not extend $e$ nor any other temporal edge that will scanned in the next iterations. Thus they can be finalized, if they have not been already (we will describe the finalisation process below). These edges correspond to those in the interval $F$ in the right part of of Figure 7, and have index in $E_{\text{node}}^{\text{dep}}[v]$ from $l_1$ to $l'_1 - 1$, where $l'_1$ is the index of the first temporal edge in $Q_1.I$ whose departure time is greater than or equal to $\text{arr}(e)$. This means that $Q_1$ is now updated to $Q_1 = (l'_1, r_1, c_1, \{e'_1, e''_1\}, \eta_1)$, and $p$ is updated to $l'_1 - 1$. Now we also have to consider the temporal edges with index greater than $r_1$. These edges were not reachable before this iteration. However, those of them that extends $e$ are now reachable and do extend an se-walk with length $c$ (these edges are those that have index between $l_2$ and $r_2$ in the figure). If $c$ is equal to $c_1$, then the minimum length of a walk from $s$ that
reaches all the temporal edges with index between $l'_1$ and $r_2$ would still be $c_1$ but $e$ has to be added to set of predecessors and the number $\Sigma[e]$ of se-walk with length $c$ has to be added to $\eta_1$: that is, $Q_1$ is updated to $Q_1 = (l'_1, r_2, c_1, \{e'_1, e''_1, e\}, \eta_1 + \Sigma[e])$. If, instead, $c$ is less than $c_1$, then the minimum length of a walk from $s$ that reaches all the temporal edges with index between $l'_1$ and $r_2$ would be $c$ and these temporal edges can be grouped into a single interval: that is, $Q_1$ is updated to $Q_1 = (l'_1, r_2, c, \{e\}, \Sigma[e])$. Finally, if $c$ is greater than $c_1$ (which is the case represented in the figure), we need to add an interval quintuple $Q_2 = (l_2, r_2, c, \{e\}, \Sigma[e])$, where $l_2 = r_1 + 1$. We also store in the variables $L[e]$ and $R[e]$ the left and right extreme of the last interval quintuple in $\mathcal{I}_v$ (either $Q_1$ in the two first cases, or $Q_2$ in the third case): these values correspond to the interval of edges having $e$ as predecessor and will be used in the backward phase. When $\mathcal{I}_v$ contains more quintuples, we can proceed similarly and need to inspect only quintuples at the beginning or at the end of $\mathcal{I}_v$.

The finalisation of an edge is also more complicated than in the case of the non-restless Sh and SFo case. Suppose that we want to finalise all edges in $E_{\text{node}}^{\text{dep}}[v]$ from the position $l[v]$ to the position $j$. Since these positions are now partitioned into intervals corresponding to the interval quintuples in $\mathcal{I}_v$, we scan these interval quintuples, starting from the first one, until we find an interval quintuple $Q$ such that $Q.l > j$. For each scanned interval quintuple $(l, r, c, P, \eta)$ and for each edge $e \in P$ such that $R[e] \le j$, we can finalize all edges $f$ in $E_{\text{node}}^{\text{dep}}[v][l:R[e]]$, that is, we can set the minimum length $C[f]$ of a sf-walk equal to the minimum length $c$ of a Sh walk which can be extended by $f$ plus one, and the number of these sf-walks equal to the number of Sh walks that can be extended by $f$ (that is, we set $\Sigma[f] = \eta$). Note that, once all edges $f$ have been finalised, the number of Sh walks that can now be extended has to be reduced by subtracting to it the number of Sh se-walks (that is, we set $\eta = \eta - \Sigma[e]$), since all these latter walks have now been indeed extended. If a scanned quintuple has been emptied (that is, if $j \ge r$), then we can remove it from $\mathcal{I}_v$ and continue with the next one. Otherwise, we can update it by setting its left extreme equal to $j+1$. Finally, at the end of the scanning of $\mathcal{I}_v$, we can also set $l[v]$ equal to $j+1$ (as we already did in the non-restless cases).

Once computed (similarly to the non-restless case), for any node $v$, the earliest arrival time among all sv-walks together with the minimum length of such Fo walks, the number of such SFo sv-walks, and, for any temporal edge $e$, the number of SFo se-walks, the backward phase of the general algorithm applies, once again, Lemma 5. As in the case of the non-restless case, the contribution of the successors of a currently scanned temporal edge $e$ is accumulated in the head of $e$ (more precisely, in the variable $\delta[v]$). In order to avoid to count more than once each contribution, the contributions of the temporal edges in $E_{\text{node}}^{\text{dep}}[v]$ on the right of position $R[e]$ is subtracted to $\delta[v]$. Subsequently, the contributions of the temporal edges in $E_{\text{node}}^{\text{dep}}[v]$ from position $L[e]$ and position $R[e]$ which are not already included are added to $\delta[v]$: the new value of $\delta[v]$ can then be used to compute the temporal betweenness of $e$, according to Lemma 5.

The pseudo-code of the restless algorithm for the SFo betweenness is shown in Algorithm 3. It has to be observed that the actual code includes, in the backward phase, a control structure which allows us to deal with numerical approximation problems. This structure is not needed if big integer and big rational data structures are used, which, on the other hand, may slower the execution of the algorithm by a factor between two and four.

# 14 The general algorithm

In this section we show how Algorithm 3 can be generalised in order to deal with Fa, Fo, Sh and SFa walks. To this aim, we first introduce the notion of cost and target cost structures and we extend Facts 1 and 2 to these structures.

## 14.1 Walk cost and target cost structures

In order to generalise Algorithm 3 to other centrality measures, we integrate a temporal graph $G = (V, E, \beta)$ with an algebraic cost structure $(C, \gamma, \oplus, \leq)$, where $C$ is the set of possible cost
**Algorithm 3:** compute SFo $b_{s,e}$, for all $e \in E$

input : $G = (V, E, \beta)$ (represented by $E^{\text{dep}}$ and $E^{\text{arr}}$) and $s \in V$

output : s-SFO betweenness $b_{s,e}$, for all $e \in E$

1 Compute the lists $E_{\text{node}}^{\text{dep}}$ and $E_{\text{dep}}^{\text{arr}}$;

2 **foreach** $v \in V$ **do** $l[v] := 1$; $r[v] := 0$; $\mathcal{I}[v] := \emptyset$;

3 **foreach** $e \in E$ **do** $L[e] := |E^{\text{arr}}| + 1$; $R[e] := 0$; $C[e] := \infty$; $\Sigma[e] := 0$;

4 **foreach** $e = (u, v, \tau, \lambda) \in E^{\text{arr}}$ **do**

5 **if** $E_{\text{dep}}^{\text{arr}}[e] \ge l[u]$ **then** **Finalize**($u, E_{\text{dep}}^{\text{arr}}[e]$);

6 **if** $u = s$ **then** $C[e] := 1$; $\Sigma[e] := 1$;

7 **if** $C[e] \ne \infty$ **then**

8 $a := l[v]$; **while** $a \le |E_{\text{node}}^{\text{dep}}[v]| \land \text{dep}(E^{\text{arr}}[E_{\text{node}}^{\text{dep}}[v][a]]) < \tau + \lambda$ **do** $a := a + 1$;

9 $b := r[v]$; **while** $b < |E_{\text{node}}^{\text{dep}}[v]| \land \text{dep}(E^{\text{arr}}[E_{\text{node}}^{\text{dep}}[v][b+1]]) \le \tau + \lambda + \beta$ **do** $b := b + 1$;

10 **Finalize**($v, a-1$); $l_c := \max(a, r[v] + 1)$;

11 **while** $|\mathcal{I}[v]| > 0 \land C[e] \prec \text{last}(\mathcal{I}[v]) \cdot c$ **do** $Q := \text{poplast}(\mathcal{I}[v])$; $l_c := Q.l$; **foreach** $f \in Q.P$ **do** $R[f] := a-1$;

12 **if** $|\mathcal{I}[v]| > 0 \land \text{last}(\mathcal{I}[v]) \cdot c = C[e]$ **then** $Q := \text{last}(\mathcal{I}[v])$; $Q.r := b$; $Q.\eta := Q.\eta + \Sigma[e]$; $Q.P := Q.P \cup \{e\}$; $L[e] := Q.l$;

13 **else if** $l_c \le b$ **then** $L[e] := l_c$; **pushlast**($\mathcal{I}[v], (l_c, b, C[e], \{e\}, \Sigma[e])$);

14 $R[e] := b$; $r[v] := b$;

15 **foreach** $v \in V$ **do** $c^*[v] = [\infty, \infty]$; $\sigma^*[v] = 0$; $\delta[v] := 0$;

16 $c^*[s] := [0, 0]$; $\sigma^*[s] := 1$; **foreach** $e \in E$ **do** $\Sigma^*[e] := 0$; $b[e] := 0$;

17 **foreach** $e = (u, v, \tau, \lambda) \in E^{\text{arr}}$ **do if** $(C[e] < \infty \land (\text{arr}(e), C[e]) \triangleleft c^*[v])$ **then** $c^*[v] := (\text{arr}(e), C[e])$;

18 **foreach** $e = (u, v, \tau, \lambda) \in E^{\text{arr}}$ **do if** $(\text{arr}(e), C[e]) = c^*[v]$ **then** $\Sigma^*[e] := \Sigma[e]$; $\sigma^*[v] := \sigma^*[v] + \Sigma[e]$;

19 **foreach** $e = (u, v, \tau, \lambda) \in \text{reverse}(E^{\text{arr}})$ **do**

20 **if** $0 < L[e] \le R[e]$ **then**

21 **foreach** $f \in E_{\text{node}}^{\text{dep}}[v][\max(l[v], R[e] + 1) : r[v]]$ **do if** $v \ne s \lor C[f] = C[e] + 1$ **then** $\delta[v] := \delta[v] - b[f]/\Sigma[f]$;

22 $r[v] := R[e]$; **foreach** $f \in E_{\text{node}}^{\text{dep}}[v][L[e] : \min(R[e], l[v] - 1)]$ **do if** $v \ne s \lor C[f] = C[e] + 1$ **then** $\delta[v] := \delta[v] + b[f]/\Sigma[f]$;

23 $l[v] := L[e]$; $b[e] := \Sigma[e]\delta[v]$;

24 **if** $\Sigma^*[e] > 0$ **then** $b[e] := b[e] + \Sigma^*[e]/\sigma^*[v]$;

25 **return** $b$

26 **Finalize**($v, j$):

27 **while** $|\mathcal{I}[v]| > 0 \land \text{first}(\mathcal{I}[v]) \cdot l \le j$ **do**

28 $Q := \text{first}(\mathcal{I}[v])$; $ql := Q.l$; $q\eta := Q.\eta$;

29 **while** $|Q.P| > 0 \land R[\text{first}(Q.P)] \le j$ **do**

30 $e := \text{popfirst}(Q.P)$; **foreach** $f \in E_{\text{node}}^{\text{dep}}[v][ql : R[e]]$ **do** $C[f] := Q.c + 1$; $\Sigma[f] := q\eta$;

31 $q\eta := q\eta - \Sigma[e]$; $ql := R[e] + 1$; **foreach** $f \in E_{\text{node}}^{\text{dep}}[v][ql : \min(j, Q.r)]$ **do** $C[f] := Q.c + 1$; $\Sigma[f] := Q.\eta$;

32 **if** $j \ge Q.r$ **then** $\text{popfirst}(\mathcal{I}[v])$; **else** $Q.l := j + 1$; $Q.\eta = q\eta$; **break**;

33 $l[v] := j + 1$;

values, $\gamma$ is a cost function $\gamma: E \to C$, $\oplus$ is a cost combination function $\oplus: C \times C \to C$, and $\preceq$ is a cost total order with $\preceq \subseteq C \times C$. For any two elements $c_1$ and $c_2$ of $C$, we say that $c_1 = c_2$ if $c_1 \preceq c_2$ and $c_2 \preceq c_1$ both hold. We also define the relation $\prec$ between the elements of $C$ as $c_1 \prec c_2$ if and only if $c_1 \preceq c_2$ and $c_1 \ne c_2$. For any walk $W = \langle e_1, \dots, e_k \rangle$, the cost function of $W$ is recursively defined as follows: $\gamma(W) = \gamma(\langle e_1, \dots, e_{k-1} \rangle) \oplus \gamma(e_k)$, with $\gamma(\langle e_1 \rangle) = \gamma(e_1)$ (in other words, the costs combine along the walk according to the cost combination function). The cost structure is supposed to satisfy the following strict right-isotonicity property [8, 45, 46] (isotonicity for short): for any $c_1, c_2, c \in C$ such that $c_1 \prec c_2$, we have $c_1 \oplus c \prec c_2 \oplus c$. This property implies the following walk extension property: for any two walks $W$ and $X$ such that $\gamma(W) \prec \gamma(X)$ and for any temporal edge $e$ which can extend both $W$ and $X$, we have $\gamma(W.e) \prec \gamma(X.e)$ (that is,
<table><caption>Table 8: The 4 cost structures used in this paper</caption><thead><tr><th></th><th>C</th><th>γ(e)</th><th>c<sub>1</sub> ⊕ c<sub>2</sub></th><th>c<sub>1</sub> ≲ c<sub>2</sub></th></tr></thead><tbody><tr><td>All</td><td>{0}</td><td>0</td><td>0</td><td>true</td></tr><tr><td>Shortest</td><td>N</td><td>1</td><td>c<sub>1</sub> + c<sub>2</sub></td><td>c<sub>1</sub> ≤ c<sub>2</sub></td></tr><tr><td>Latest</td><td>Z</td><td>-dep(e)</td><td>c<sub>1</sub></td><td>c<sub>1</sub> ≤ c<sub>2</sub></td></tr><tr><td>Shortest latest</td><td>Z × N</td><td>(-dep(e), 1)</td><td>(c<sub>1</sub>[1], c<sub>1</sub>[2] + c<sub>2</sub>[2])</td><td>c<sub>1</sub>[1] &lt; c<sub>2</sub>[1] or (c<sub>1</sub>[1] = c<sub>2</sub>[1] and c<sub>1</sub>[2] ≤ c<sub>2</sub>[2])</td></tr></tbody></table>

<table><caption>Table 9: The 2 target cost structures along with the TC functions used in this paper</caption><thead><tr><th></th><th>C<sup>F</sup></th><th>c<sub>1</sub> ≲<sup>F</sup> c<sub>2</sub></th></tr></thead><tbody><tr><td>Natural</td><td>Z</td><td>c<sub>1</sub> ≤ c<sub>2</sub></td></tr><tr><td>Lexicographic</td><td>Z × N</td><td>c<sub>1</sub>[1] &lt; c<sub>2</sub>[1] or (c<sub>1</sub>[1] = c<sub>2</sub>[1] and c<sub>1</sub>[2] ≤ c<sub>2</sub>[2])</td></tr></tbody></table>

if several walks are extended by a given temporal edge $e$, then the best cost is obtained only by extending a walk with minimum cost). The isotonicity property also implies the following prefix property, which generalizes Fact 1 and is similar to the prefix-optimality property introduced in [38].

**Fact 9.** Let $G = (V, E, \beta)$ be a temporal graph and $(C, \gamma, \oplus, \preceq)$ be a cost structure satisfying the isotonicity property. For any node $s \in V$, if a walk $W$ with last temporal edge $f \in E$ has minimum cost among the sf-walks, and $e \in E$ is a temporal edge of $W$, then the prefix of $W$ up to the temporal edge $e$ has minimum cost among the se-walks.

*Proof.* Let $W_1$ be the prefix of $W$ up to the temporal edge $e$ and let us prove that $W_1$ has minimum cost among the se-walks. To this aim, let $\langle e_1 e_2 \cdots e_k \rangle$, with $e_k = f$ be the suffix $W_2$ of $W$ following the temporal edge $e$. Suppose that $W_1$ has not minimum cost and that there exists another se-walk such that $\gamma(X) \prec \gamma(W_1)$. By the isotonicity of $\Gamma$ it follows that $\gamma(X.e_1) \prec \gamma(W_1.e_1)$. By continuing in this way, we have that $\gamma(X.e_1.e_2.\cdots.e_k) \prec \gamma(W_1.e_1.e_2.\cdots.e_k) = \gamma(W)$, contradicting the fact that $W$ has minimum cost among the sf-walks. The fact thus follows. □

In this paper, we will consider the four cost structures shown in Table 8. It is easy to verify that all of them satisfy the isotonicity property. For example, let us prove that the shortest latest cost structure satisfies the isotonicity property. Suppose that $c_1, c_2 \in Z \times N$ satisfy $c_1 \prec c_2$: this implies that either $c_1[1] > c_2[1]$ or $c_1[1] = c_2[1] \land c_1[2] < c_2[2]$. For any $c \in Z \times N$, $c_1 \oplus c = (c_1[1], c_1[2] + c[2])$ and $c_2 \oplus c = (c_2[1], c_2[2] + c[2])$. If $c_1[1] > c_2[1]$, then $c_1 \oplus c \prec c_2 \oplus c$. Otherwise (that is, $c_1[1] = c_2[1]$ and $c_1[2] < c_2[2]$), $c_1[2] + c[2] < c_2[2] + c[2]$ and, thus, $c_1 \oplus c \prec c_2 \oplus c$.

Similar to the algorithms introduced in Section 4, the general algorithm consists of three phases. Given a temporal graph $G = (V, E, \beta)$ and a cost structure $(C, \gamma, \oplus, \preceq)$ among the ones in Table 8, in the first phase (that is, the forward phase), the algorithm counts, for any source node $s$ and for any temporal edge $e$, the number of se-walks which are optimal with respect to the walk cost function $\gamma$. In the other two phases (that is, the intermediate and the backward phase), the algorithm makes use of a target (or final) cost structure $(C^F, \preceq^F)$, where $C^F$ is the set of possible target cost values and $\preceq^F$ is a target cost total order with $\preceq^F \subseteq C^F \times C^F$. For any two elements $c_1$ and $c_2$ of $C^F$, we say that $c_1 =^F c_2$ if $c_1 \preceq^F c_2$ and $c_2 \preceq^F c_1$ both hold. We also define the relation $\prec^F$ between the elements of $C^F$ as $c_1 \prec^F c_2$ if and only if $c_1 \preceq^F c_2$ and $c_1 \neq^F c_2$.

Costs and target costs are related through a function $\text{TC}: E \times C \to C^F$ that associates to a temporal edge and a cost, a corresponding target cost. This function needs to satisfy the following increasing property: for any $c_1, c_2 \in C$ such that $c_1 \prec c_2$ and for any $e \in E$, we have that $\text{TC}(e, c_1) \prec^F \text{TC}(e, c_2)$. In this paper, we will consider the two target cost structures shown in Table 9, which together with a combination of one of the cost structures of Table 8 and an appropriate TC function will allow us to deal all optimality criteria. For example, Fa walks can be modeled by using the latest cost structure of Table 8 that associates to a walk the opposite of its departure time as a cost with later time being considered as lower cost: for that, it suffices to define the cost of a temporal edge as the opposite of its departure time and a combination
function $\oplus$ that returns its first argument. The duration of a walk $W$ with cost $c$ and ending with a temporal edge $e = (u, v, \tau, \lambda)$ is then obtained by using the natural target cost (see Table 9) and the target cost function $TC(e, c) = \text{arr}(e)+c$, since $\text{arr}(e) = \tau+\lambda$ equals $\text{arr}(W)$ and $c = -\text{dep}(W)$. As shown in Table 10, any of the walk optimality criteria defined in Section 3 can be modelled by an appropriate combination of the introduced cost structures, target cost structures, and target functions.

Given a cost structure $\Gamma = (C, \gamma, \oplus, \preceq)$ and a target cost structure $\Theta = (C^F, \preceq^F)$ along with a target cost function $TC$, we say that a temporal st-walk $W$ is $\Theta$-optimal if, for any st-walk $X$, we have $TC(e, \gamma(W)) \preceq^F TC(f, \gamma(X))$, where $e$ and $f$ are the last temporal edge of $W$ and $X$, respectively. We also say that a temporal se-walk $W$ is $\Gamma$-optimal if, for any se-walk $X$, we have $\gamma(W) \preceq^F \gamma(X)$. Note that a $\Gamma$-optimal se-walk $X$ not necessarily is a $\Theta$-optimal st-walk where $t$ is the head of $e$. The opposite, instead, is true as shown by the following which is a generalization of Fact 2.

**Fact 10.** Given a temporal graph $G = (V, E, \beta)$, a cost structure $(C, \gamma, \oplus, \preceq)$, a target cost structure $(C^F, \preceq^F)$, and a $TC$ function, let $W$ be a $\Theta$-optimal st-walk (for some $s, t \in V$) and let $e$ be the last temporal edge of $W$. Then, $W$ is a $\Gamma$-optimal se-walk.

*Proof.* Suppose that $W$ is not $\Gamma$-optimal and that there exists another se-walk $X$ (and, hence, st-walk) such that $\gamma(X) \prec \gamma(W)$. By the increasing property of the $TC$ function it follows that $TC(e, \gamma(X)) \prec^F TC(e, \gamma(W))$, contradicting the fact that $W$ is a $\Theta$-optimal st-walk. The fact thus follows. $\square$

<table><caption>Table 10: Optimality criteria in terms of cost and target cost structures. In the last column of the table, the semantic of $c$ is the following: number of hops for Sh and for SFo, the opposite of the departure time for latest and for Fa the array whose first entry is the opposite of the departure time and whose second entry is the number of hops for shortest latest and SFa.</caption><thead><tr><th>Optimality criterion</th><th>Cost</th><th>Target cost</th><th>TC(e, c)</th></tr></thead><tbody><tr><td>Shortest</td><td>Shortest</td><td>Natural</td><td>c</td></tr><tr><td>Foremost</td><td>All</td><td>Natural</td><td>arr(e)</td></tr><tr><td>Latest</td><td>Latest</td><td>Natural</td><td>c</td></tr><tr><td>Fastest</td><td>Latest</td><td>Natural</td><td>arr(e) + c</td></tr><tr><td>Shortest foremost</td><td>Shortest</td><td>Lexicographic</td><td>(arr(e), c)</td></tr><tr><td>Shortest latest</td><td>Shortest latest</td><td>Lexicographic</td><td>c</td></tr><tr><td>Shortest fastest</td><td>Shortest latest</td><td>Lexicographic</td><td>(arr(e) + c[1], c[2])</td></tr></tbody></table>

Moreover, all the definitions concerning the Sh and the SFo betweenness can be appropriately adapted to the any other optimality criterion case and all the results proved for the SFo betweenness can be proved also for the corresponding betweenness.

## 14.2 The general algorithm

The pseudo-code of the general algorithm for any of optimality criteria which fits in our framework is shown in Algorithm 4. Note that the pseudo-code uses the symbol $\infty^\Gamma$ and $\infty^\Theta$ to denote the natural infinite value of a cost structure $\Gamma$ and a target cost structure $\Theta$. The pseudo-code also uses the symbol $0^\Theta$ to denote the natural minimum value of a target cost structure $\Theta$. Moreover, note the strong similarity of the pseudo-code with Algorithm 3: indeed, the two pseudo-codes are almost the same apart from the use in Algorithm 4 of the components of the cost and target cost structures. Even in this case, we do not include the control structure for dealing with numerical approximation problems, which is not needed if big integer and big rational data structures are used.
<caption>**Algorithm 4:** compute $b_{s,e}$ of all temporal edges</caption>

**input** : temporal graph $G = (V, E, \beta)$ (represented by $E^{\text{dep}}$ and $E^{\text{arr}}$), $s \in V$, cost structure $\Gamma = (C, \gamma, \oplus, \preceq)$, target cost structure $\Theta = (C^F, \preceq^F)$, and target cost function TC
**output** : s-temporal betweenness $b_{s,e}$ of each $e \in E$ w.r.t. $\Gamma, \Theta$, and TC
1 Compute the lists $E_{\text{node}}^{\text{dep}}$ and $E_{\text{dep}}^{\text{arr}}$;
2 **foreach** $v \in V$ **do** $l[v] := 1$; $r[v] := 0$; $\mathcal{I}[v] := \emptyset$;
3 **foreach** $e \in E$ **do** $L[e] := |E^{\text{arr}}| + 1$; $R[e] := 0$; $C[e] := \infty^{\Gamma}$; $\Sigma[e] := 0$;
4 **foreach** $e = (u, v, \tau, \lambda) \in E^{\text{arr}}$ **do**
5 if $E_{\text{dep}}^{\text{arr}}[e] \ge l[u]$ **then** **Finalize**($u, E_{\text{dep}}^{\text{arr}}[e]$);
6 if $u = s$ **then** if $\gamma(e) \prec C[e]$ **then** $C[e] := \gamma(e)$; $\Sigma[e] := 1$; **else if** $\gamma(e) = C[e]$ **then**
$\Sigma[e] := \Sigma[e] + 1$;
7 if $C[e] \ne \infty^{\Gamma}$ **then**
8 $a := l[v]$; **while** $a \le |E_{\text{node}}^{\text{dep}}[v]| \wedge \text{dep}(E^{\text{arr}}[E_{\text{node}}^{\text{dep}}[v][a]]) < \tau + \lambda$ **do** $a := a + 1$;
9 $b := r[v]$; **while** $b < |E_{\text{node}}^{\text{dep}}[v]| \wedge \text{dep}(E^{\text{arr}}[E_{\text{node}}^{\text{dep}}[v][b + 1]]) \le \tau + \lambda + \beta$ **do** $b := b + 1$;
10 **Finalize**($v, a - 1$); $l_c := \max(a, r[v] + 1)$;
11 **while** $|\mathcal{I}[v]| > 0 \wedge C[e] \prec \text{last}(\mathcal{I}[v]) \cdot c$ **do** $Q := \text{poplast}(\mathcal{I}[v])$; $l_c := Q.l$; **foreach** $f \in Q.P$ **do**
$R[f] := a - 1$;
12 if $|\mathcal{I}[v]| > 0 \wedge \text{last}(\mathcal{I}[v]) \cdot c = C[e]$ **then** $Q := \text{last}(\mathcal{I}[v])$; $Q.r := b$; $Q.\eta := Q.\eta + \Sigma[e]$;
$Q.P := Q.P \cup \{e\}$; $L[e] := Q.l$;
13 **else if** $l_c \le b$ **then** $L[e] := l_c$; $\text{pushlast}(\mathcal{I}[v], (l_c, b, C[e], \{e\}, \Sigma[e]))$;
14 $R[e] := b$; $r[v] := b$;
15 **foreach** $v \in V$ **do** $c^*[v] = \infty^{\Theta}$; $\sigma^*[v] = 0$; $\delta[v] := 0$;
16 $c^*[s] := 0^{\Theta}$; $\sigma^*[s] := 1$; **foreach** $e \in E$ **do** $\Sigma^*[e] := 0$; $b[e] := 0$;
17 **foreach** $e = (u, v, \tau, \lambda) \in E^{\text{arr}}$ **do if** $(C[e] < \infty \wedge \text{TC}(e, C[e]) \prec^F c^*[v])$ **then** $c^*[v] := \text{TC}(e, C[e])$;
18 **foreach** $e = (u, v, \tau, \lambda) \in E^{\text{arr}}$ **do if** $\text{TC}(e, C[e]) =^F c^*[v]$ **then** $\Sigma^*[e] := \Sigma[e]$; $\sigma^*[v] := \sigma^*[v] + \Sigma[e]$;
19 **foreach** $e = (u, v, \tau, \lambda) \in \text{reverse}(E^{\text{arr}})$ **do**
20 if $0 < L[e] \le R[e]$ **then**
21 **foreach** $f \in E_{\text{node}}^{\text{dep}}[v][\max(l[v], R[e] + 1) : r[v]]$ **do if** $v \ne s \vee C[f] = C[e] \oplus \gamma(f)$ **then**
$\delta[v] := \delta[v] - b[f]/\Sigma[f]$;
22 $r[v] := R[e]$; **foreach** $f \in E_{\text{node}}^{\text{dep}}[v][L[e] : \min(R[e], l[v] - 1)]$ **do if** $v \ne s \vee C[f] = C[e] \oplus \gamma(f)$
**then** $\delta[v] := \delta[v] + b[f]/\Sigma[f]$;
23 $l[v] := L[e]$; $b[e] := \Sigma[e]\delta[v]$;
24 if $\Sigma^*[e] > 0$ **then** $b[e] := b[e] + \Sigma^*[e]/\sigma^*[v]$;
25 **return** $b$
26 **Finalize**($v, j$):
27 **while** $|\mathcal{I}[v]| > 0 \wedge \text{first}(\mathcal{I}[v]) \cdot l \le j$ **do**
28 $Q := \text{first}(\mathcal{I}[v])$; $ql := Q.l$; $q\eta := Q.\eta$;
29 **while** $|Q.P| > 0 \wedge \text{first}(Q.P)| \le j$ **do**
30 $e := \text{popfirst}(Q.P)$; **foreach** $f \in E_{\text{node}}^{\text{dep}}[v][ql : R[e]]$ **do** $C[f] := Q.c \oplus \gamma(f)$; $\Sigma[f] := q\eta$;
31 $q\eta := Q.\eta - \Sigma[e]$; $ql := R[e] + 1$; **foreach** $f \in E_{\text{node}}^{\text{dep}}[v][ql : \min(j, Q.r)]$ **do**
$C[f] := Q.c \oplus \gamma(f)$; $\Sigma[f] := q\eta$;
32 if $j \ge Q.r$ **then** $\text{popfirst}(\mathcal{I}[v])$; **else** $Q.l := j + 1$; $Q.\eta := q\eta$; **break**;
33 $l[v] := j + 1$;
## 15 Comparing SFo BMNR and Fast times

<table><thead><tr><th>Temporal graph</th><th>t<sub>BMNR</sub></th><th>t<sub>FAST</sub></th><th>t<sub>BMNR</sub>/t<sub>FAST</sub></th></tr></thead><tbody><tr><td>Infectious</td><td>3158.12</td><td>1595.56</td><td>1.98</td></tr><tr><td>Digg reply</td><td>1201.86</td><td>507.74</td><td>2.37</td></tr><tr><td>Facebook wall</td><td>3402.02</td><td>1354.76</td><td>2.51</td></tr><tr><td>Slashdot reply</td><td>4518.64</td><td>1730.93</td><td>2.61</td></tr><tr><td>SMS</td><td>12501.27</td><td>4773.57</td><td>2.62</td></tr><tr><td>Wiki elections</td><td>526.94</td><td>125.10</td><td>4.21</td></tr><tr><td>College msg</td><td>246.30</td><td>27.95</td><td>8.81</td></tr><tr><td>Topology</td><td>8926.13</td><td>930.49</td><td>9.59</td></tr><tr><td>Hypertext 2009</td><td>85.17</td><td>1.09</td><td>78.42</td></tr><tr><td>High school 2011</td><td>134.05</td><td>1.63</td><td>82.34</td></tr><tr><td>High school 2012</td><td>402.18</td><td>3.71</td><td>108.54</td></tr><tr><td>Primary school</td><td>1938.72</td><td>17.29</td><td>112.16</td></tr><tr><td>Email EU</td><td>12233.57</td><td>91.78</td><td>133.30</td></tr><tr><td>Hospital ward</td><td>204.56</td><td>1.14</td><td>178.88</td></tr><tr><td>High school 2013</td><td>7329.39</td><td>38.94</td><td>188.21</td></tr></tbody></table>

## 16 Ranking correlations

In the Tables 11-20, we show the different correlations (that is, Kendall, weighted Kendall, and intersection correlation) between the rankings produced by the execution of our algorithm (that is, Algorithm 4) on the networks of the first dataset, for different optimality criteria (that is, fastest, foremost, shortest, shortest fastest, and shortest foremost) and for different values of $\beta$ (that is, $\beta = 300, 600, 1200, 2400, \infty$). In the Tables 21-25, we show the same correlations between the rankings produced by the execution of the algorithm on the public transport networks, for different values of $\beta$ and for different pairs of optimality criteria.
<table><caption>Table 11: Fastest walks and Kendall, weighted Kendall, and intersection correlation</caption><thead><tr><th rowspan="3">Network</th><th colspan="6">Kendall's τ</th></tr><tr><th colspan="3">300</th><th colspan="3">600</th><th>1200</th></tr><tr><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.87</td><td>0.86</td><td>0.80</td><td>0.88</td><td>0.81</td><td>0.89</td></tr><tr><td>Hospital ward</td><td>0.88</td><td>0.88</td><td>0.84</td><td>0.97</td><td>0.89</td><td>0.90</td></tr><tr><td>Highschool 2011</td><td>0.87</td><td>0.72</td><td>0.71</td><td>0.75</td><td>0.72</td><td>0.87</td></tr><tr><td>Highschool 2012</td><td>0.77</td><td>0.69</td><td>0.70</td><td>0.80</td><td>0.74</td><td>0.80</td></tr><tr><td>Primary school</td><td>0.92</td><td>0.89</td><td>0.89</td><td>0.96</td><td>0.96</td><td>1.00</td></tr><tr><td>College msg</td><td>0.90</td><td>0.83</td><td>0.79</td><td>0.90</td><td>0.86</td><td>0.93</td></tr><tr><td>Highschool 2013</td><td>0.87</td><td>0.79</td><td>0.79</td><td>0.88</td><td>0.87</td><td>0.93</td></tr><tr><td>Email EU</td><td>0.88</td><td>0.79</td><td>0.74</td><td>0.87</td><td>0.81</td><td>0.89</td></tr><tr><td>Wiki elections</td><td>0.79</td><td>0.62</td><td>0.51</td><td>0.79</td><td>0.64</td><td>0.81</td></tr><tr><td>Digg reply</td><td>0.82</td><td>0.71</td><td>0.61</td><td>0.86</td><td>0.75</td><td>0.86</td></tr><tr><td>Facebook wall</td><td>0.78</td><td>0.63</td><td>0.52</td><td>0.81</td><td>0.67</td><td>0.82</td></tr><tr><td>Infectious</td><td>0.84</td><td>0.80</td><td>0.77</td><td>0.92</td><td>0.88</td><td>0.94</td></tr><tr><td>Slashdot reply</td><td>0.86</td><td>0.74</td><td>0.65</td><td>0.86</td><td>0.76</td><td>0.87</td></tr><tr><td>SMS</td><td>0.85</td><td>0.77</td><td>0.70</td><td>0.90</td><td>0.82</td><td>0.91</td></tr></tbody><thead><tr><th rowspan="3">Network</th><th colspan="6">Weighted Kendall's τ</th></tr><tr><th colspan="3">300</th><th colspan="3">600</th><th>1200</th></tr><tr><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.91</td><td>0.90</td><td>0.86</td><td>0.92</td><td>0.85</td><td>0.91</td></tr><tr><td>Hospital ward</td><td>0.94</td><td>0.94</td><td>0.92</td><td>0.99</td><td>0.95</td><td>0.96</td></tr><tr><td>Highschool 2011</td><td>0.86</td><td>0.78</td><td>0.81</td><td>0.84</td><td>0.78</td><td>0.90</td></tr><tr><td>Highschool 2012</td><td>0.84</td><td>0.79</td><td>0.81</td><td>0.88</td><td>0.85</td><td>0.89</td></tr><tr><td>Primary school</td><td>0.96</td><td>0.94</td><td>0.94</td><td>0.98</td><td>0.98</td><td>1.00</td></tr><tr><td>College msg</td><td>0.96</td><td>0.93</td><td>0.92</td><td>0.95</td><td>0.94</td><td>0.97</td></tr><tr><td>Highschool 2013</td><td>0.92</td><td>0.87</td><td>0.86</td><td>0.94</td><td>0.92</td><td>0.96</td></tr><tr><td>Email EU</td><td>0.95</td><td>0.93</td><td>0.91</td><td>0.95</td><td>0.93</td><td>0.96</td></tr><tr><td>Wiki elections</td><td>0.94</td><td>0.87</td><td>0.81</td><td>0.95</td><td>0.89</td><td>0.95</td></tr><tr><td>Digg reply</td><td>0.96</td><td>0.93</td><td>0.90</td><td>0.97</td><td>0.94</td><td>0.97</td></tr><tr><td>Facebook wall</td><td>0.95</td><td>0.91</td><td>0.88</td><td>0.96</td><td>0.92</td><td>0.96</td></tr><tr><td>Infectious</td><td>0.93</td><td>0.91</td><td>0.90</td><td>0.97</td><td>0.96</td><td>0.98</td></tr><tr><td>Slashdot reply</td><td>0.97</td><td>0.95</td><td>0.92</td><td>0.98</td><td>0.95</td><td>0.97</td></tr><tr><td>SMS</td><td>0.97</td><td>0.95</td><td>0.93</td><td>0.98</td><td>0.96</td><td>0.98</td></tr></tbody><thead><tr><th rowspan="3">Network</th><th colspan="6">Intersection top-50</th></tr><tr><th colspan="3">300</th><th colspan="3">600</th><th>1200</th></tr><tr><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>46</td><td>45</td><td>44</td><td>47</td><td>46</td><td>46</td></tr><tr><td>Hospital ward</td><td>47</td><td>47</td><td>46</td><td>49</td><td>47</td><td>47</td></tr><tr><td>Highschool 2011</td><td>47</td><td>42</td><td>41</td><td>42</td><td>42</td><td>46</td></tr><tr><td>Highschool 2012</td><td>42</td><td>39</td><td>39</td><td>43</td><td>39</td><td>42</td></tr><tr><td>Primary school</td><td>46</td><td>45</td><td>45</td><td>48</td><td>48</td><td>50</td></tr><tr><td>College msg</td><td>38</td><td>32</td><td>33</td><td>36</td><td>36</td><td>40</td></tr><tr><td>Highschool 2013</td><td>39</td><td>34</td><td>29</td><td>44</td><td>39</td><td>45</td></tr><tr><td>Email EU</td><td>46</td><td>42</td><td>42</td><td>45</td><td>45</td><td>45</td></tr><tr><td>Wiki elections</td><td>29</td><td>22</td><td>18</td><td>30</td><td>26</td><td>29</td></tr><tr><td>Digg reply</td><td>31</td><td>23</td><td>20</td><td>33</td><td>31</td><td>36</td></tr><tr><td>Facebook wall</td><td>36</td><td>32</td><td>29</td><td>38</td><td>33</td><td>38</td></tr><tr><td>Infectious</td><td>32</td><td>29</td><td>29</td><td>43</td><td>41</td><td>48</td></tr><tr><td>Slashdot reply</td><td>39</td><td>39</td><td>30</td><td>43</td><td>34</td><td>36</td></tr><tr><td>SMS</td><td>42</td><td>36</td><td>35</td><td>39</td><td>37</td><td>43</td></tr></tbody></table>
<table><caption>Table 12: Foremost walks and Kendall, weighted Kendall, and intersection correlation</caption><thead><tr><th rowspan="3">Network</th><th colspan="6">Kendall's τ</th></tr><tr><th colspan="3">300</th><th colspan="3">600</th><th>1200</th></tr><tr><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.77</td><td>0.74</td><td>0.72</td><td>0.84</td><td>0.82</td><td>0.91</td></tr><tr><td>Hospital ward</td><td>0.92</td><td>0.87</td><td>0.82</td><td>0.93</td><td>0.87</td><td>0.91</td></tr><tr><td>Highschool 2011</td><td>0.85</td><td>0.65</td><td>0.64</td><td>0.68</td><td>0.66</td><td>0.92</td></tr><tr><td>Highschool 2012</td><td>0.78</td><td>0.71</td><td>0.71</td><td>0.80</td><td>0.72</td><td>0.77</td></tr><tr><td>Primary school</td><td>0.86</td><td>0.86</td><td>0.86</td><td>0.92</td><td>0.92</td><td>1.00</td></tr><tr><td>College msg</td><td>0.90</td><td>0.84</td><td>0.80</td><td>0.91</td><td>0.87</td><td>0.93</td></tr><tr><td>Highschool 2013</td><td>0.85</td><td>0.81</td><td>0.77</td><td>0.89</td><td>0.85</td><td>0.89</td></tr><tr><td>Email EU</td><td>0.87</td><td>0.78</td><td>0.74</td><td>0.86</td><td>0.81</td><td>0.89</td></tr><tr><td>Wiki elections</td><td>0.82</td><td>0.66</td><td>0.53</td><td>0.80</td><td>0.65</td><td>0.81</td></tr><tr><td>Digg reply</td><td>0.82</td><td>0.71</td><td>0.61</td><td>0.86</td><td>0.75</td><td>0.87</td></tr><tr><td>Facebook wall</td><td>0.77</td><td>0.62</td><td>0.51</td><td>0.81</td><td>0.66</td><td>0.82</td></tr><tr><td>Infectious</td><td>0.85</td><td>0.81</td><td>0.79</td><td>0.93</td><td>0.89</td><td>0.94</td></tr><tr><td>Slashdot reply</td><td>0.85</td><td>0.73</td><td>0.64</td><td>0.86</td><td>0.75</td><td>0.87</td></tr><tr><td>SMS</td><td>0.84</td><td>0.75</td><td>0.69</td><td>0.90</td><td>0.82</td><td>0.91</td></tr></tbody></table><table><thead><tr><th rowspan="3">Network</th><th colspan="6">Weighted Kendall's τ</th></tr><tr><th colspan="3">300</th><th colspan="3">600</th><th>1200</th></tr><tr><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.83</td><td>0.84</td><td>0.83</td><td>0.91</td><td>0.90</td><td>0.95</td></tr><tr><td>Hospital ward</td><td>0.96</td><td>0.94</td><td>0.91</td><td>0.97</td><td>0.93</td><td>0.96</td></tr><tr><td>Highschool 2011</td><td>0.90</td><td>0.65</td><td>0.61</td><td>0.66</td><td>0.62</td><td>0.96</td></tr><tr><td>Highschool 2012</td><td>0.86</td><td>0.82</td><td>0.83</td><td>0.89</td><td>0.82</td><td>0.86</td></tr><tr><td>Primary school</td><td>0.94</td><td>0.91</td><td>0.91</td><td>0.95</td><td>0.95</td><td>1.00</td></tr><tr><td>College msg</td><td>0.96</td><td>0.94</td><td>0.92</td><td>0.95</td><td>0.94</td><td>0.97</td></tr><tr><td>Highschool 2013</td><td>0.93</td><td>0.92</td><td>0.90</td><td>0.96</td><td>0.94</td><td>0.96</td></tr><tr><td>Email EU</td><td>0.95</td><td>0.92</td><td>0.91</td><td>0.95</td><td>0.93</td><td>0.96</td></tr><tr><td>Wiki elections</td><td>0.95</td><td>0.89</td><td>0.82</td><td>0.95</td><td>0.90</td><td>0.95</td></tr><tr><td>Digg reply</td><td>0.96</td><td>0.93</td><td>0.90</td><td>0.97</td><td>0.94</td><td>0.97</td></tr><tr><td>Facebook wall</td><td>0.95</td><td>0.91</td><td>0.88</td><td>0.96</td><td>0.92</td><td>0.96</td></tr><tr><td>Infectious</td><td>0.94</td><td>0.93</td><td>0.92</td><td>0.98</td><td>0.96</td><td>0.98</td></tr><tr><td>Slashdot reply</td><td>0.97</td><td>0.95</td><td>0.92</td><td>0.97</td><td>0.95</td><td>0.97</td></tr><tr><td>SMS</td><td>0.96</td><td>0.94</td><td>0.93</td><td>0.98</td><td>0.96</td><td>0.98</td></tr></tbody></table><table><thead><tr><th rowspan="3">Network</th><th colspan="6">Intersection top-50</th></tr><tr><th colspan="3">300</th><th colspan="3">600</th><th>1200</th></tr><tr><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>44</td><td>43</td><td>42</td><td>44</td><td>43</td><td>47</td></tr><tr><td>Hospital ward</td><td>49</td><td>49</td><td>47</td><td>49</td><td>46</td><td>46</td></tr><tr><td>Highschool 2011</td><td>46</td><td>38</td><td>38</td><td>39</td><td>37</td><td>48</td></tr><tr><td>Highschool 2012</td><td>40</td><td>37</td><td>36</td><td>41</td><td>41</td><td>40</td></tr><tr><td>Primary school</td><td>48</td><td>45</td><td>46</td><td>47</td><td>48</td><td>49</td></tr><tr><td>College msg</td><td>40</td><td>31</td><td>30</td><td>34</td><td>31</td><td>44</td></tr><tr><td>Highschool 2013</td><td>42</td><td>40</td><td>40</td><td>46</td><td>45</td><td>47</td></tr><tr><td>Email EU</td><td>45</td><td>42</td><td>43</td><td>45</td><td>44</td><td>43</td></tr><tr><td>Wiki elections</td><td>33</td><td>24</td><td>23</td><td>33</td><td>29</td><td>37</td></tr><tr><td>Digg reply</td><td>31</td><td>23</td><td>20</td><td>33</td><td>31</td><td>36</td></tr><tr><td>Facebook wall</td><td>38</td><td>32</td><td>28</td><td>39</td><td>31</td><td>38</td></tr><tr><td>Infectious</td><td>37</td><td>35</td><td>33</td><td>47</td><td>44</td><td>47</td></tr><tr><td>Slashdot reply</td><td>40</td><td>38</td><td>31</td><td>40</td><td>32</td><td>36</td></tr><tr><td>SMS</td><td>39</td><td>32</td><td>33</td><td>39</td><td>37</td><td>46</td></tr></tbody></table>
<table><thead><tr><th rowspan="3">Network</th><th colspan="10">Kendall's τ</th></tr><tr><th colspan="4">∞</th><th colspan="4">300</th><th colspan="3">600</th><th colspan="3">1200</th></tr><tr><th>300</th><th>600</th><th>1200</th><th>2400</th><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.68</td><td>0.71</td><td>0.75</td><td>0.75</td><td>0.84</td><td>0.78</td><td>0.74</td><td>0.82</td><td>0.78</td><td>0.88</td><td>0.82</td><td>0.78</td><td>0.88</td></tr><tr><td>Hospital ward</td><td>0.75</td><td>0.71</td><td>0.70</td><td>0.69</td><td>0.76</td><td>0.72</td><td>0.69</td><td>0.82</td><td>0.76</td><td>0.80</td><td>0.82</td><td>0.76</td><td>0.80</td></tr><tr><td>Highschool 2011</td><td>0.65</td><td>0.67</td><td>0.70</td><td>0.74</td><td>0.83</td><td>0.76</td><td>0.76</td><td>0.78</td><td>0.78</td><td>0.87</td><td>0.82</td><td>0.78</td><td>0.87</td></tr><tr><td>Highschool 2012</td><td>0.57</td><td>0.56</td><td>0.53</td><td>0.57</td><td>0.76</td><td>0.67</td><td>0.70</td><td>0.75</td><td>0.71</td><td>0.72</td><td>0.82</td><td>0.75</td><td>0.82</td></tr><tr><td>Primary school</td><td>0.68</td><td>0.70</td><td>0.72</td><td>0.77</td><td>0.85</td><td>0.81</td><td>0.78</td><td>0.88</td><td>0.84</td><td>0.90</td><td>0.82</td><td>0.88</td><td>0.88</td></tr><tr><td>College msg</td><td>0.58</td><td>0.61</td><td>0.64</td><td>0.66</td><td>0.90</td><td>0.83</td><td>0.80</td><td>0.89</td><td>0.86</td><td>0.92</td><td>0.82</td><td>0.86</td><td>0.88</td></tr><tr><td>Highschool 2013</td><td>0.59</td><td>0.66</td><td>0.70</td><td>0.72</td><td>0.81</td><td>0.73</td><td>0.70</td><td>0.86</td><td>0.82</td><td>0.89</td><td>0.82</td><td>0.86</td><td>0.88</td></tr><tr><td>Email EU</td><td>0.58</td><td>0.62</td><td>0.67</td><td>0.68</td><td>0.87</td><td>0.78</td><td>0.73</td><td>0.86</td><td>0.80</td><td>0.88</td><td>0.82</td><td>0.88</td><td>0.88</td></tr><tr><td>Wiki elections</td><td>0.18</td><td>0.22</td><td>0.28</td><td>0.34</td><td>0.79</td><td>0.63</td><td>0.51</td><td>0.78</td><td>0.64</td><td>0.81</td><td>0.82</td><td>0.78</td><td>0.81</td></tr><tr><td>Digg reply</td><td>0.25</td><td>0.30</td><td>0.34</td><td>0.40</td><td>0.82</td><td>0.71</td><td>0.61</td><td>0.86</td><td>0.74</td><td>0.86</td><td>0.82</td><td>0.74</td><td>0.86</td></tr><tr><td>Facebook wall</td><td>0.19</td><td>0.23</td><td>0.28</td><td>0.33</td><td>0.78</td><td>0.63</td><td>0.52</td><td>0.80</td><td>0.67</td><td>0.82</td><td>0.82</td><td>0.67</td><td>0.82</td></tr><tr><td>Infectious</td><td>0.57</td><td>0.65</td><td>0.73</td><td>0.84</td><td>0.74</td><td>0.66</td><td>0.61</td><td>0.78</td><td>0.71</td><td>0.81</td><td>0.82</td><td>0.78</td><td>0.81</td></tr><tr><td>Slashdot reply</td><td>0.32</td><td>0.37</td><td>0.42</td><td>0.48</td><td>0.86</td><td>0.74</td><td>0.65</td><td>0.86</td><td>0.76</td><td>0.87</td><td>0.82</td><td>0.86</td><td>0.87</td></tr><tr><td>SMS</td><td>0.26</td><td>0.30</td><td>0.33</td><td>0.36</td><td>0.85</td><td>0.76</td><td>0.70</td><td>0.89</td><td>0.82</td><td>0.91</td><td>0.82</td><td>0.89</td><td>0.91</td></tr></tbody></table>

<table><thead><tr><th rowspan="3">Network</th><th colspan="10">Weighted Kendall's τ</th></tr><tr><th colspan="4">∞</th><th colspan="4">300</th><th colspan="3">600</th><th colspan="3">1200</th></tr><tr><th>300</th><th>600</th><th>1200</th><th>2400</th><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.83</td><td>0.84</td><td>0.87</td><td>0.86</td><td>0.90</td><td>0.88</td><td>0.86</td><td>0.91</td><td>0.88</td><td>0.94</td><td>0.82</td><td>0.86</td><td>0.91</td></tr><tr><td>Hospital ward</td><td>0.83</td><td>0.76</td><td>0.79</td><td>0.85</td><td>0.87</td><td>0.85</td><td>0.83</td><td>0.90</td><td>0.82</td><td>0.86</td><td>0.82</td><td>0.82</td><td>0.91</td></tr><tr><td>Highschool 2011</td><td>0.73</td><td>0.65</td><td>0.77</td><td>0.80</td><td>0.84</td><td>0.82</td><td>0.82</td><td>0.83</td><td>0.82</td><td>0.91</td><td>0.82</td><td>0.82</td><td>0.91</td></tr><tr><td>Highschool 2012</td><td>0.66</td><td>0.65</td><td>0.64</td><td>0.70</td><td>0.85</td><td>0.78</td><td>0.80</td><td>0.85</td><td>0.81</td><td>0.82</td><td>0.82</td><td>0.81</td><td>0.82</td></tr><tr><td>Primary school</td><td>0.79</td><td>0.81</td><td>0.83</td><td>0.86</td><td>0.92</td><td>0.89</td><td>0.88</td><td>0.94</td><td>0.92</td><td>0.95</td><td>0.95</td><td>0.92</td><td>0.95</td></tr><tr><td>College msg</td><td>0.84</td><td>0.83</td><td>0.83</td><td>0.84</td><td>0.96</td><td>0.93</td><td>0.92</td><td>0.95</td><td>0.94</td><td>0.96</td><td>0.95</td><td>0.94</td><td>0.96</td></tr><tr><td>Highschool 2013</td><td>0.73</td><td>0.82</td><td>0.86</td><td>0.87</td><td>0.89</td><td>0.83</td><td>0.81</td><td>0.93</td><td>0.91</td><td>0.95</td><td>0.93</td><td>0.91</td><td>0.95</td></tr><tr><td>Email EU</td><td>0.83</td><td>0.85</td><td>0.86</td><td>0.86</td><td>0.95</td><td>0.92</td><td>0.91</td><td>0.95</td><td>0.93</td><td>0.96</td><td>0.95</td><td>0.93</td><td>0.96</td></tr><tr><td>Wiki elections</td><td>0.63</td><td>0.67</td><td>0.72</td><td>0.76</td><td>0.94</td><td>0.87</td><td>0.81</td><td>0.94</td><td>0.89</td><td>0.95</td><td>0.95</td><td>0.94</td><td>0.95</td></tr><tr><td>Digg reply</td><td>0.75</td><td>0.79</td><td>0.81</td><td>0.83</td><td>0.96</td><td>0.93</td><td>0.90</td><td>0.97</td><td>0.94</td><td>0.97</td><td>0.97</td><td>0.94</td><td>0.97</td></tr><tr><td>Facebook wall</td><td>0.72</td><td>0.75</td><td>0.78</td><td>0.81</td><td>0.95</td><td>0.91</td><td>0.88</td><td>0.96</td><td>0.92</td><td>0.96</td><td>0.96</td><td>0.92</td><td>0.96</td></tr><tr><td>Infectious</td><td>0.72</td><td>0.78</td><td>0.84</td><td>0.91</td><td>0.85</td><td>0.80</td><td>0.75</td><td>0.90</td><td>0.84</td><td>0.90</td><td>0.90</td><td>0.84</td><td>0.90</td></tr><tr><td>Slashdot reply</td><td>0.82</td><td>0.84</td><td>0.86</td><td>0.88</td><td>0.97</td><td>0.95</td><td>0.92</td><td>0.98</td><td>0.95</td><td>0.97</td><td>0.98</td><td>0.95</td><td>0.97</td></tr><tr><td>SMS</td><td>0.79</td><td>0.81</td><td>0.83</td><td>0.84</td><td>0.97</td><td>0.95</td><td>0.93</td><td>0.98</td><td>0.96</td><td>0.98</td><td>0.98</td><td>0.96</td><td>0.98</td></tr></tbody></table>

<table><caption>Table 13: Shortest walks and Kendall, weighted Kendall, and intersection correlation</caption><thead><tr><th rowspan="3">Network</th><th colspan="10">Intersection top-50</th></tr><tr><th colspan="4">∞</th><th colspan="4">300</th><th colspan="3">600</th><th colspan="3">1200</th></tr><tr><th>300</th><th>600</th><th>1200</th><th>2400</th><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>39</td><td>40</td><td>42</td><td>40</td><td>46</td><td>41</td><td>40</td><td>43</td><td>42</td><td>45</td><td>45</td><td>46</td><td>46</td></tr><tr><td>Hospital ward</td><td>47</td><td>45</td><td>44</td><td>42</td><td>44</td><td>43</td><td>43</td><td>46</td><td>45</td><td>45</td><td>45</td><td>46</td><td>46</td></tr><tr><td>Highschool 2011</td><td>41</td><td>42</td><td>44</td><td>44</td><td>48</td><td>44</td><td>44</td><td>45</td><td>45</td><td>45</td><td>45</td><td>47</td><td>47</td></tr><tr><td>Highschool 2012</td><td>35</td><td>32</td><td>31</td><td>34</td><td>40</td><td>39</td><td>40</td><td>42</td><td>43</td><td>40</td><td>42</td><td>40</td><td>40</td></tr><tr><td>Primary school</td><td>36</td><td>37</td><td>39</td><td>42</td><td>43</td><td>41</td><td>38</td><td>44</td><td>41</td><td>43</td><td>44</td><td>41</td><td>43</td></tr><tr><td>College msg</td><td>24</td><td>22</td><td>23</td><td>22</td><td>36</td><td>29</td><td>30</td><td>34</td><td>33</td><td>39</td><td>34</td><td>33</td><td>39</td></tr><tr><td>Highschool 2013</td><td>31</td><td>38</td><td>40</td><td>38</td><td>38</td><td>35</td><td>33</td><td>44</td><td>41</td><td>45</td><td>41</td><td>45</td><td>45</td></tr><tr><td>Email EU</td><td>35</td><td>37</td><td>36</td><td>35</td><td>45</td><td>44</td><td>42</td><td>46</td><td>45</td><td>46</td><td>46</td><td>45</td><td>46</td></tr><tr><td>Wiki elections</td><td>12</td><td>11</td><td>14</td><td>15</td><td>29</td><td>22</td><td>18</td><td>30</td><td>26</td><td>30</td><td>30</td><td>26</td><td>30</td></tr><tr><td>Digg reply</td><td>14</td><td>19</td><td>23</td><td>28</td><td>31</td><td>23</td><td>20</td><td>33</td><td>31</td><td>36</td><td>31</td><td>33</td><td>36</td></tr><tr><td>Facebook wall</td><td>18</td><td>16</td><td>17</td><td>18</td><td>34</td><td>31</td><td>28</td><td>37</td><td>30</td><td>37</td><td>30</td><td>37</td><td>37</td></tr><tr><td>Infectious</td><td>9</td><td>12</td><td>18</td><td>26</td><td>16</td><td>16</td><td>13</td><td>28</td><td>19</td><td>28</td><td>19</td><td>28</td><td>28</td></tr><tr><td>Slashdot reply</td><td>24</td><td>22</td><td>23</td><td>23</td><td>39</td><td>39</td><td>32</td><td>42</td><td>34</td><td>36</td><td>34</td><td>36</td><td>36</td></tr><tr><td>SMS</td><td>22</td><td>24</td><td>24</td><td>27</td><td>39</td><td>35</td><td>34</td><td>38</td><td>37</td><td>44</td><td>37</td><td>44</td><td>44</td></tr></tbody></table>
<table><caption>Table 14: Shortest fastest walks and Kendall, weighted Kendall, and intersection correlation</caption><thead><tr><th rowspan="3">Network</th><th colspan="10">Kendall's τ</th></tr><tr><th colspan="4">∞</th><th colspan="4">300</th><th colspan="3">600</th><th colspan="3">1200</th></tr><tr><th>300</th><th>600</th><th>1200</th><th>2400</th><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.83</td><td>0.86</td><td>0.92</td><td>0.96</td><td>0.87</td><td>0.85</td><td>0.82</td><td>0.89</td><td>0.86</td><td>0.93</td><td>0.83</td><td>0.86</td><td>0.93</td></tr><tr><td>Hospital ward</td><td>0.66</td><td>0.70</td><td>0.78</td><td>0.82</td><td>0.79</td><td>0.77</td><td>0.71</td><td>0.84</td><td>0.77</td><td>0.83</td><td>0.66</td><td>0.70</td><td>0.78</td></tr><tr><td>Highschool 2011</td><td>0.81</td><td>0.82</td><td>0.83</td><td>0.88</td><td>0.86</td><td>0.80</td><td>0.78</td><td>0.83</td><td>0.80</td><td>0.85</td><td>0.71</td><td>0.78</td><td>0.83</td></tr><tr><td>Highschool 2012</td><td>0.71</td><td>0.69</td><td>0.66</td><td>0.76</td><td>0.78</td><td>0.69</td><td>0.72</td><td>0.76</td><td>0.72</td><td>0.74</td><td>0.69</td><td>0.72</td><td>0.76</td></tr><tr><td>Primary school</td><td>0.88</td><td>0.96</td><td>0.99</td><td>0.99</td><td>0.90</td><td>0.89</td><td>0.88</td><td>0.97</td><td>0.96</td><td>0.99</td><td>0.88</td><td>0.96</td><td>0.97</td></tr><tr><td>College msg</td><td>0.62</td><td>0.65</td><td>0.68</td><td>0.70</td><td>0.90</td><td>0.83</td><td>0.80</td><td>0.89</td><td>0.86</td><td>0.92</td><td>0.62</td><td>0.65</td><td>0.68</td></tr><tr><td>Highschool 2013</td><td>0.73</td><td>0.85</td><td>0.93</td><td>0.97</td><td>0.82</td><td>0.75</td><td>0.74</td><td>0.88</td><td>0.86</td><td>0.95</td><td>0.73</td><td>0.85</td><td>0.93</td></tr><tr><td>Email EU</td><td>0.63</td><td>0.68</td><td>0.73</td><td>0.76</td><td>0.88</td><td>0.79</td><td>0.74</td><td>0.87</td><td>0.81</td><td>0.89</td><td>0.63</td><td>0.68</td><td>0.73</td></tr><tr><td>Wiki elections</td><td>0.22</td><td>0.28</td><td>0.36</td><td>0.43</td><td>0.79</td><td>0.62</td><td>0.51</td><td>0.79</td><td>0.64</td><td>0.81</td><td>0.22</td><td>0.28</td><td>0.36</td></tr><tr><td>Digg reply</td><td>0.25</td><td>0.30</td><td>0.35</td><td>0.40</td><td>0.82</td><td>0.71</td><td>0.61</td><td>0.86</td><td>0.75</td><td>0.86</td><td>0.25</td><td>0.30</td><td>0.35</td></tr><tr><td>Facebook wall</td><td>0.19</td><td>0.24</td><td>0.28</td><td>0.34</td><td>0.78</td><td>0.63</td><td>0.52</td><td>0.80</td><td>0.67</td><td>0.82</td><td>0.19</td><td>0.24</td><td>0.28</td></tr><tr><td>Infectious</td><td>0.64</td><td>0.73</td><td>0.82</td><td>0.91</td><td>0.76</td><td>0.70</td><td>0.66</td><td>0.83</td><td>0.76</td><td>0.86</td><td>0.64</td><td>0.73</td><td>0.82</td></tr><tr><td>Slashdot reply</td><td>0.33</td><td>0.38</td><td>0.44</td><td>0.50</td><td>0.86</td><td>0.74</td><td>0.65</td><td>0.86</td><td>0.76</td><td>0.87</td><td>0.33</td><td>0.38</td><td>0.44</td></tr><tr><td>SMS</td><td>0.29</td><td>0.34</td><td>0.38</td><td>0.41</td><td>0.85</td><td>0.76</td><td>0.70</td><td>0.90</td><td>0.82</td><td>0.91</td><td>0.29</td><td>0.34</td><td>0.38</td></tr></tbody></table><table><thead><tr><th rowspan="3">Network</th><th colspan="10">Weighted Kendall's τ</th></tr><tr><th colspan="4">∞</th><th colspan="4">300</th><th colspan="3">600</th><th colspan="3">1200</th></tr><tr><th>300</th><th>600</th><th>1200</th><th>2400</th><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.92</td><td>0.93</td><td>0.97</td><td>0.98</td><td>0.94</td><td>0.92</td><td>0.91</td><td>0.94</td><td>0.93</td><td>0.97</td><td>0.92</td><td>0.93</td><td>0.98</td></tr><tr><td>Hospital ward</td><td>0.83</td><td>0.80</td><td>0.86</td><td>0.91</td><td>0.88</td><td>0.88</td><td>0.86</td><td>0.91</td><td>0.84</td><td>0.90</td><td>0.83</td><td>0.80</td><td>0.86</td></tr><tr><td>Highschool 2011</td><td>0.86</td><td>0.83</td><td>0.88</td><td>0.94</td><td>0.87</td><td>0.85</td><td>0.85</td><td>0.86</td><td>0.82</td><td>0.89</td><td>0.86</td><td>0.83</td><td>0.89</td></tr><tr><td>Highschool 2012</td><td>0.78</td><td>0.77</td><td>0.78</td><td>0.86</td><td>0.85</td><td>0.78</td><td>0.81</td><td>0.85</td><td>0.81</td><td>0.83</td><td>0.78</td><td>0.77</td><td>0.81</td></tr><tr><td>Primary school</td><td>0.93</td><td>0.98</td><td>0.99</td><td>0.99</td><td>0.94</td><td>0.94</td><td>0.93</td><td>0.98</td><td>0.98</td><td>0.99</td><td>0.93</td><td>0.98</td><td>0.99</td></tr><tr><td>College msg</td><td>0.86</td><td>0.86</td><td>0.86</td><td>0.87</td><td>0.96</td><td>0.93</td><td>0.92</td><td>0.95</td><td>0.94</td><td>0.96</td><td>0.86</td><td>0.86</td><td>0.87</td></tr><tr><td>Highschool 2013</td><td>0.82</td><td>0.93</td><td>0.97</td><td>0.99</td><td>0.89</td><td>0.84</td><td>0.83</td><td>0.95</td><td>0.94</td><td>0.98</td><td>0.82</td><td>0.85</td><td>0.87</td></tr><tr><td>Email EU</td><td>0.87</td><td>0.89</td><td>0.91</td><td>0.91</td><td>0.96</td><td>0.93</td><td>0.91</td><td>0.95</td><td>0.93</td><td>0.96</td><td>0.87</td><td>0.89</td><td>0.91</td></tr><tr><td>Wiki elections</td><td>0.68</td><td>0.72</td><td>0.75</td><td>0.79</td><td>0.94</td><td>0.87</td><td>0.81</td><td>0.95</td><td>0.89</td><td>0.95</td><td>0.68</td><td>0.72</td><td>0.75</td></tr><tr><td>Digg reply</td><td>0.75</td><td>0.79</td><td>0.81</td><td>0.83</td><td>0.96</td><td>0.93</td><td>0.90</td><td>0.97</td><td>0.94</td><td>0.97</td><td>0.75</td><td>0.79</td><td>0.81</td></tr><tr><td>Facebook wall</td><td>0.73</td><td>0.76</td><td>0.78</td><td>0.81</td><td>0.95</td><td>0.91</td><td>0.88</td><td>0.96</td><td>0.92</td><td>0.96</td><td>0.73</td><td>0.76</td><td>0.78</td></tr><tr><td>Infectious</td><td>0.75</td><td>0.82</td><td>0.88</td><td>0.95</td><td>0.85</td><td>0.81</td><td>0.77</td><td>0.92</td><td>0.86</td><td>0.92</td><td>0.75</td><td>0.82</td><td>0.88</td></tr><tr><td>Slashdot reply</td><td>0.82</td><td>0.85</td><td>0.87</td><td>0.88</td><td>0.97</td><td>0.95</td><td>0.92</td><td>0.98</td><td>0.95</td><td>0.97</td><td>0.82</td><td>0.85</td><td>0.87</td></tr><tr><td>SMS</td><td>0.79</td><td>0.82</td><td>0.83</td><td>0.85</td><td>0.97</td><td>0.95</td><td>0.93</td><td>0.98</td><td>0.96</td><td>0.98</td><td>0.79</td><td>0.82</td><td>0.83</td></tr></tbody></table><table><thead><tr><th rowspan="3">Network</th><th colspan="10">Intersection top-50</th></tr><tr><th colspan="4">∞</th><th colspan="4">300</th><th colspan="3">600</th><th colspan="3">1200</th></tr><tr><th>300</th><th>600</th><th>1200</th><th>2400</th><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>45</td><td>47</td><td>48</td><td>48</td><td>46</td><td>46</td><td>45</td><td>48</td><td>47</td><td>48</td><td>45</td><td>47</td><td>48</td></tr><tr><td>Hospital ward</td><td>41</td><td>44</td><td>46</td><td>45</td><td>45</td><td>44</td><td>42</td><td>47</td><td>45</td><td>48</td><td>41</td><td>42</td><td>47</td></tr><tr><td>Highschool 2011</td><td>44</td><td>44</td><td>46</td><td>48</td><td>47</td><td>42</td><td>43</td><td>44</td><td>45</td><td>47</td><td>44</td><td>43</td><td>48</td></tr><tr><td>Highschool 2012</td><td>39</td><td>40</td><td>38</td><td>43</td><td>41</td><td>36</td><td>38</td><td>41</td><td>40</td><td>40</td><td>39</td><td>40</td><td>41</td></tr><tr><td>Primary school</td><td>45</td><td>47</td><td>50</td><td>49</td><td>44</td><td>45</td><td>44</td><td>47</td><td>48</td><td>49</td><td>45</td><td>47</td><td>48</td></tr><tr><td>College msg</td><td>27</td><td>25</td><td>24</td><td>24</td><td>36</td><td>29</td><td>31</td><td>33</td><td>33</td><td>39</td><td>27</td><td>25</td><td>24</td></tr><tr><td>Highschool 2013</td><td>33</td><td>43</td><td>47</td><td>49</td><td>38</td><td>35</td><td>33</td><td>46</td><td>44</td><td>47</td><td>33</td><td>43</td><td>47</td></tr><tr><td>Email EU</td><td>39</td><td>41</td><td>43</td><td>40</td><td>46</td><td>43</td><td>42</td><td>46</td><td>45</td><td>46</td><td>39</td><td>41</td><td>43</td></tr><tr><td>Wiki elections</td><td>12</td><td>11</td><td>15</td><td>14</td><td>29</td><td>22</td><td>18</td><td>30</td><td>26</td><td>29</td><td>12</td><td>11</td><td>15</td></tr><tr><td>Digg reply</td><td>14</td><td>20</td><td>23</td><td>28</td><td>31</td><td>23</td><td>20</td><td>33</td><td>31</td><td>36</td><td>14</td><td>20</td><td>23</td></tr><tr><td>Facebook wall</td><td>17</td><td>16</td><td>18</td><td>19</td><td>34</td><td>31</td><td>28</td><td>37</td><td>30</td><td>38</td><td>17</td><td>16</td><td>18</td></tr><tr><td>Infectious</td><td>10</td><td>16</td><td>20</td><td>33</td><td>20</td><td>18</td><td>16</td><td>30</td><td>23</td><td>30</td><td>10</td><td>16</td><td>20</td></tr><tr><td>Slashdot reply</td><td>23</td><td>21</td><td>22</td><td>23</td><td>39</td><td>39</td><td>32</td><td>42</td><td>34</td><td>36</td><td>23</td><td>21</td><td>22</td></tr><tr><td>SMS</td><td>23</td><td>27</td><td>26</td><td>30</td><td>39</td><td>35</td><td>35</td><td>38</td><td>38</td><td>42</td><td>23</td><td>27</td><td>26</td></tr></tbody></table>
<table><thead><tr><th rowspan="3">Network</th><th colspan="10">Kendall's τ</th></tr><tr><th colspan="4">∞</th><th colspan="3">300</th><th colspan="2">600</th><th>1200</th></tr><tr><th>300</th><th>600</th><th>1200</th><th>2400</th><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.59</td><td>0.64</td><td>0.71</td><td>0.81</td><td>0.70</td><td>0.69</td><td>0.61</td><td>0.74</td><td>0.67</td><td>0.80</td></tr><tr><td>Hospital ward</td><td>0.64</td><td>0.69</td><td>0.74</td><td>0.76</td><td>0.77</td><td>0.70</td><td>0.65</td><td>0.81</td><td>0.73</td><td>0.79</td></tr><tr><td>Highschool 2011</td><td>0.57</td><td>0.57</td><td>0.63</td><td>0.71</td><td>0.80</td><td>0.72</td><td>0.65</td><td>0.73</td><td>0.64</td><td>0.77</td></tr><tr><td>Highschool 2012</td><td>0.56</td><td>0.54</td><td>0.53</td><td>0.63</td><td>0.75</td><td>0.66</td><td>0.65</td><td>0.74</td><td>0.64</td><td>0.66</td></tr><tr><td>Primary school</td><td>0.48</td><td>0.65</td><td>0.80</td><td>0.87</td><td>0.62</td><td>0.51</td><td>0.49</td><td>0.74</td><td>0.69</td><td>0.86</td></tr><tr><td>College msg</td><td>0.62</td><td>0.65</td><td>0.68</td><td>0.70</td><td>0.90</td><td>0.83</td><td>0.80</td><td>0.89</td><td>0.85</td><td>0.91</td></tr><tr><td>Highschool 2013</td><td>0.49</td><td>0.58</td><td>0.68</td><td>0.79</td><td>0.73</td><td>0.61</td><td>0.53</td><td>0.75</td><td>0.65</td><td>0.78</td></tr><tr><td>Email EU</td><td>0.61</td><td>0.66</td><td>0.70</td><td>0.71</td><td>0.88</td><td>0.79</td><td>0.74</td><td>0.87</td><td>0.82</td><td>0.89</td></tr><tr><td>Wiki elections</td><td>0.24</td><td>0.29</td><td>0.36</td><td>0.45</td><td>0.82</td><td>0.66</td><td>0.53</td><td>0.79</td><td>0.65</td><td>0.80</td></tr><tr><td>Digg reply</td><td>0.25</td><td>0.30</td><td>0.35</td><td>0.40</td><td>0.82</td><td>0.71</td><td>0.61</td><td>0.86</td><td>0.75</td><td>0.87</td></tr><tr><td>Facebook wall</td><td>0.19</td><td>0.24</td><td>0.29</td><td>0.34</td><td>0.78</td><td>0.63</td><td>0.52</td><td>0.81</td><td>0.67</td><td>0.82</td></tr><tr><td>Infectious</td><td>0.62</td><td>0.70</td><td>0.79</td><td>0.89</td><td>0.75</td><td>0.68</td><td>0.64</td><td>0.81</td><td>0.74</td><td>0.84</td></tr><tr><td>Slashdot reply</td><td>0.33</td><td>0.38</td><td>0.44</td><td>0.50</td><td>0.86</td><td>0.74</td><td>0.65</td><td>0.86</td><td>0.76</td><td>0.87</td></tr><tr><td>SMS</td><td>0.30</td><td>0.35</td><td>0.38</td><td>0.41</td><td>0.85</td><td>0.77</td><td>0.70</td><td>0.90</td><td>0.82</td><td>0.91</td></tr></tbody></table>

<table><thead><tr><th rowspan="3">Network</th><th colspan="10">Weighted Kendall's τ</th></tr><tr><th colspan="4">∞</th><th colspan="3">300</th><th colspan="2">600</th><th>1200</th></tr><tr><th>300</th><th>600</th><th>1200</th><th>2400</th><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.79</td><td>0.82</td><td>0.86</td><td>0.92</td><td>0.84</td><td>0.85</td><td>0.81</td><td>0.88</td><td>0.84</td><td>0.90</td></tr><tr><td>Hospital ward</td><td>0.77</td><td>0.81</td><td>0.86</td><td>0.89</td><td>0.88</td><td>0.83</td><td>0.80</td><td>0.90</td><td>0.84</td><td>0.89</td></tr><tr><td>Highschool 2011</td><td>0.66</td><td>0.62</td><td>0.75</td><td>0.84</td><td>0.85</td><td>0.74</td><td>0.70</td><td>0.74</td><td>0.67</td><td>0.87</td></tr><tr><td>Highschool 2012</td><td>0.66</td><td>0.58</td><td>0.60</td><td>0.79</td><td>0.83</td><td>0.74</td><td>0.76</td><td>0.83</td><td>0.73</td><td>0.74</td></tr><tr><td>Primary school</td><td>0.65</td><td>0.78</td><td>0.91</td><td>0.95</td><td>0.75</td><td>0.69</td><td>0.67</td><td>0.84</td><td>0.80</td><td>0.94</td></tr><tr><td>College msg</td><td>0.85</td><td>0.86</td><td>0.86</td><td>0.87</td><td>0.96</td><td>0.93</td><td>0.92</td><td>0.95</td><td>0.94</td><td>0.96</td></tr><tr><td>Highschool 2013</td><td>0.61</td><td>0.76</td><td>0.85</td><td>0.92</td><td>0.83</td><td>0.74</td><td>0.65</td><td>0.87</td><td>0.79</td><td>0.89</td></tr><tr><td>Email EU</td><td>0.85</td><td>0.87</td><td>0.88</td><td>0.88</td><td>0.95</td><td>0.93</td><td>0.91</td><td>0.96</td><td>0.94</td><td>0.96</td></tr><tr><td>Wiki elections</td><td>0.68</td><td>0.71</td><td>0.74</td><td>0.78</td><td>0.95</td><td>0.89</td><td>0.82</td><td>0.95</td><td>0.90</td><td>0.95</td></tr><tr><td>Digg reply</td><td>0.75</td><td>0.79</td><td>0.81</td><td>0.83</td><td>0.96</td><td>0.93</td><td>0.90</td><td>0.97</td><td>0.94</td><td>0.97</td></tr><tr><td>Facebook wall</td><td>0.73</td><td>0.76</td><td>0.78</td><td>0.81</td><td>0.95</td><td>0.91</td><td>0.88</td><td>0.96</td><td>0.92</td><td>0.96</td></tr><tr><td>Infectious</td><td>0.74</td><td>0.80</td><td>0.87</td><td>0.93</td><td>0.85</td><td>0.81</td><td>0.76</td><td>0.91</td><td>0.85</td><td>0.91</td></tr><tr><td>Slashdot reply</td><td>0.82</td><td>0.85</td><td>0.87</td><td>0.88</td><td>0.97</td><td>0.95</td><td>0.92</td><td>0.98</td><td>0.95</td><td>0.97</td></tr><tr><td>SMS</td><td>0.79</td><td>0.82</td><td>0.84</td><td>0.85</td><td>0.97</td><td>0.95</td><td>0.93</td><td>0.98</td><td>0.96</td><td>0.98</td></tr></tbody></table>

<table><caption>Table 15: Shortest foremost walks and Kendall, weighted Kendall, and intersection correlation</caption><thead><tr><th rowspan="3">Network</th><th colspan="10">Intersection top-50</th></tr><tr><th colspan="4">∞</th><th colspan="3">300</th><th colspan="2">600</th><th>1200</th></tr><tr><th>300</th><th>600</th><th>1200</th><th>2400</th><th>600</th><th>1200</th><th>2400</th><th>1200</th><th>2400</th><th>2400</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>40</td><td>40</td><td>45</td><td>44</td><td>44</td><td>42</td><td>40</td><td>44</td><td>41</td><td>44</td></tr><tr><td>Hospital ward</td><td>43</td><td>45</td><td>44</td><td>45</td><td>45</td><td>41</td><td>43</td><td>45</td><td>45</td><td>44</td></tr><tr><td>Highschool 2011</td><td>36</td><td>36</td><td>38</td><td>40</td><td>47</td><td>40</td><td>39</td><td>41</td><td>39</td><td>43</td></tr><tr><td>Highschool 2012</td><td>34</td><td>33</td><td>28</td><td>35</td><td>40</td><td>34</td><td>34</td><td>40</td><td>37</td><td>34</td></tr><tr><td>Primary school</td><td>25</td><td>36</td><td>41</td><td>48</td><td>33</td><td>26</td><td>25</td><td>36</td><td>36</td><td>43</td></tr><tr><td>College msg</td><td>26</td><td>24</td><td>23</td><td>23</td><td>35</td><td>29</td><td>30</td><td>34</td><td>33</td><td>39</td></tr><tr><td>Highschool 2013</td><td>24</td><td>35</td><td>37</td><td>43</td><td>33</td><td>26</td><td>22</td><td>39</td><td>30</td><td>34</td></tr><tr><td>Email EU</td><td>39</td><td>42</td><td>41</td><td>41</td><td>46</td><td>42</td><td>43</td><td>45</td><td>45</td><td>44</td></tr><tr><td>Wiki elections</td><td>10</td><td>14</td><td>16</td><td>16</td><td>33</td><td>24</td><td>23</td><td>33</td><td>29</td><td>37</td></tr><tr><td>Digg reply</td><td>14</td><td>19</td><td>23</td><td>27</td><td>31</td><td>23</td><td>20</td><td>33</td><td>31</td><td>36</td></tr><tr><td>Facebook wall</td><td>17</td><td>18</td><td>19</td><td>19</td><td>35</td><td>32</td><td>30</td><td>39</td><td>32</td><td>36</td></tr><tr><td>Infectious</td><td>12</td><td>13</td><td>19</td><td>31</td><td>19</td><td>18</td><td>16</td><td>31</td><td>22</td><td>31</td></tr><tr><td>Slashdot reply</td><td>23</td><td>21</td><td>22</td><td>23</td><td>39</td><td>38</td><td>31</td><td>41</td><td>33</td><td>36</td></tr><tr><td>SMS</td><td>23</td><td>26</td><td>26</td><td>29</td><td>41</td><td>35</td><td>35</td><td>39</td><td>38</td><td>43</td></tr></tbody></table>
<table><thead><tr><th rowspan="3">Network</th><th colspan="12">Kendall's τ</th></tr><tr><th colspan="4">Fa</th><th colspan="3">Fo</th><th colspan="3">Sh</th><th colspan="3">SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.64</td><td>0.84</td><td>0.84</td><td>0.66</td><td>0.58</td><td>0.57</td><td>0.67</td><td>0.93</td><td>0.69</td><td>0.68</td><td></td><td></td></tr><tr><td>Hospital ward</td><td>0.79</td><td>0.79</td><td>0.79</td><td>0.73</td><td>0.71</td><td>0.70</td><td>0.76</td><td>0.94</td><td>0.82</td><td>0.80</td><td></td><td></td></tr><tr><td>Highschool 2011</td><td>0.70</td><td>0.79</td><td>0.81</td><td>0.72</td><td>0.62</td><td>0.63</td><td>0.70</td><td>0.92</td><td>0.80</td><td>0.78</td><td></td><td></td></tr><tr><td>Highschool 2012</td><td>0.79</td><td>0.82</td><td>0.82</td><td>0.78</td><td>0.71</td><td>0.71</td><td>0.74</td><td>0.94</td><td>0.87</td><td>0.87</td><td></td><td></td></tr><tr><td>Primary school</td><td>0.44</td><td>0.69</td><td>0.71</td><td>0.50</td><td>0.32</td><td>0.31</td><td>0.48</td><td>0.82</td><td>0.48</td><td>0.47</td><td></td><td></td></tr><tr><td>College msg</td><td>0.93</td><td>0.99</td><td>1.00</td><td>0.98</td><td>0.93</td><td>0.93</td><td>0.94</td><td>0.99</td><td>0.98</td><td>0.98</td><td></td><td></td></tr><tr><td>Highschool 2013</td><td>0.67</td><td>0.78</td><td>0.78</td><td>0.64</td><td>0.55</td><td>0.55</td><td>0.71</td><td>0.91</td><td>0.62</td><td>0.63</td><td></td><td></td></tr><tr><td>Email EU</td><td>0.93</td><td>0.99</td><td>1.00</td><td>0.94</td><td>0.93</td><td>0.93</td><td>0.99</td><td>0.99</td><td>0.94</td><td>0.94</td><td></td><td></td></tr><tr><td>Wiki elections</td><td>0.92</td><td>1.00</td><td>1.00</td><td>0.92</td><td>0.92</td><td>0.92</td><td>0.99</td><td>1.00</td><td>0.92</td><td>0.92</td><td></td><td></td></tr><tr><td>Digg reply</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td></tr><tr><td>Facebook wall</td><td>0.95</td><td>1.00</td><td>1.00</td><td>0.97</td><td>0.95</td><td>0.95</td><td>0.98</td><td>1.00</td><td>0.97</td><td>0.97</td><td></td><td></td></tr><tr><td>Infectious</td><td>0.83</td><td>0.79</td><td>0.81</td><td>0.79</td><td>0.70</td><td>0.71</td><td>0.72</td><td>0.91</td><td>0.90</td><td>0.91</td><td></td><td></td></tr><tr><td>Slashdot reply</td><td>0.99</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td>0.99</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td></tr><tr><td>SMS</td><td>0.92</td><td>1.00</td><td>1.00</td><td>0.97</td><td>0.92</td><td>0.92</td><td>0.95</td><td>1.00</td><td>0.97</td><td>0.97</td><td></td><td></td></tr></tbody></table>

<table><thead><tr><th rowspan="3">Network</th><th colspan="12">Weighted Kendall's τ</th></tr><tr><th colspan="4">Fa</th><th colspan="3">Fo</th><th colspan="3">Sh</th><th colspan="3">SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.77</td><td>0.90</td><td>0.90</td><td>0.78</td><td>0.76</td><td>0.74</td><td>0.83</td><td>0.96</td><td>0.82</td><td>0.81</td><td></td><td></td></tr><tr><td>Hospital ward</td><td>0.87</td><td>0.91</td><td>0.91</td><td>0.86</td><td>0.85</td><td>0.85</td><td>0.88</td><td>0.98</td><td>0.90</td><td>0.89</td><td></td><td></td></tr><tr><td>Highschool 2011</td><td>0.83</td><td>0.86</td><td>0.86</td><td>0.81</td><td>0.75</td><td>0.75</td><td>0.81</td><td>0.96</td><td>0.86</td><td>0.86</td><td></td><td></td></tr><tr><td>Highschool 2012</td><td>0.88</td><td>0.91</td><td>0.90</td><td>0.87</td><td>0.85</td><td>0.84</td><td>0.86</td><td>0.97</td><td>0.93</td><td>0.93</td><td></td><td></td></tr><tr><td>Primary school</td><td>0.57</td><td>0.75</td><td>0.74</td><td>0.58</td><td>0.39</td><td>0.41</td><td>0.52</td><td>0.90</td><td>0.63</td><td>0.57</td><td></td><td></td></tr><tr><td>College msg</td><td>0.98</td><td>0.99</td><td>1.00</td><td>0.99</td><td>0.97</td><td>0.97</td><td>0.98</td><td>1.00</td><td>0.99</td><td>0.99</td><td></td><td></td></tr><tr><td>Highschool 2013</td><td>0.84</td><td>0.86</td><td>0.85</td><td>0.80</td><td>0.70</td><td>0.69</td><td>0.81</td><td>0.96</td><td>0.78</td><td>0.79</td><td></td><td></td></tr><tr><td>Email EU</td><td>0.98</td><td>1.00</td><td>1.00</td><td>0.98</td><td>0.98</td><td>0.98</td><td>1.00</td><td>1.00</td><td>0.98</td><td>0.98</td><td></td><td></td></tr><tr><td>Wiki elections</td><td>0.98</td><td>1.00</td><td>1.00</td><td>0.98</td><td>0.98</td><td>0.98</td><td>1.00</td><td>1.00</td><td>0.98</td><td>0.98</td><td></td><td></td></tr><tr><td>Digg reply</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td></tr><tr><td>Facebook wall</td><td>0.99</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td></tr><tr><td>Infectious</td><td>0.95</td><td>0.89</td><td>0.90</td><td>0.89</td><td>0.86</td><td>0.87</td><td>0.87</td><td>0.97</td><td>0.97</td><td>0.98</td><td></td><td></td></tr><tr><td>Slashdot reply</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td></tr><tr><td>SMS</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.98</td><td>0.98</td><td>0.99</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td></tr></tbody></table>

<table><caption>Table 16: $\beta$ = 300 and Kendall, weighted Kendall, and intersection correlation</caption><thead><tr><th rowspan="3">Network</th><th colspan="12">Intersection top-50</th></tr><tr><th colspan="4">Fa</th><th colspan="3">Fo</th><th colspan="3">Sh</th><th colspan="3">SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>42</td><td>45</td><td>45</td><td>40</td><td>41</td><td>41</td><td>40</td><td>48</td><td>42</td><td>41</td><td></td><td></td></tr><tr><td>Hospital ward</td><td>48</td><td>46</td><td>47</td><td>45</td><td>45</td><td>45</td><td>45</td><td>48</td><td>46</td><td>46</td><td></td><td></td></tr><tr><td>Highschool 2011</td><td>42</td><td>42</td><td>43</td><td>41</td><td>38</td><td>39</td><td>39</td><td>47</td><td>44</td><td>44</td><td></td><td></td></tr><tr><td>Highschool 2012</td><td>45</td><td>41</td><td>39</td><td>41</td><td>39</td><td>36</td><td>39</td><td>46</td><td>43</td><td>45</td><td></td><td></td></tr><tr><td>Primary school</td><td>27</td><td>31</td><td>33</td><td>31</td><td>19</td><td>19</td><td>27</td><td>42</td><td>29</td><td>29</td><td></td><td></td></tr><tr><td>College msg</td><td>44</td><td>47</td><td>47</td><td>45</td><td>44</td><td>44</td><td>42</td><td>50</td><td>48</td><td>48</td><td></td><td></td></tr><tr><td>Highschool 2013</td><td>35</td><td>31</td><td>33</td><td>29</td><td>24</td><td>26</td><td>32</td><td>44</td><td>29</td><td>31</td><td></td><td></td></tr><tr><td>Email EU</td><td>47</td><td>49</td><td>50</td><td>47</td><td>47</td><td>47</td><td>50</td><td>49</td><td>47</td><td>47</td><td></td><td></td></tr><tr><td>Wiki elections</td><td>37</td><td>50</td><td>50</td><td>37</td><td>37</td><td>37</td><td>50</td><td>50</td><td>37</td><td>37</td><td></td><td></td></tr><tr><td>Digg reply</td><td>49</td><td>50</td><td>50</td><td>49</td><td>49</td><td>49</td><td>50</td><td>50</td><td>49</td><td>49</td><td></td><td></td></tr><tr><td>Facebook wall</td><td>44</td><td>50</td><td>50</td><td>48</td><td>44</td><td>44</td><td>45</td><td>50</td><td>48</td><td>48</td><td></td><td></td></tr><tr><td>Infectious</td><td>39</td><td>16</td><td>15</td><td>17</td><td>13</td><td>11</td><td>13</td><td>45</td><td>47</td><td>47</td><td></td><td></td></tr><tr><td>Slashdot reply</td><td>48</td><td>50</td><td>50</td><td>49</td><td>48</td><td>48</td><td>49</td><td>50</td><td>49</td><td>49</td><td></td><td></td></tr><tr><td>SMS</td><td>44</td><td>50</td><td>50</td><td>46</td><td>44</td><td>44</td><td>47</td><td>50</td><td>46</td><td>46</td><td></td><td></td></tr></tbody></table>
<table><thead><tr><th rowspan="3">Network</th><th colspan="12">Kendall's τ</th></tr><tr><th colspan="4">Fa</th><th colspan="4">Fo</th><th colspan="3">Sh</th><th colspan="3">SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.60</td><td>0.80</td><td>0.78</td><td>0.63</td><td>0.52</td><td>0.50</td><td>0.62</td><td>0.88</td><td>0.68</td><td>0.66</td><td>0.82</td><td>0.71</td><td>0.72</td><td>0.69</td></tr><tr><td>Hospital ward</td><td>0.72</td><td>0.75</td><td>0.79</td><td>0.73</td><td>0.60</td><td>0.62</td><td>0.68</td><td>0.89</td><td>0.79</td><td>0.80</td><td>0.80</td><td>0.78</td><td>0.79</td><td>0.76</td></tr><tr><td>Highschool 2011</td><td>0.80</td><td>0.78</td><td>0.79</td><td>0.76</td><td>0.68</td><td>0.68</td><td>0.71</td><td>0.94</td><td>0.86</td><td>0.86</td><td>0.40</td><td>0.66</td><td>0.70</td><td>0.45</td></tr><tr><td>Highschool 2012</td><td>0.93</td><td>0.98</td><td>0.98</td><td>0.97</td><td>0.92</td><td>0.92</td><td>0.93</td><td>0.99</td><td>0.98</td><td>0.99</td><td>0.63</td><td>0.73</td><td>0.72</td><td>0.59</td></tr><tr><td>Primary school</td><td>0.93</td><td>0.98</td><td>1.00</td><td>0.94</td><td>0.93</td><td>0.93</td><td>0.98</td><td>0.99</td><td>0.94</td><td>0.94</td><td>0.95</td><td>1.00</td><td>1.00</td><td>0.95</td></tr><tr><td>College msg</td><td>0.95</td><td>1.00</td><td>1.00</td><td>0.95</td><td>0.95</td><td>0.95</td><td>1.00</td><td>1.00</td><td>0.95</td><td>0.95</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td></tr><tr><td>Highschool 2013</td><td>0.95</td><td>1.00</td><td>1.00</td><td>0.97</td><td>0.94</td><td>0.94</td><td>0.97</td><td>1.00</td><td>0.97</td><td>0.97</td><td>0.82</td><td>0.71</td><td>0.74</td><td>0.71</td></tr><tr><td>Email EU</td><td>0.98</td><td>1.00</td><td>1.00</td><td>0.98</td><td>0.95</td><td>0.95</td><td>1.00</td><td>1.00</td><td>0.95</td><td>0.95</td><td>0.95</td><td>1.00</td><td>1.00</td><td>0.97</td></tr><tr><td>Wiki elections</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.95</td><td>1.00</td><td>1.00</td><td>1.00</td></tr><tr><td>Digg reply</td><td>0.95</td><td>1.00</td><td>1.00</td><td>0.97</td><td>0.94</td><td>0.94</td><td>0.97</td><td>1.00</td><td>0.97</td><td>0.97</td><td>0.81</td><td>0.87</td><td>0.74</td><td>0.71</td></tr><tr><td>Facebook wall</td><td>0.98</td><td>1.00</td><td>1.00</td><td>0.97</td><td>0.91</td><td>0.91</td><td>0.93</td><td>1.00</td><td>0.98</td><td>0.98</td><td>0.91</td><td>1.00</td><td>1.00</td><td>0.97</td></tr><tr><td>Infectious</td><td>0.98</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.98</td><td>0.98</td><td>0.98</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.91</td><td>1.00</td><td>1.00</td><td>0.97</td></tr><tr><td>Slashdot reply</td><td>0.91</td><td>1.00</td><td>1.00</td><td>0.97</td><td>0.91</td><td>0.91</td><td>0.93</td><td>1.00</td><td>0.98</td><td>0.98</td><td>0.91</td><td>1.00</td><td>1.00</td><td>0.97</td></tr></tbody></table>

<table><thead><tr><th rowspan="3">Network</th><th colspan="12">Weighted Kendall's τ</th></tr><tr><th colspan="4">Fa</th><th colspan="4">Fo</th><th colspan="3">Sh</th><th colspan="3">SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.75</td><td>0.87</td><td>0.86</td><td>0.78</td><td>0.70</td><td>0.68</td><td>0.78</td><td>0.93</td><td>0.83</td><td>0.81</td><td>0.90</td><td>0.86</td><td>0.86</td><td>0.82</td></tr><tr><td>Hospital ward</td><td>0.83</td><td>0.86</td><td>0.88</td><td>0.82</td><td>0.74</td><td>0.75</td><td>0.77</td><td>0.94</td><td>0.87</td><td>0.86</td><td>0.90</td><td>0.87</td><td>0.86</td><td>0.85</td></tr><tr><td>Highschool 2011</td><td>0.90</td><td>0.87</td><td>0.86</td><td>0.85</td><td>0.83</td><td>0.82</td><td>0.84</td><td>0.98</td><td>0.93</td><td>0.93</td><td>0.54</td><td>0.72</td><td>0.71</td><td>0.43</td></tr><tr><td>Highschool 2012</td><td>0.98</td><td>0.99</td><td>0.99</td><td>0.99</td><td>0.97</td><td>0.97</td><td>0.97</td><td>1.00</td><td>0.99</td><td>0.99</td><td>0.81</td><td>0.81</td><td>0.77</td><td>0.74</td></tr><tr><td>Primary school</td><td>0.98</td><td>0.99</td><td>1.00</td><td>0.98</td><td>0.98</td><td>0.98</td><td>0.99</td><td>1.00</td><td>0.98</td><td>0.98</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td></tr><tr><td>College msg</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td>0.95</td><td>1.00</td><td>1.00</td><td>0.99</td></tr><tr><td>Highschool 2013</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td>0.99</td><td>0.99</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.95</td><td>0.85</td><td>0.86</td><td>0.85</td></tr><tr><td>Email EU</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td>0.98</td><td>1.00</td><td>1.00</td><td>0.98</td></tr><tr><td>Wiki elections</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td></tr><tr><td>Digg reply</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td>0.99</td><td>0.99</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.95</td><td>1.00</td><td>1.00</td><td>0.99</td></tr><tr><td>Facebook wall</td><td>0.95</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td>0.99</td><td>0.99</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.98</td><td>1.00</td><td>1.00</td><td>0.98</td></tr><tr><td>Infectious</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.98</td><td>1.00</td><td>1.00</td><td>0.98</td></tr><tr><td>Slashdot reply</td><td>0.98</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.98</td><td>0.98</td><td>0.99</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.98</td><td>1.00</td><td>1.00</td><td>0.98</td></tr></tbody></table>

<table><caption>Table 17: $\beta$ = 600 and Kendall, weighted Kendall, and intersection correlation</caption><thead><tr><th rowspan="3">Network</th><th colspan="12">Intersection top-50</th></tr><tr><th colspan="4">Fa</th><th colspan="4">Fo</th><th colspan="3">Sh</th><th colspan="3">SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>39</td><td>46</td><td>47</td><td>39</td><td>40</td><td>39</td><td>41</td><td>45</td><td>41</td><td>40</td><td>47</td><td>42</td><td>42</td><td>41</td></tr><tr><td>Hospital ward</td><td>47</td><td>42</td><td>42</td><td>41</td><td>42</td><td>42</td><td>42</td><td>47</td><td>45</td><td>46</td><td>42</td><td>43</td><td>43</td><td>40</td></tr><tr><td>Highschool 2011</td><td>42</td><td>43</td><td>43</td><td>42</td><td>38</td><td>38</td><td>40</td><td>48</td><td>43</td><td>44</td><td>45</td><td>40</td><td>39</td><td>40</td></tr><tr><td>Highschool 2012</td><td>45</td><td>40</td><td>39</td><td>40</td><td>39</td><td>38</td><td>41</td><td>48</td><td>44</td><td>44</td><td>26</td><td>32</td><td>35</td><td>27</td></tr><tr><td>Primary school</td><td>46</td><td>42</td><td>43</td><td>43</td><td>43</td><td>43</td><td>42</td><td>49</td><td>49</td><td>49</td><td>48</td><td>50</td><td>50</td><td>49</td></tr><tr><td>College msg</td><td>33</td><td>32</td><td>31</td><td>27</td><td>19</td><td>17</td><td>30</td><td>45</td><td>22</td><td>24</td><td>42</td><td>50</td><td>50</td><td>42</td></tr><tr><td>Highschool 2013</td><td>48</td><td>50</td><td>50</td><td>49</td><td>48</td><td>48</td><td>49</td><td>50</td><td>49</td><td>49</td><td>42</td><td>50</td><td>50</td><td>49</td></tr><tr><td>Email EU</td><td>42</td><td>50</td><td>50</td><td>42</td><td>42</td><td>42</td><td>50</td><td>50</td><td>42</td><td>42</td><td>50</td><td>50</td><td>50</td><td>49</td></tr><tr><td>Wiki elections</td><td>50</td><td>50</td><td>50</td><td>50</td><td>50</td><td>50</td><td>50</td><td>50</td><td>50</td><td>50</td><td>46</td><td>46</td><td>46</td><td>45</td></tr><tr><td>Digg reply</td><td>46</td><td>46</td><td>46</td><td>46</td><td>43</td><td>43</td><td>43</td><td>50</td><td>48</td><td>48</td><td>37</td><td>15</td><td>17</td><td>45</td></tr><tr><td>Facebook wall</td><td>49</td><td>50</td><td>50</td><td>49</td><td>49</td><td>49</td><td>50</td><td>50</td><td>49</td><td>49</td><td>49</td><td>50</td><td>50</td><td>49</td></tr><tr><td>Infectious</td><td>49</td><td>50</td><td>50</td><td>49</td><td>49</td><td>49</td><td>50</td><td>50</td><td>49</td><td>49</td><td>49</td><td>50</td><td>50</td><td>49</td></tr><tr><td>Slashdot reply</td><td>42</td><td>45</td><td>45</td><td>43</td><td>41</td><td>41</td><td>40</td><td>50</td><td>46</td><td>46</td><td>42</td><td>45</td><td>45</td><td>40</td></tr><tr><td>SMS</td><td>42</td><td>45</td><td>45</td><td>43</td><td>41</td><td>41</td><td>40</td><td>50</td><td>46</td><td>46</td><td>42</td><td>45</td><td>45</td><td>40</td></tr></tbody></table>
<table><thead><tr><th rowspan="3">Network</th><th colspan="12">Kendall's τ</th></tr><tr><th colspan="4">Fa</th><th colspan="3">Fo</th><th colspan="3">Sh</th><th colspan="3">SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.57</td><td>0.75</td><td>0.77</td><td>0.63</td><td>0.48</td><td>0.48</td><td>0.61</td><td>0.83</td><td>0.64</td><td>0.64</td><td></td><td></td></tr><tr><td>Hospital ward</td><td>0.77</td><td>0.62</td><td>0.63</td><td>0.59</td><td>0.56</td><td>0.58</td><td>0.61</td><td>0.87</td><td>0.78</td><td>0.80</td><td></td><td></td></tr><tr><td>Highschool 2011</td><td>0.72</td><td>0.73</td><td>0.75</td><td>0.67</td><td>0.57</td><td>0.57</td><td>0.68</td><td>0.87</td><td>0.71</td><td>0.69</td><td></td><td></td></tr><tr><td>Highschool 2012</td><td>0.82</td><td>0.76</td><td>0.77</td><td>0.73</td><td>0.68</td><td>0.68</td><td>0.71</td><td>0.93</td><td>0.84</td><td>0.84</td><td></td><td></td></tr><tr><td>Primary school</td><td>0.38</td><td>0.64</td><td>0.70</td><td>0.38</td><td>0.27</td><td>0.29</td><td>0.29</td><td>0.75</td><td>0.41</td><td>0.45</td><td></td><td></td></tr><tr><td>College msg</td><td>0.94</td><td>0.97</td><td>0.97</td><td>0.96</td><td>0.92</td><td>0.92</td><td>0.93</td><td>0.99</td><td>0.98</td><td>0.98</td><td></td><td></td></tr><tr><td>Highschool 2013</td><td>0.58</td><td>0.70</td><td>0.69</td><td>0.55</td><td>0.44</td><td>0.41</td><td>0.58</td><td>0.80</td><td>0.56</td><td>0.54</td><td></td><td></td></tr><tr><td>Email EU</td><td>0.93</td><td>0.98</td><td>1.00</td><td>0.95</td><td>0.93</td><td>0.93</td><td>0.98</td><td>0.98</td><td>0.95</td><td>0.95</td><td></td><td></td></tr><tr><td>Wiki elections</td><td>0.97</td><td>1.00</td><td>1.00</td><td>0.97</td><td>0.96</td><td>0.97</td><td>0.99</td><td>1.00</td><td>0.97</td><td>0.97</td><td></td><td></td></tr><tr><td>Digg reply</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td></tr><tr><td>Facebook wall</td><td>0.94</td><td>0.99</td><td>0.99</td><td>0.97</td><td>0.94</td><td>0.94</td><td>0.96</td><td>1.00</td><td>0.98</td><td>0.98</td><td></td><td></td></tr><tr><td>Infectious</td><td>0.82</td><td>0.64</td><td>0.68</td><td>0.65</td><td>0.57</td><td>0.60</td><td>0.60</td><td>0.82</td><td>0.83</td><td>0.87</td><td></td><td></td></tr><tr><td>Slashdot reply</td><td>0.98</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.98</td><td>0.98</td><td>0.98</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td></tr><tr><td>SMS</td><td>0.91</td><td>0.99</td><td>0.99</td><td>0.97</td><td>0.90</td><td>0.90</td><td>0.92</td><td>1.00</td><td>0.98</td><td>0.98</td><td></td><td></td></tr></tbody></table>

<table><thead><tr><th rowspan="3">Network</th><th colspan="12">Weighted Kendall's τ</th></tr><tr><th colspan="4">Fa</th><th colspan="3">Fo</th><th colspan="3">Sh</th><th colspan="3">SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFo</th><th>SFa</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.74</td><td>0.85</td><td>0.86</td><td>0.79</td><td>0.68</td><td>0.67</td><td>0.79</td><td>0.91</td><td>0.81</td><td>0.80</td><td></td><td></td></tr><tr><td>Hospital ward</td><td>0.87</td><td>0.82</td><td>0.83</td><td>0.76</td><td>0.76</td><td>0.79</td><td>0.78</td><td>0.94</td><td>0.84</td><td>0.85</td><td></td><td></td></tr><tr><td>Highschool 2011</td><td>0.73</td><td>0.82</td><td>0.81</td><td>0.72</td><td>0.61</td><td>0.59</td><td>0.75</td><td>0.92</td><td>0.77</td><td>0.75</td><td></td><td></td></tr><tr><td>Highschool 2012</td><td>0.89</td><td>0.83</td><td>0.82</td><td>0.81</td><td>0.79</td><td>0.78</td><td>0.82</td><td>0.97</td><td>0.90</td><td>0.91</td><td></td><td></td></tr><tr><td>Primary school</td><td>0.50</td><td>0.70</td><td>0.71</td><td>0.44</td><td>0.29</td><td>0.33</td><td>0.31</td><td>0.86</td><td>0.56</td><td>0.59</td><td></td><td></td></tr><tr><td>College msg</td><td>0.98</td><td>0.98</td><td>0.98</td><td>0.98</td><td>0.97</td><td>0.97</td><td>0.97</td><td>1.00</td><td>0.99</td><td>0.99</td><td></td><td></td></tr><tr><td>Highschool 2013</td><td>0.76</td><td>0.77</td><td>0.73</td><td>0.70</td><td>0.54</td><td>0.46</td><td>0.70</td><td>0.90</td><td>0.74</td><td>0.70</td><td></td><td></td></tr><tr><td>Email EU</td><td>0.98</td><td>0.99</td><td>1.00</td><td>0.98</td><td>0.98</td><td>0.98</td><td>0.99</td><td>0.99</td><td>0.98</td><td>0.98</td><td></td><td></td></tr><tr><td>Wiki elections</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td></td><td></td></tr><tr><td>Digg reply</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td></tr><tr><td>Facebook wall</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td>0.99</td><td>0.99</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td></tr><tr><td>Infectious</td><td>0.95</td><td>0.81</td><td>0.82</td><td>0.82</td><td>0.78</td><td>0.78</td><td>0.79</td><td>0.94</td><td>0.95</td><td>0.96</td><td></td><td></td></tr><tr><td>Slashdot reply</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td></tr><tr><td>SMS</td><td>0.98</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.98</td><td>0.98</td><td>0.98</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td></tr></tbody></table>

<table><caption>Table 18: $\beta$ = 1200 and Kendall, weighted Kendall, and intersection correlation</caption><thead><tr><th rowspan="3">Network</th><th colspan="12">Intersection top-50</th></tr><tr><th colspan="4">Fa</th><th colspan="3">Fo</th><th colspan="3">Sh</th><th colspan="3">SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFo</th><th>SFa</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>40</td><td>42</td><td>46</td><td>39</td><td>36</td><td>38</td><td>42</td><td>44</td><td>39</td><td>38</td><td></td><td></td></tr><tr><td>Hospital ward</td><td>47</td><td>40</td><td>39</td><td>40</td><td>40</td><td>39</td><td>41</td><td>49</td><td>45</td><td>44</td><td></td><td></td></tr><tr><td>Highschool 2011</td><td>42</td><td>42</td><td>43</td><td>41</td><td>36</td><td>36</td><td>38</td><td>48</td><td>40</td><td>39</td><td></td><td></td></tr><tr><td>Highschool 2012</td><td>43</td><td>39</td><td>38</td><td>39</td><td>38</td><td>36</td><td>41</td><td>48</td><td>42</td><td>44</td><td></td><td></td></tr><tr><td>Primary school</td><td>23</td><td>33</td><td>36</td><td>22</td><td>21</td><td>20</td><td>17</td><td>40</td><td>20</td><td>24</td><td></td><td></td></tr><tr><td>College msg</td><td>47</td><td>43</td><td>43</td><td>43</td><td>42</td><td>42</td><td>42</td><td>50</td><td>50</td><td>50</td><td></td><td></td></tr><tr><td>Highschool 2013</td><td>29</td><td>31</td><td>34</td><td>26</td><td>18</td><td>18</td><td>25</td><td>42</td><td>27</td><td>27</td><td></td><td></td></tr><tr><td>Email EU</td><td>47</td><td>48</td><td>49</td><td>47</td><td>47</td><td>47</td><td>50</td><td>49</td><td>47</td><td>47</td><td></td><td></td></tr><tr><td>Wiki elections</td><td>44</td><td>50</td><td>50</td><td>44</td><td>44</td><td>44</td><td>50</td><td>50</td><td>44</td><td>44</td><td></td><td></td></tr><tr><td>Digg reply</td><td>50</td><td>50</td><td>50</td><td>50</td><td>50</td><td>50</td><td>50</td><td>50</td><td>50</td><td>50</td><td></td><td></td></tr><tr><td>Facebook wall</td><td>47</td><td>46</td><td>46</td><td>46</td><td>43</td><td>44</td><td>45</td><td>49</td><td>47</td><td>48</td><td></td><td></td></tr><tr><td>Infectious</td><td>37</td><td>16</td><td>16</td><td>17</td><td>14</td><td>14</td><td>15</td><td>45</td><td>45</td><td>48</td><td></td><td></td></tr><tr><td>Slashdot reply</td><td>48</td><td>49</td><td>49</td><td>49</td><td>47</td><td>47</td><td>47</td><td>50</td><td>50</td><td>50</td><td></td><td></td></tr><tr><td>SMS</td><td>42</td><td>44</td><td>45</td><td>44</td><td>39</td><td>38</td><td>39</td><td>49</td><td>49</td><td>49</td><td></td><td></td></tr></tbody></table>
<table><thead><tr><th rowspan="3">Network</th><th colspan="12">Kendall's τ</th></tr><tr><th colspan="4">Fa</th><th colspan="4">Fo</th><th colspan="3">Sh</th><th colspan="3">SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.55</td><td>0.75</td><td>0.79</td><td>0.62</td><td>0.46</td><td>0.45</td><td>0.55</td><td>0.79</td><td>0.65</td><td>0.63</td><td></td><td></td><td></td></tr><tr><td>Hospital ward</td><td>0.78</td><td>0.62</td><td>0.59</td><td>0.57</td><td>0.59</td><td>0.55</td><td>0.59</td><td>0.85</td><td>0.79</td><td>0.77</td><td></td><td></td><td></td></tr><tr><td>Highschool 2011</td><td>0.68</td><td>0.67</td><td>0.69</td><td>0.61</td><td>0.54</td><td>0.51</td><td>0.60</td><td>0.81</td><td>0.66</td><td>0.64</td><td></td><td></td><td></td></tr><tr><td>Highschool 2012</td><td>0.78</td><td>0.71</td><td>0.69</td><td>0.65</td><td>0.62</td><td>0.61</td><td>0.66</td><td>0.89</td><td>0.76</td><td>0.77</td><td></td><td></td><td></td></tr><tr><td>Primary school</td><td>0.38</td><td>0.63</td><td>0.70</td><td>0.36</td><td>0.26</td><td>0.29</td><td>0.27</td><td>0.72</td><td>0.38</td><td>0.44</td><td></td><td></td><td></td></tr><tr><td>College msg</td><td>0.94</td><td>0.96</td><td>0.97</td><td>0.95</td><td>0.92</td><td>0.92</td><td>0.93</td><td>0.99</td><td>0.98</td><td>0.98</td><td></td><td></td><td></td></tr><tr><td>Highschool 2013</td><td>0.56</td><td>0.69</td><td>0.69</td><td>0.51</td><td>0.43</td><td>0.39</td><td>0.53</td><td>0.76</td><td>0.56</td><td>0.53</td><td></td><td></td><td></td></tr><tr><td>Email EU</td><td>0.94</td><td>0.98</td><td>0.99</td><td>0.95</td><td>0.94</td><td>0.93</td><td>0.98</td><td>0.98</td><td>0.95</td><td>0.95</td><td></td><td></td><td></td></tr><tr><td>Wiki elections</td><td>0.96</td><td>1.00</td><td>1.00</td><td>0.96</td><td>0.96</td><td>0.96</td><td>1.00</td><td>1.00</td><td>0.96</td><td>0.96</td><td></td><td></td><td></td></tr><tr><td>Digg reply</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td><td></td></tr><tr><td>Facebook wall</td><td>0.94</td><td>0.99</td><td>0.99</td><td>0.97</td><td>0.93</td><td>0.93</td><td>0.95</td><td>1.00</td><td>0.98</td><td>0.98</td><td></td><td></td><td></td></tr><tr><td>Infectious</td><td>0.82</td><td>0.57</td><td>0.64</td><td>0.60</td><td>0.52</td><td>0.56</td><td>0.55</td><td>0.78</td><td>0.80</td><td>0.85</td><td></td><td></td><td></td></tr><tr><td>Slashdot reply</td><td>0.98</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.97</td><td>0.97</td><td>0.98</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td><td></td></tr><tr><td>SMS</td><td>0.91</td><td>0.99</td><td>0.99</td><td>0.97</td><td>0.90</td><td>0.90</td><td>0.91</td><td>1.00</td><td>0.98</td><td>0.98</td><td></td><td></td><td></td></tr></tbody></table>

<table><thead><tr><th rowspan="3">Network</th><th colspan="12">Weighted Kendall's τ</th></tr><tr><th colspan="4">Fa</th><th colspan="4">Fo</th><th colspan="3">Sh</th><th colspan="3">SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.73</td><td>0.87</td><td>0.89</td><td>0.79</td><td>0.68</td><td>0.66</td><td>0.76</td><td>0.89</td><td>0.80</td><td>0.78</td><td></td><td></td><td></td></tr><tr><td>Hospital ward</td><td>0.88</td><td>0.78</td><td>0.80</td><td>0.72</td><td>0.77</td><td>0.78</td><td>0.75</td><td>0.91</td><td>0.88</td><td>0.84</td><td></td><td></td><td></td></tr><tr><td>Highschool 2011</td><td>0.70</td><td>0.75</td><td>0.75</td><td>0.70</td><td>0.51</td><td>0.46</td><td>0.62</td><td>0.87</td><td>0.74</td><td>0.70</td><td></td><td></td><td></td></tr><tr><td>Highschool 2012</td><td>0.87</td><td>0.80</td><td>0.78</td><td>0.74</td><td>0.75</td><td>0.72</td><td>0.78</td><td>0.94</td><td>0.84</td><td>0.83</td><td></td><td></td><td></td></tr><tr><td>Primary school</td><td>0.50</td><td>0.70</td><td>0.71</td><td>0.41</td><td>0.27</td><td>0.33</td><td>0.29</td><td>0.84</td><td>0.51</td><td>0.59</td><td></td><td></td><td></td></tr><tr><td>College msg</td><td>0.98</td><td>0.98</td><td>0.98</td><td>0.98</td><td>0.97</td><td>0.97</td><td>0.97</td><td>1.00</td><td>0.99</td><td>0.99</td><td></td><td></td><td></td></tr><tr><td>Highschool 2013</td><td>0.74</td><td>0.76</td><td>0.73</td><td>0.64</td><td>0.53</td><td>0.44</td><td>0.62</td><td>0.88</td><td>0.74</td><td>0.71</td><td></td><td></td><td></td></tr><tr><td>Email EU</td><td>0.98</td><td>0.99</td><td>1.00</td><td>0.98</td><td>0.98</td><td>0.98</td><td>0.99</td><td>1.00</td><td>0.98</td><td>0.98</td><td></td><td></td><td></td></tr><tr><td>Wiki elections</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.99</td><td></td><td></td><td></td></tr><tr><td>Digg reply</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td><td></td></tr><tr><td>Facebook wall</td><td>0.99</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.98</td><td>0.98</td><td>0.99</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td><td></td></tr><tr><td>Infectious</td><td>0.95</td><td>0.77</td><td>0.79</td><td>0.78</td><td>0.73</td><td>0.75</td><td>0.74</td><td>0.92</td><td>0.93</td><td>0.95</td><td></td><td></td><td></td></tr><tr><td>Slashdot reply</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td><td></td></tr><tr><td>SMS</td><td>0.98</td><td>1.00</td><td>1.00</td><td>0.99</td><td>0.97</td><td>0.97</td><td>0.98</td><td>1.00</td><td>1.00</td><td>1.00</td><td></td><td></td><td></td></tr></tbody></table>

<table><caption>Table 19: $\beta$ = 2400 and Kendall, weighted Kendall, and intersection correlation</caption><thead><tr><th rowspan="3">Network</th><th colspan="12">Intersection top-50</th></tr><tr><th colspan="4">Fa</th><th colspan="4">Fo</th><th colspan="3">Sh</th><th colspan="3">SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>37</td><td>41</td><td>46</td><td>37</td><td>35</td><td>38</td><td>40</td><td>42</td><td>39</td><td>39</td><td></td><td></td><td></td></tr><tr><td>Hospital ward</td><td>46</td><td>41</td><td>39</td><td>41</td><td>42</td><td>40</td><td>43</td><td>46</td><td>47</td><td>45</td><td></td><td></td><td></td></tr><tr><td>Highschool 2011</td><td>41</td><td>40</td><td>41</td><td>40</td><td>35</td><td>36</td><td>37</td><td>47</td><td>38</td><td>38</td><td></td><td></td><td></td></tr><tr><td>Highschool 2012</td><td>41</td><td>36</td><td>37</td><td>36</td><td>35</td><td>35</td><td>38</td><td>47</td><td>39</td><td>40</td><td></td><td></td><td></td></tr><tr><td>Primary school</td><td>24</td><td>33</td><td>36</td><td>21</td><td>21</td><td>20</td><td>15</td><td>38</td><td>19</td><td>24</td><td></td><td></td><td></td></tr><tr><td>College msg</td><td>45</td><td>42</td><td>43</td><td>43</td><td>40</td><td>40</td><td>40</td><td>49</td><td>48</td><td>49</td><td></td><td></td><td></td></tr><tr><td>Highschool 2013</td><td>27</td><td>32</td><td>36</td><td>26</td><td>18</td><td>16</td><td>22</td><td>41</td><td>29</td><td>28</td><td></td><td></td><td></td></tr><tr><td>Email EU</td><td>49</td><td>49</td><td>50</td><td>48</td><td>48</td><td>49</td><td>49</td><td>49</td><td>48</td><td>48</td><td></td><td></td><td></td></tr><tr><td>Wiki elections</td><td>39</td><td>49</td><td>50</td><td>39</td><td>40</td><td>39</td><td>50</td><td>49</td><td>40</td><td>39</td><td></td><td></td><td></td></tr><tr><td>Digg reply</td><td>49</td><td>50</td><td>50</td><td>49</td><td>49</td><td>49</td><td>50</td><td>50</td><td>49</td><td>49</td><td></td><td></td><td></td></tr><tr><td>Facebook wall</td><td>46</td><td>44</td><td>44</td><td>45</td><td>42</td><td>42</td><td>43</td><td>50</td><td>47</td><td>47</td><td></td><td></td><td></td></tr><tr><td>Infectious</td><td>37</td><td>18</td><td>17</td><td>20</td><td>15</td><td>14</td><td>17</td><td>41</td><td>44</td><td>45</td><td></td><td></td><td></td></tr><tr><td>Slashdot reply</td><td>48</td><td>47</td><td>47</td><td>47</td><td>48</td><td>48</td><td>48</td><td>50</td><td>50</td><td>50</td><td></td><td></td><td></td></tr><tr><td>SMS</td><td>43</td><td>45</td><td>45</td><td>43</td><td>41</td><td>40</td><td>40</td><td>48</td><td>48</td><td>47</td><td></td><td></td><td></td></tr></tbody></table>
<table><thead><tr><th rowspan="3">Network</th><th colspan="3">Kendall's τ</th></tr><tr><th colspan="2">Sh</th><th>SFa</th></tr><tr><th>SFa</th><th>SFo</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.72</td><td>0.55</td><td>0.56</td></tr><tr><td>Hospital ward</td><td>0.65</td><td>0.63</td><td>0.70</td></tr><tr><td>Highschool 2011</td><td>0.70</td><td>0.54</td><td>0.52</td></tr><tr><td>Highschool 2012</td><td>0.69</td><td>0.49</td><td>0.60</td></tr><tr><td>Primary school</td><td>0.62</td><td>0.28</td><td>0.41</td></tr><tr><td>College msg</td><td>0.88</td><td>0.89</td><td>0.93</td></tr><tr><td>Highschool 2013</td><td>0.64</td><td>0.43</td><td>0.50</td></tr><tr><td>Email EU</td><td>0.84</td><td>0.80</td><td>0.84</td></tr><tr><td>Wiki elections</td><td>0.77</td><td>0.77</td><td>0.98</td></tr><tr><td>Digg reply</td><td>0.98</td><td>0.98</td><td>0.99</td></tr><tr><td>Facebook wall</td><td>0.96</td><td>0.97</td><td>0.99</td></tr><tr><td>Infectious</td><td>0.75</td><td>0.77</td><td>0.83</td></tr><tr><td>Slashdot reply</td><td>0.94</td><td>0.95</td><td>0.99</td></tr><tr><td>SMS</td><td>0.86</td><td>0.86</td><td>0.99</td></tr></tbody></table>

<table><thead><tr><th rowspan="3">Network</th><th colspan="3">Weighted Kendall's τ</th></tr><tr><th colspan="2">Sh</th><th>SFa</th></tr><tr><th>SFa</th><th>SFo</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>0.86</td><td>0.71</td><td>0.74</td></tr><tr><td>Hospital ward</td><td>0.83</td><td>0.78</td><td>0.79</td></tr><tr><td>Highschool 2011</td><td>0.80</td><td>0.64</td><td>0.63</td></tr><tr><td>Highschool 2012</td><td>0.80</td><td>0.63</td><td>0.71</td></tr><tr><td>Primary school</td><td>0.75</td><td>0.35</td><td>0.53</td></tr><tr><td>College msg</td><td>0.95</td><td>0.96</td><td>0.96</td></tr><tr><td>Highschool 2013</td><td>0.81</td><td>0.66</td><td>0.68</td></tr><tr><td>Email EU</td><td>0.93</td><td>0.90</td><td>0.92</td></tr><tr><td>Wiki elections</td><td>0.96</td><td>0.97</td><td>0.99</td></tr><tr><td>Digg reply</td><td>1.00</td><td>1.00</td><td>1.00</td></tr><tr><td>Facebook wall</td><td>0.99</td><td>0.99</td><td>1.00</td></tr><tr><td>Infectious</td><td>0.91</td><td>0.92</td><td>0.94</td></tr><tr><td>Slashdot reply</td><td>0.99</td><td>0.99</td><td>1.00</td></tr><tr><td>SMS</td><td>0.98</td><td>0.98</td><td>1.00</td></tr></tbody></table>

<table><caption>Table 20: $\beta = \infty$ and Kendall, weighted Kendall, and intersection correlation</caption><thead><tr><th rowspan="3">Network</th><th colspan="3">Intersection top-50</th></tr><tr><th colspan="2">Sh</th><th>SFa</th></tr><tr><th>SFa</th><th>SFo</th><th>SFo</th></tr></thead><tbody><tr><td>Hypertext 2009</td><td>40</td><td>37</td><td>38</td></tr><tr><td>Hospital ward</td><td>42</td><td>44</td><td>44</td></tr><tr><td>Highschool 2011</td><td>43</td><td>32</td><td>32</td></tr><tr><td>Highschool 2012</td><td>38</td><td>31</td><td>34</td></tr><tr><td>Primary school</td><td>35</td><td>15</td><td>23</td></tr><tr><td>College msg</td><td>44</td><td>42</td><td>42</td></tr><tr><td>Highschool 2013</td><td>36</td><td>27</td><td>27</td></tr><tr><td>Email EU</td><td>42</td><td>38</td><td>41</td></tr><tr><td>Wiki elections</td><td>39</td><td>41</td><td>42</td></tr><tr><td>Digg reply</td><td>48</td><td>49</td><td>48</td></tr><tr><td>Facebook wall</td><td>45</td><td>46</td><td>47</td></tr><tr><td>Infectious</td><td>35</td><td>40</td><td>41</td></tr><tr><td>Slashdot reply</td><td>48</td><td>47</td><td>49</td></tr><tr><td>SMS</td><td>47</td><td>48</td><td>48</td></tr></tbody></table>
<table><caption>Table 21: $\beta$ = 300 and Kendall, weighted Kendall, and intersection correlation</caption><thead><tr><th rowspan="3">Network</th><th colspan="10">Kendall's τ</th></tr><tr><th colspan="4">Fa</th><th colspan="4">Fo</th><th colspan="2">Sh</th><th>SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFo</th><th>SFa</th></tr></thead><tbody><tr><td>Kuopio</td><td>0.83</td><td>0.88</td><td>0.93</td><td>0.85</td><td>0.77</td><td>0.80</td><td>0.89</td><td>0.93</td><td>0.83</td><td>0.86</td></tr><tr><td>Venice</td><td>0.88</td><td>0.88</td><td>0.93</td><td>0.87</td><td>0.82</td><td>0.84</td><td>0.88</td><td>0.94</td><td>0.90</td><td>0.91</td></tr><tr><td>Bordeaux</td><td>0.76</td><td>0.87</td><td>0.95</td><td>0.81</td><td>0.72</td><td>0.75</td><td>0.87</td><td>0.90</td><td>0.79</td><td>0.81</td></tr><tr><td>Berlin</td><td>0.64</td><td>0.63</td><td>0.89</td><td>0.70</td><td>0.44</td><td>0.59</td><td>0.80</td><td>0.69</td><td>0.55</td><td>0.69</td></tr><tr><td>Rome</td><td>0.74</td><td>0.75</td><td>0.95</td><td>0.77</td><td>0.62</td><td>0.72</td><td>0.85</td><td>0.79</td><td>0.71</td><td>0.78</td></tr><tr><td>Paris</td><td>0.88</td><td>0.88</td><td>0.97</td><td>0.90</td><td>0.81</td><td>0.87</td><td>0.93</td><td>0.90</td><td>0.86</td><td>0.90</td></tr></tbody><thead><tr><th rowspan="3">Network</th><th colspan="10">Weighted Kendall's τ</th></tr><tr><th colspan="4">Fa</th><th colspan="4">Fo</th><th colspan="2">Sh</th><th>SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFo</th><th>SFa</th></tr></thead><tbody><tr><td>Kuopio</td><td>0.90</td><td>0.94</td><td>0.97</td><td>0.91</td><td>0.87</td><td>0.88</td><td>0.93</td><td>0.96</td><td>0.91</td><td>0.92</td></tr><tr><td>Venice</td><td>0.95</td><td>0.94</td><td>0.96</td><td>0.94</td><td>0.91</td><td>0.92</td><td>0.93</td><td>0.97</td><td>0.96</td><td>0.97</td></tr><tr><td>Bordeaux</td><td>0.89</td><td>0.94</td><td>0.98</td><td>0.92</td><td>0.88</td><td>0.88</td><td>0.94</td><td>0.96</td><td>0.93</td><td>0.93</td></tr><tr><td>Berlin</td><td>0.86</td><td>0.87</td><td>0.96</td><td>0.90</td><td>0.72</td><td>0.76</td><td>0.88</td><td>0.89</td><td>0.85</td><td>0.90</td></tr><tr><td>Rome</td><td>0.89</td><td>0.90</td><td>0.98</td><td>0.92</td><td>0.81</td><td>0.86</td><td>0.92</td><td>0.92</td><td>0.90</td><td>0.92</td></tr><tr><td>Paris</td><td>0.93</td><td>0.95</td><td>0.99</td><td>0.96</td><td>0.88</td><td>0.91</td><td>0.94</td><td>0.95</td><td>0.94</td><td>0.96</td></tr></tbody><thead><tr><th rowspan="3">Network</th><th colspan="10">Intersection top-100</th></tr><tr><th colspan="4">Fa</th><th colspan="4">Fo</th><th colspan="2">Sh</th><th>SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFo</th><th>SFa</th></tr></thead><tbody><tr><td>Kuopio</td><td>62</td><td>88</td><td>94</td><td>74</td><td>60</td><td>59</td><td>72</td><td>92</td><td>76</td><td>75</td></tr><tr><td>Venice</td><td>82</td><td>78</td><td>82</td><td>79</td><td>69</td><td>70</td><td>71</td><td>91</td><td>90</td><td>88</td></tr><tr><td>Bordeaux</td><td>55</td><td>72</td><td>92</td><td>74</td><td>54</td><td>53</td><td>67</td><td>76</td><td>81</td><td>78</td></tr><tr><td>Berlin</td><td>69</td><td>69</td><td>90</td><td>88</td><td>51</td><td>65</td><td>65</td><td>75</td><td>78</td><td>90</td></tr><tr><td>Rome</td><td>56</td><td>60</td><td>83</td><td>66</td><td>41</td><td>46</td><td>62</td><td>70</td><td>67</td><td>70</td></tr><tr><td>Paris</td><td>50</td><td>69</td><td>94</td><td>79</td><td>41</td><td>47</td><td>54</td><td>70</td><td>71</td><td>83</td></tr></tbody></table>
<table><caption>Table 22: $\beta$ = 600 and Kendall, weighted Kendall, and intersection correlation</caption><thead><tr><th rowspan="3">Network</th><th colspan="10">Kendall's τ</th></tr><tr><th colspan="4">Fa</th><th colspan="4">Fo</th><th colspan="2">Sh</th><th>SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFo</th><th>SFa</th></tr></thead><tbody><tr><td>Kuopio</td><td>0.80</td><td>0.82</td><td>0.93</td><td>0.83</td><td>0.71</td><td>0.76</td><td>0.85</td><td>0.87</td><td>0.78</td><td>0.83</td></tr><tr><td>Venice</td><td>0.85</td><td>0.82</td><td>0.91</td><td>0.84</td><td>0.75</td><td>0.81</td><td>0.85</td><td>0.88</td><td>0.84</td><td>0.88</td></tr><tr><td>Bordeaux</td><td>0.75</td><td>0.75</td><td>0.95</td><td>0.80</td><td>0.63</td><td>0.73</td><td>0.86</td><td>0.78</td><td>0.71</td><td>0.80</td></tr><tr><td>Berlin</td><td>0.64</td><td>0.57</td><td>0.89</td><td>0.70</td><td>0.40</td><td>0.59</td><td>0.78</td><td>0.63</td><td>0.52</td><td>0.70</td></tr><tr><td>Rome</td><td>0.75</td><td>0.64</td><td>0.95</td><td>0.76</td><td>0.55</td><td>0.73</td><td>0.85</td><td>0.67</td><td>0.64</td><td>0.77</td></tr><tr><td>Paris</td><td>0.89</td><td>0.83</td><td>0.97</td><td>0.89</td><td>0.79</td><td>0.88</td><td>0.93</td><td>0.85</td><td>0.83</td><td>0.90</td></tr></tbody><thead><tr><th rowspan="3">Network</th><th colspan="10">Weighted Kendall's τ</th></tr><tr><th colspan="4">Fa</th><th colspan="4">Fo</th><th colspan="2">Sh</th><th>SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFo</th><th>SFa</th></tr></thead><tbody><tr><td>Kuopio</td><td>0.88</td><td>0.91</td><td>0.96</td><td>0.90</td><td>0.84</td><td>0.86</td><td>0.91</td><td>0.93</td><td>0.89</td><td>0.90</td></tr><tr><td>Venice</td><td>0.93</td><td>0.90</td><td>0.95</td><td>0.93</td><td>0.86</td><td>0.89</td><td>0.91</td><td>0.94</td><td>0.93</td><td>0.95</td></tr><tr><td>Bordeaux</td><td>0.89</td><td>0.90</td><td>0.98</td><td>0.92</td><td>0.84</td><td>0.89</td><td>0.94</td><td>0.91</td><td>0.89</td><td>0.93</td></tr><tr><td>Berlin</td><td>0.86</td><td>0.84</td><td>0.96</td><td>0.90</td><td>0.68</td><td>0.75</td><td>0.86</td><td>0.87</td><td>0.84</td><td>0.91</td></tr><tr><td>Rome</td><td>0.90</td><td>0.85</td><td>0.98</td><td>0.91</td><td>0.75</td><td>0.88</td><td>0.93</td><td>0.87</td><td>0.86</td><td>0.92</td></tr><tr><td>Paris</td><td>0.95</td><td>0.92</td><td>0.99</td><td>0.96</td><td>0.89</td><td>0.94</td><td>0.96</td><td>0.93</td><td>0.93</td><td>0.97</td></tr></tbody><thead><tr><th rowspan="3">Network</th><th colspan="10">Intersection top-100</th></tr><tr><th colspan="4">Fa</th><th colspan="4">Fo</th><th colspan="2">Sh</th><th>SFa</th></tr><tr><th>Fo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>Sh</th><th>SFa</th><th>SFo</th><th>SFa</th><th>SFo</th><th>SFo</th><th>SFa</th></tr></thead><tbody><tr><td>Kuopio</td><td>67</td><td>89</td><td>96</td><td>79</td><td>64</td><td>66</td><td>75</td><td>91</td><td>76</td><td>79</td></tr><tr><td>Venice</td><td>80</td><td>68</td><td>78</td><td>73</td><td>58</td><td>66</td><td>68</td><td>87</td><td>82</td><td>83</td></tr><tr><td>Bordeaux</td><td>71</td><td>71</td><td>97</td><td>85</td><td>61</td><td>70</td><td>74</td><td>74</td><td>72</td><td>84</td></tr><tr><td>Berlin</td><td>73</td><td>63</td><td>91</td><td>85</td><td>51</td><td>70</td><td>67</td><td>67</td><td>71</td><td>92</td></tr><tr><td>Rome</td><td>58</td><td>50</td><td>87</td><td>65</td><td>35</td><td>48</td><td>65</td><td>54</td><td>55</td><td>74</td></tr><tr><td>Paris</td><td>71</td><td>60</td><td>95</td><td>83</td><td>47</td><td>68</td><td>76</td><td>61</td><td>60</td><td>83</td></tr></tbody></table>