# Approximating the Temporal Neighbourhood Function of Large Temporal Graphs
## 6 Conclusions  
In this paper, we have proposed a new algorithm for approximating the temporal neighborhood function of a temporal network, which is based on the bottom-\(k\) sketch technique. We have experimentally validated the quality and the time performance of our algorithm, by comparing it with a recently proposed scan-based algorithm. We showed that our algorithm is able to obtain good quality results (typically with  
Figure 8: The reachability diagrams of three sample cities with different values of \(k\).  
Figure 7: The comparison of the reachability diagrams with 30 intervals of 30 min each (**left**), and with 10 intervals of 90 min each (**right**) of the 25 public transport networks.  
a mean relative error of 5% or less) in a very small fraction of the time of the exact algorithm (typically 0.3% or less). Finally, we have applied our algorithm to the analysis of the reachability properties of 25 public transport networks and showed that the neighborhood function gives some non-trivial insight about the number of pairs of stops that are reachable from one another.  
From a more technical point of view, a quite natural and straightforward extension of our work consists of applying other sketch techniques, such as, for example, the ones based on the probabilistic counting approach [7; 8; 38]. We are confident that, by using these other techniques, our results can be improved both in terms of approximation quality and of execution time. A comparison of the different sketch techniques for approximating the temporal neighborhood function is beyond the scope of this paper, whose main goal is showing how these techniques are extremely effective when applied to temporal networks.  
More interestingly, the approach we have described in this paper can also be applied to compute a different kind of temporal cones. Intuitively, these cones would allow us, for each node \(u\) of a temporal graph \(G=(V,E)\), to determine what is the latest starting time from any other node \(v\) that can reach \(u\) in a specified interval \(\mathbb{I}=[t_{a},t_{\omega}]\), in order to arrive at \(u\) not later than \(t_{\omega}\). By appropriately adapting the dynamic programming algorithm for computing the reverse temporal cones, we can show that the latest starting time cones can also be computed in time \(O(nm)\) and space \(O(n^{2}m)\) (or \(O(nm)\) if we do not need to store all the intermediate results). Moreover, in order to improve the efficiency of the algorithm, we can use, even in this case, the bottom-\(k\) sketch technique, exactly as we have done in the case of the reverse temporal cones.  
Finally, a more general question is whether other heuristics can be used in order to compute graph metrics for which the sketch approach does not seem to be very efficient in the case of classical graphs. For example, a promising research direction is to define an analogue of the backward breadth-first search for temporal networks, in order to apply techniques that have been extremely powerful for computing the diameter of a graph [39; 40] or to apply sampling techniques for computing centrality measures in temporal networks [41; 42].  
All authors contributed equally to this work.  
This research was funded in part by the ANR (French National Agency of Research) under grant ANR-15-CE38-0001 (Algodiv), by Thales within the CLEAR SU-Thales joint lab, and by the Ile-de-France program FUI21 under grant 16010629 (iTRAC).  
We thank the anonymous reviewers whose comments helped us to improve this manuscript, in particular for what concerns the way to adapt our algorithm to the case of transportation networks.  
The authors declare no conflict of interest. The funding agents had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript, or in the decision to publish the results.