# Approximating the Temporal Neighbourhood Function of Large Temporal Graphs
## 3 Computing Temporal Neighborhood Functions through Reverse Temporal Cones
We can then implement the above dynamic programming algorithm by scanning the edges in \(\overrightarrow{E}\) one after the other. For each edge \(e_{\overrightarrow{i}}=(v,u,t)\), if \(t=t_{a}\), then we add \(v\) to \(\mathcal{R}(u,[t_{a},t_{a}])\). Otherwise (that is, \(t>t_{a}\)), we set \(\mathcal{R}(u,[t_{a},t])\) equal to the union of \(\mathcal{R}(u,[t_{a},t])\) and \(\mathcal{R}(v,[t_{a},\texttt{pred}(t)])\), after having initialized \(\mathcal{R}(u,[t_{a},t])\) to \(\mathcal{R}(u,[t_{a},\texttt{pred}(t)])\) the first time an edge appearing at time \(t\) is scanned. Since the size of the intermediate reverse temporal cones can be linear in the number \(n\) of nodes in the graph, the time complexity of this algorithm is \(O(nm)\). Moreover, if we want to maintain all the intermediate reverse temporal cones, then the space complexity of the algorithm is \(O(n^{2}m)\). However, if we just want to compute the final reverse temporal cones, then the space complexity can be reduced to \(O(n^{2})\). Observe that, if the edges are bidirectional, then we can easily modify this algorithm by simply considering twice each edge \((v,u,t)\): once as \((v,u,t)\), and the other as \((u,v,t)\). Once we have computed the reverse temporal cones in a specific interval \(\mathbb{I}\), we can easily compute \(\mathcal{N}(\mathbb{I})\). Indeed, we have that, for each pair of nodes \(u\) and \(v\), \((u,v)\) belongs to \(\mathcal{N}(\mathbb{I})\) if and only if \(u\in\mathcal{R}(v,\mathbb{I})\). This implies that  
\[\left|\mathcal{N}(\mathbb{I})\right|=\sum_{u\in V}\left|\mathcal{R}(u,\mathbb{ I})\right|.\]  
Hence, the temporal neighborhood function can be computed by using the sizes of the reverse temporal cones. **Remark 1**. : _Note that the above dynamic programming approach does not seem to be applicable to the computation of temporal cones, as defined in the previous section. More precisely, it is not clear how to rewrite the recursive step of the algorithm, when referring to temporal cones. Indeed, in general, it holds that_  
\[\mathcal{C}(u,[t_{a},t])\
eq\mathcal{C}(u,[t_{a},\texttt{pred}(t)])\cup\bigcup _{v\in(u,[t,t])}\mathcal{C}(v,[t_{a},\texttt{pred}(t)]),\]  
_since, for each vertex \(v\), \(\mathcal{C}(v,[t_{a},\texttt{pred}(t)])\) is the set of all the vertices reachable from \(v\) through temporal paths which use edge appearing times smaller than \(t\). Hence, \(\mathcal{C}(u,[t_{a},t])\) does not necessarily include the nodes in \(\mathcal{C}(v,[t_{a},\texttt{pred}(t)])\), as the corresponding paths might turn out to be not valid from a temporal point of view. Indeed, the edge from \(u\) to \(v\) appears at time \(t\), but the edges on the paths from \(v\) to other vertices may have appearing times smaller than \(t\). Let us consider, for example, the temporal graph with the three nodes \(1\), \(2\), and \(3\), and the two temporal edges \((1,2,1)\) and \((2,3,2)\). Clearly, \(\mathcal{C}(2,[1,1])=\{1,2\}\) and \(\mathcal{C}(3,[1,1])=\{3\}\). Hence, when the edge \((2,3,2)\) is analyzed, we have that_  
\[\mathcal{C}(3,[1,2])=\{2,3\}\
eq\{1,2,3\}=\mathcal{C}(3,[1,1])\cup\mathcal{C} (2,[1,1]).\]