# Approximating the Temporal Neighbourhood Function of Large Temporal Graphs
## 4 Experimental Results
### Running Time and Time Comparison with Respect to etnf
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Graph**} & \multicolumn{8}{c}{**Running Time of atnf over Running Time of etnf**} \\ \cline{2-9}  & \(k=2\) & \(k=4\) & \(k=8\) & \(k=16\) & \(k=32\) & \(k=64\) & \(k=128\) \\ \hline TOPOLOGY & 0.00141 & 0.00142 & 0.00149 & 0.00171 & 0.00274 & 0.00577 & 0.01825 \\ rollernet & 0.06534 & 0.09701 & 0.13967 & 0.23038 & 0.53422 & 0.13624 & 0.12522 \\ enron & 0.05990 & 0.02918 & 0.06408 & 0.11212 & 0.22432 & 0.70213 & 1.02517 \\ COLLEGE & 0.00289 & 0.00373 & 0.00527 & 0.00965 & 0.03065 & 0.09292 & 0.29230 \\ Wiki-election & 0.00070 & 0.00088 & 0.00163 & 0.00302 & 0.00730 & 0.02352 & 0.08301 \\ FACEBOOK-wallpost & 0.00012 & 0.00019 & 0.00026 & 0.00050 & 0.00138 & 0.00456 & 0.01384 \\ IMDB-ADVENTURE & 0.00011 & 0.00014 & 0.00016 & 0.00022 & 0.00046 & 0.00114 & 0.00326 \\ IMDB-HORRO & 0.00013 & 0.00014 & 0.00014 & 0.00015 & 0.00024 & 0.00044 & 0.00107 \\ IMDB-THILLER & 0.00012 & 0.00012 & 0.00013 & 0.00015 & 0.00028 & 0.00066 & 0.00171 \\ IMDB-crime & 0.00010 & 0.00011 & 0.00013 & 0.00017 & 0.00035 & 0.00086 & 0.00252 \\ IMDB-ROMANCE & 0.00010 & 0.00011 & 0.0012 & 0.00017 & 0.00031 & 0.00082 & 0.00241 \\ IMDB-action & 0.00012 & 0.00013 & 0.00014 & 0.00018 & 0.00037 & 0.00086 & 0.00256 \\ IMDB-CODDY & 0.00009 & 0.00010 & 0.00010 & 0.00013 & 0.00022 & 0.00049 & 0.00134 \\ IMDB-DRAMA & 0.00008 & 0.00009 & 0.00010 & 0.00012 & 0.00018 & 0.00034 & 0.00090 \\ IMDB-all\({}^{\ddagger}\) & 0.00006 & 0.00006 & 0.00007 & 0.00007 & 0.00009 & 0.00015 & 0.00034 \\ twitter\({}^{\ddagger}\) & 1.2\(\cdot 10^{-6}\) & 1.6\(\cdot 10^{-6}\) & 2.4\(\cdot 10^{-6}\) & 5.2\(\cdot 10^{-6}\) & 0.00002 & 0.00005 & 0.00016 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Ratio between the running time of atnf and the one of etnf for different values of \(k\) (lower is better). The values for the graphs marked with \({}^{\ddagger}\) are estimated due to the computational limits of etnf. In the general case, running atnf with \(k=128\), and thus getting an average mre below 5.3% (as we have seen in the previous section), the running time of atnf is very often below 0.3% the running time of etnf. This improvement is even more striking for bigger graphs, where the running time of atnf further reduces to 0.1%. For the two biggest graphs, i.e., imdb-all and twitter, we were not able to run etnf, due to the large amount of time required by the method. For this reason, we have estimated its running time (reported with \(\dagger\) in Table 4). The estimation is based on the fact that etnf runs \(n\) single-source procedures, each one from a different source node. It is possible to estimate the average running time \(\mu\) of a single-source procedure, sampling \(\Theta(\frac{logn}{e^{2}})\) sources and computing the average time \(\overline{\mu}\). It is easy to show that this is an unbiased estimator and that, by using the [PERSON]'s inequality, \(|\mu-\overline{\mu}|\) is bounded with high probability by \(\epsilon\cdot r\), where \(r\) is an upper bound on the maximum time needed by a single-source procedure, e.g., the time for visiting all the edges. By multiplying \(\overline{\mu}\) by \(n\), we get an estimation of the running time of etnf. We have verified experimentally that the order of magnitude reported by our estimation is consistent with the actual time used by etnf for the smaller graphs. As a result, applying our estimation for the biggest graphs, since a single-source procedure requires on average 1.18 s for imdb-all and 7.33 s for twitter, with relative standard deviation, respectively, of 17.49% and 10.87%, etnf requires 622,185 s (more than a week) for imdb-all and 25,771,840 s (more than 198 days) for twitter. On the other hand, setting \(k=128\), atnf is able to approximate \(|\mathcal{N}(\mathbb{I})|\) in only 112 s for the former graphs and in 71 min for the latter one, as shown in Table 4. Comparing these running times with our estimates (last two rows of Table 5), atnf turns out to be four orders of magnitude faster than etnf.