# Finding Top-\(k\) Nodes for Temporal Closeness in Large Temporal Graphs
## 5 Experimental Results
### Accuracy  
In this section, we analyze the accuracy of the estimation performed by apx-\(h\) for different \(h\). To this aim, we consider the following measures. * Mean Absolute Error (MAE) in each experiment. Namely, for each experiment, we compute \(\sum_{p}|C^{X}(u)-C(u)|/n\), where \(X\) is the sample of size \(h\) randomly chosen by apx-\(h\). This is guaranteed to be bounded with high probability (see Theorem 3). * Relative Error (RE), which is defined, for a given node \(u\) and for a given sample \(X\), as \(|C^{X}(u)-C(u)|/C(u)\). We show that, even though we do not have any theoretical guarantee on this error, it is very low when considering nodes which are in the top of the ranking, while it gets bigger for peripheral nodes. **MAE as a function of the sample size. ** Figure 4 shows the behaviour of MAE as a function of the sample size, through box-and-whisker plots, where for each graph, and for each \(h\) (\(X\)-axis), the \(Y\)-axis reports the median (and also minimum, maximum, first and third quartiles) among 50 experiments of the MAEs obtained by running apx-\(h\). For the sake of brevity, we show here just the plots for the graphs come, fbwa, and melb (the behaviour is similar for the other graphs). Clearly, the scale is different due to the different values of the closeness centrality of each graph. For the sake of completeness we report the average closeness of come, fbwa, and melb, which is, respectively \(6.1\cdot 10^{-4}\), \(5.4\cdot 10^{-9}\), and \(2.5\cdot 10^{-5}\). As expected, when increasing the sample size \(h\), the MAE gets consistently lower. In particular, this applies to the median but also to the variability, as we see that the window between the minimum and maximum and also the one between the quartiles reduces. In the case of \(h=1024\), if we compare the median of the MAEs with the corresponding average values of closeness for the three graphs we get an error of 8%, 4%, and 6%. **RE as a function of the ranking. ** We now show that the behaviour of the RE of apx-\(h\) for all the nodes of each graph depends on their ranking. In particular, given a temporal graph with \(n\) nodes, let \(r\) be the ranking computed by exact and let \(r(i)\), for any \(i\) with \(1\leq i\leq n\), be the node \(v\) having position \(i\) in the ranking \(r\) (smaller \(i\) means higher closeness). For each \(i\), we compute the mean and the maximum RE over 50 experiments of apx-\(h\) when estimating the closeness of the node \(v=r(i)\): in the following, we denote by \(\mu\text{RE}(i)\) and \(\text{mRE}(i)\) these two values. Figure 5 reports, for each ranking position \(i\), the maximum \(\mu\text{RE}(i)\) and \(\text{mRE}(i)\) of apx-1024 among all the nodes with position up to \(i\), for the graphs come, fbwa, and melb (from top to bottom). More specifically, the black plots depict the behavior of \(\max_{1\leq j\leq i}\mu\text{RE}(j)\), while the red dashed plots depict the behavior of \(\max_{1\leq j\leq i}\text{mRE}(j)\). As can be seen, both the \(\mu\text{RE}(i)\) and \(\text{mRE}(i)\) are very small for nodes having high closeness value (thus low ranks), while they are larger for nodes having a lower closeness value (thus high ranks). This behavior is quite natural as nodes having lower closeness are less often \"backward\" reachable from the sample and their closeness is often estimated as zero, or whenever they are \"backward\" reached by the sample, their closeness is then overestimated. This induces a higher variability in general for their estimation. On the other hand, nodes having higher values of closeness behave more stably with respect to the chosen sample, leading to better estimation. The overall good results are shown by this experiment suggest that apx-\(h\) is able to give a very good estimation for the top-\(k\) nodes, i.e., the \(k\) nodes having higher closeness for a given constant \(k\) (see also Table 15 in the Appendix A, which shows the difference between the average RE of the top-100 nodes and of the other nodes, with respect to different sizes of the sample).