# Approximating the Temporal Neighbourhood Function of Large Temporal Graphs
## 3 Computing Temporal Neighborhood Functions through Reverse Temporal Cones  
As we already said, in this paper, we consider the _left-to-right_ order for reading the stream of temporal edges, which corresponds to reading the edges in non-decreasing order with respect to their appearing times. **Definition 4**. : _Given a temporal graph \(G=(V,E)\) and a time instant \(t\in\mathcal{T}(G)\), the **predecessor**\(\mathtt{pred}(t)\) of \(t\) in \(G\) is the maximum time instant \(t^{\prime}\in\mathcal{T}(G)\) such that \(t^{\prime}<t\) (if \(t^{\prime}\) does not exist, then we set \(\mathtt{pred}(t)=\bot\))._  
For example, by referring to the temporal graph of Figure 2, \(\mathtt{pred}(1)=\bot\), \(\mathtt{pred}(9)=8\), and \(\mathtt{pred}(11)=9\). Observe that, if \(\mathbb{I}=[t_{\alpha},t_{\omega}]\) and \(\mathtt{pred}(t_{\omega})\
eq\bot\), then \(\mathcal{N}(\mathbb{I})-\mathcal{N}([t_{\alpha},\mathtt{pred}(t_{\omega})])\) contains exactly all pairs of nodes \((u,v)\) such that any earliest arrival path \(\mathbb{P}\) from \(u\) to \(v\) satisfies \(\eta(\mathbb{P})=t_{\omega}\). In order to compute the temporal neighborhood function of a temporal graph \(G\) in a given time interval \([t_{\alpha},t_{\omega}]\), we first introduce the following definition. **Definition 5**. : _Given a temporal graph \(G=(V,E)\), a node \(u\), and a time interval \(\mathbb{I}=[t_{\alpha},t_{\omega}]\), the **reverse temporal cone** of \(u\) in the interval \(\mathbb{I}\) is defined as \(\mathcal{R}(u,\mathbb{I})=\{v\in V:\mathcal{P}(v,u,\mathbb{I})\
eq\emptyset\}\)._  
In other words, the reverse temporal cone of \(u\) in the interval \(\mathbb{I}\) contains all nodes \(v\) that can reach \(u\) in \(\mathbb{I}\) (hence, if \(v\in\mathcal{R}(u,\mathbb{I})\), then \(u\in\mathcal{C}(v,\mathbb{I})\)). The advantage of referring to reverse temporal cones is that these cones can be easily computed by using the following dynamic programming algorithm (observe that, for any \(t\in\mathcal{T}(G)\), \(\mathcal{C}(u,[t,t])\) is the neighborhood of \(u\) at time \(t\), that is, the set of nodes \(v\) such that \((u,v,t)\in E\)). **Base case**: \(\mathcal{R}(u,[t_{\alpha},t_{\alpha}])=\{u\}\cup\{v\in V:u\in\mathcal{C}(v,[t _{\alpha},t_{\alpha}])\}\). **Recursive step**: Let \(t\in\mathcal{T}(G)\) with \(t>t_{\alpha}\) and suppose we have computed \(\mathcal{R}(u,[t_{\alpha},t^{\prime}])\) for every \(t^{\prime}<t\) with \(t^{\prime}\in\mathcal{T}(G)\). Then, \(\mathcal{R}(u,[t_{\alpha},t])=\mathcal{R}(u,[t_{\alpha},\mathtt{pred}(t)]) \cup\bigcup_{v:u\in\mathcal{C}(v,[t,t])}\mathcal{R}(v,[t_{\alpha},\mathtt{ pred}(t)])\). The base case simply states that, if there is an edge \((v,u,t_{\alpha})\), then \(v\) belongs to the reverse temporal cone of \(u\) in the interval \([t_{\alpha},t_{\alpha}]\). The recursive step, instead, says that, if there is an edge \((v,u,t)\), then all nodes that could reach \(v\) before \(t\) can now also reach \(u\) at time \(t\). For example, by referring to the temporal graph of Figure 2 (in which all edges are bidirectional), Table 1 shows the evolution of the reverse temporal cones \(\mathcal{R}(u,[1,6])\) according to the above algorithm (until all nodes are reachable from all other nodes). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \((u,v,t)\) & \(\mathcal{R}(1,[1,6])\) & \(\mathcal{R}(2,[1,6])\) & \(\mathcal{R}(3,[1,6])\) & \(\mathcal{R}(4,[1,6])\) & \(\mathcal{R}(5,[1,6])\) \\ \hline \((1,4,1)\) & \(\{1,4\}\) & \(\{2\}\) & \(\{3\}\) & \(\{1,4\}\) & \(\Let us assume that the set of temporal edges of a temporal graph \(G=(V,E)\) is ordered in non-decreasing order with respect to the appearing times, and that edges are not bidirectional. Let \(\overrightarrow{E}=(e_{\overrightarrow{1}},e_{\overrightarrow{2}},\ldots,e_{ \overrightarrow{m}})\) be the resulting ordered set of temporal edges, so that the appearing time of \(e_{\overrightarrow{i}}\) is not greater than the appearing time of \(e_{\overrightarrow{i+1}}\), for any \(i\) with \(1\leq i<m\).