# Approximating the Temporal Neighbourhood Function of Large Temporal Graphs
## 4 Experimental Results
### Running Time and Time Comparison with Respect to etnf  
Table 4 reports the average running time (in milliseconds) of atnf and of etnf, respectively, to get the approximate and the exact value of \(|\mathcal{N}(\mathbb{I})|\) for each \(\mathbb{I}=[t_{\alpha},t_{\beta}]\). Increasing the value of \(k\), the running time of atnf increases consistently (as also the quality of the approximation). In the case of bigger graphs,  
\begin{table}
\begin{tabular}{c c c c c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Graph**} & \multicolumn{10}{c}{**MRE of atnf**} \\ \cline{2-13}  & \multicolumn{2}{c}{\(k=2\)} & \multicolumn{2}{c}{\(k=4\)} & \multicolumn{2}{c}{\(k=8\)} & \multicolumn{2}{c}{\(k=16\)} & \multicolumn{2}{c  
the running time of atnf is orders of magnitude smaller with respect to the one of etnf (rightmost column). We have highlighted this improvement in Table 5, where we have shown the ratio between the running time of atnf and the one of etnf. Concerning the smaller graphs, like rollernet and enron, which have respectively 63 and 150 nodes, we have observed that atnf turns to be exact if \(k\) is set to a value greater than this number of nodes. In the case of rollernet, it is interesting to note that the dynamic programming algorithm (which, hence, is exact for \(k=64\) or 128) is strictly faster than the BFS approach implemented by etnf. On the other hand, as in the case of enron, the running time of atnf, although not exact, can be sometimes worse than the one of etnf whenever the graph has few nodes. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Graph**} & \multicolumn{8}{c}{**Running Time of atnf**} & \multicolumn{2}{c}{**Running Time of etnf**} \\ \cline{2-9}  & \(k=2\) & \(k=4\) & \(k=8\) & \(k=16\) & \(k=32\) & \(k=64\) & \(k=128\) \\ \hline TOPOLOGY & 2419.4 & 2428.7 & 2547.8 & 2937.4 & 4700.3 & 9892.4 & 31,295.7 & 1,715,090 \\ rollernet & 498.9 & 740.8 & 1066.5 & 1759.2 & 4079.3 & 1040.3 & 956.2 & 7636 \\ enron & 70.2 & 34.2 & 75.1 & 131.4 & 262.9 & 822.9 & 1201.5 & 1172 \\ COLLEGE & 93.5 & 120.9 & 170.7 & 312.5 & 992.9 & 3010.1 & 9468.7 & 32,394 \\ wiki-election & 142.1 & 178.3 & 329.9 & 611.8 & 1478 & 4763 & 16,811.1 & 202,519 \\ FACEBOOK-wallpost & 1542.7 & 2376.9 & 3256.9 & 6188.5 & 17,152.6 & 56,847.8 & 172,628.4 & 12,469,653 \\ IMDB-ADVENTURE & 232.9 & 307.2 & 348.4 & 472.2 & 967.8 & 2428.8 & 6925.5 & 2,125,739 \\ IMDB-HORRO & 393.6 & 424.7 & 417.4 & 468.1 & 730.5 & 1352.1 & 3239.2 & 3,039,487 \\ IMDB-THILLER & 460.5 & 473.4 & 504.9 & 586.5 & 1065.6 & 2517.1 & 6549.6 & 3821,616 \\ IMDB-CHME & 383.1 & 402.6 & 477.0 & 628.6 & 1315.3 & 3230.9 & 9455.8 & 3,745,721 \\ IMDB-ROMANCE & 704.2 & 758.8 & 873.6 & 1196.2 & 2160.6 & 5773.4 & 16,980.6 & 7,046,556 \\ IMDB-ACTION & 865.7 & 927.5 & 1014.8 & 1243.6 & 2645.3 & 6060.7 & 18,109.9 & 7,079,857 \\ IMDB-CODDY & 2825.3 & 3033.0 & 3057.8 & 4075.4 & 7131.3 & 15,709.5 & 4,2579.4 & 31,806,022 \\ IMDB-DRAMA & 9619.7 & 9923.5 & 11,022.8 & 13,050.7 & 19,975.2 & 38,993.5 & 101,945 & 113,236,400 \\ IMDB-all & 39,671.1 & 40,273.2 & 41,582.4 & 44,120.5 & 55,290.4 & 91,824.0 & 212,132.1 & \({}^{\dagger}\)622,185,999 \\ twitter & 31,892.7 & 40,758.1 & 61,724.0 & 135,468.9 & 424,497.6 & 1,325,115.7 & 4,222,861.0 & \({}^{\dagger}\)25,771,840,132 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Running times (milliseconds) of atnf for different values of \(k\) compared with the running time of etnf. The numbers marked with \(\dagger\) are estimated due to the computation limits of etnf.