# Approximating the Temporal Neighbourhood Function of Large Temporal Graphs
## 5 Case Study: Comparison of 25 Public Transport Networks  
In this section, we will show how the atnf algorithm for computing the approximation of the temporal neighborhood functions can be applied in order to perform an exhaustive analysis of some reachability properties of several temporal graphs in a very efficient way. In particular, we will make use of a recently published collection of 25 cities' public transport networks [14]. This collection is available in multiple formats including the temporal edge list for a specific day, which is the format we use here. The list of the 25 cities is summarized in Table 6, where, for each city, we provide the number of stops (that is, the number of vertices of the temporal graph), the number of temporal edges, the day in which the data were collected, and the radius \(R\) around the city's central point that should cover all the continuous and dense parts of the city and its public transport network [14]. We have grouped the 25 cities into five groups according to the vale of \(R\). In particular, group \(i\) contains all the cities such that \(10(i-1)<R\leq 10i\), for \(1\leq i\leq 5\). Our goal is to analyze the _reachability efficacy_ of each public transport network. To this aim, we compute the (approximate) value of the temporal neighborhood functions corresponding to different time intervals of the day in which the data were collected. In particular, we divide the interval between 6:00 a.m. and 9:00 p.m. into 30, 15, and 10 intervals of length 30, 60, and 90 min, respectively. For each interval \(\mathbb{I}=[t_{\alpha},t_{\omega}]\), we compute the approximate value of the temporal neighborhood function \(|\mathcal{N}(\mathbb{I})|\) (normalized with respect to the number of all possible pairs of nodes), by using the atnf algorithm. In the following, we will represent the distributions of these values by _reachability diagrams_ such as the one shown in Figure 5, which refers to the city of Adelaide. Observe that, in the case of transport networks, going from one stop to another, i.e., following an edge, takes some time. Therefore, in our dataset, the temporal edge list contains the starting time \(s_{e}\) and the arrival time \(a_{e}\) of each temporal edge \(e\) between two nodes \(u\) and \(v\). In order to apply our approach, we have used the following transformation. For each edge \(e\) in the dataset from \(u\) to \(v\) with starting time \(s_{e}\) and arrival time \(a_{e}\), with \(a_{e}-s_{e}>1\), we have replaced \(e\) with a pair of two edges: one from \(u\) to with appearing time \(s_{e}\), and the other from \(z_{e}\) to \(v\) with appearing time \(a_{e}-1\), where \(z_{e}\) is a new dummy node. For the edges \(e\) from \(u\) to \(v\) in the dataset such that \(a_{e}-s_{e}=1\), we replace \(e\) by an edge from \(u\) to \(v\) with appearing time \(s_{e}\). It is easy to show that there is a one-to-one correspondence between the feasible journeys in the original dataset and the sequences induced by the non-dummy nodes in the temporal paths of the resulting temporal graph. Moreover, it is worth remarking that, when computing the temporal neighborhood function in our transformed temporal graph, we have to focus only on non-dummy nodes. To this aim, we have slightly modified our approach in order to exclude the dummy nodes from the sketches of our reverse temporal cones and, hence, not to count them in the final estimation of the temporal neighborhood function. In particular, to do this, in the base case in Section 3, it is enough to exclude \(u\) from \(\mathcal{R}(u,[t_{\alpha},t_{\alpha}])\), whenever \(u\) is a dummy node. In the left column of Figure 6, we show, for each city group, the reachability diagrams of all cities in the group in the case in which we consider intervals of \(60\) min (these diagrams have been obtained by running \(20\) times the approximation algorithm with \(k=64\), and by taking the average values).