# Approximating the Temporal Neighbourhood Function of Large Temporal Graphs
## 4 Experimental Results
### Quality of the Approximation  
In order to evaluate the quality of the approximation, for each \(\mathbb{I}=[t_{\alpha},t_{\beta}]\), we have compared the approximation \(\overline{|\mathcal{N}(\mathbb{I})|}\) provided by atnf with respect to the exact value \(|\mathcal{N}(\mathbb{I})|\) provided by etnf,  
\begin{table}
\begin{tabular}{l r r} \hline \hline \multicolumn{3}{c}{**Undirected Graphs**} \\ \hline _Name_ & _Nodes_ & _Edges_ \\ \hline TOPOLOGY & 34,761 & 154,842 \\ ROLLERNET & 63 & 403,834 \\ \hline \hline \multicolumn{3}{c}{IMDB-} \\ \hline ADVENTURE & 47,763 & 157,492 \\ HOROROR & 65,338 & 167,026 \\ THILLER & 69,753 & 188,862 \\ CRIME & 62,050 & 216,741 \\ ROMANCE & 79,227 & 305,390 \\ ACTION & 72,260 & 338,815 \\ COMEDY & 162,303 & 666,568 \\ DRAMA & 279,059 & 1,342,886 \\ all & 527,535 & 3,152,994 \\ \hline \hline \multicolumn{3}{c}{**Directed Graphs**} \\ \hline _Name_ & _Nodes_ & _Edges_ \\ ENRON & 150 & 24,705 \\ COLLEGE & 1900 & 59,834 \\ Wiki-ELECTION & 7118 & 103,675 \\ facebook-wallpost & 46,952 & 876,993 \\ twitter & 3,511,241 & 16,438,790 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Number of nodes and edges of each (undirected or directed) graph.  
using the relative error. We have hence considered the mean relative error (in short, mre) among all the intervals \(\mathbb{I}=[t_{\alpha},t_{\beta}]\) for all values of \(t_{\beta}\) in \(\mathcal{T}(G)\). More formally, the mre is defined as follows:  
\[\textsc{mre}=\frac{1}{|\mathcal{T}(G)|}\sum_{t_{\beta}\in\mathcal{T}(G)}\frac{ \|\mathcal{N}([t_{\alpha},t_{\beta}])\|-|\mathcal{N}([t_{\alpha},t_{\beta}]) |}{|\mathcal{N}([t_{\alpha},t_{\beta}])|}.\]  
For each \(k\in\{2,4,8,16,32,64,128\}\), we have repeated the experiments ten times, and we have reported our results in Table 3. In this table, for each \(k\), we have reported the average mre, denoted as \(\mu\), and the standard deviation, denoted as \(\sigma\), over the ten experiments (note that both \(\mu\) and \(\sigma\) are 0 for the rollernet network, whenever \(k\geq 64\), since the graph has less than 64 nodes and hence atnf turns out to always compute the exact values).  
In general, both \(\mu\) and \(\sigma\) consistently decrease while increasing \(k\). For \(k=2\), 4, and 8, the average mre appears to be quite large: for \(k=2\), the mre can be up to 50%, and, for \(k=8\), the mre can be close to 20%. By increasing \(k\) to 16, we get an average mre consistently smaller than 17%, which further reduces with \(k=32\) and \(k=64\), where, in both of the cases, the average mre is very often below 8%. Finally, for \(k=128\), the average mre appears to be always smaller than 5.3%. For the sake of completeness, looking at the values of \(\sigma\), we can observe how the variability of the experiments is more controlled when \(k\) increases.  
Note that, in the table, the imdb-all and twitter networks are missing since, according to our estimate and as shown in the next section, etnf would have taken more than one week for the first and more than 190 days for the second to complete. Hence, for these two graphs, no quality comparison was possible.