# Finding Top-\(k\) Nodes for Temporal Closeness in Large Temporal Graphs
## 3 Approximating the Closeness  
In order to approximate the closeness in temporal graphs, we first need to introduce the notion of the latest starting path. To this aim, given a time \(t\in\mathcal{T}(G)\) and two nodes \(u\) and \(v\), we will denote by \(\mathcal{P}^{\leq}(u,v,t)\) the set of all temporal paths \(\mathbb{P}\) from \(u\) to \(v\) such that \(\eta(\mathbb{P})\leq t\). **Definition 4**. : _Given a temporal graph \(G=(V,E)\), two nodes \(u\) and \(v\) in \(V\), and a time \(t\in\mathcal{T}(G)\), a path \(\mathbb{P}\in\mathcal{P}^{\leq}(u,v,t)\) is said to be the latest starting \(t\)-path if \(\sigma(\mathbb{P})=\max\{\sigma(\mathbb{P}^{\prime}):\forall\mathbb{P}^{ \prime}\in\mathcal{P}^{\leq}(u,v,t)\}\)._  
Moreover, we need to define the contribution of a destination node \(d\) to the closeness of another node \(u\). **Definition 5**. : _Given a temporal graph \(G=(V,E)\) and two distinct nodes \(d\) and \(u\), the contribution of \(d\) to the closeness of \(u\) is defined as_  
\[C(u,d)=\frac{1}{t_{\omega}-t_{x}}\int_{t_{x}}^{t_{\omega}}\frac{1}{d_{t}(u,d) }\,\mathrm{d}t.\]  
_By convention, we also set \(C(u,u)=0\), for any node \(u\in V\)._  
We now introduce a sort of backward version of Algorithm 1 (which can be seen as an adaptation of the earliest arrival profile algorithms proposed in [32]), which has to be applied to a destination node \(d\), and that will allows us to compute, for any other node \(x\), the contribution of \(d\) to the closeness of \(x\) (that is, \(C(x,d)\)) and, hence, to adapt to temporal graphs the well-known sampling technique already used in the case of classical graphs. Differently from the case of Algorithm 1, we assume that the temporal edges are scanned in non-increasing order with respect to their appearing times. Once again, we assume that the appearing times of all temporal edges are distinct (we will see in the next section how the algorithm can be adapted to the case in which this assumption is not satisfied), and that the temporal graph is directed (if this not the case, we simply have to examine each edge twice by inverting the source and the destination). The algorithm maintains, for each node \(x\) of \(G\), a triple \(\tau_{x}=(l_{x},r_{x},s_{x})\), which indicates that, for any time instant \(t\) in \([l_{x},r_{x})\), any latest starting \(t\)-path \(\mathbb{P}\) from \(x\) to \(d\) has starting time \(\sigma(\mathbb{P})\) equal to \(s_{x}\) (see Algorithm 2). At the beginning, we do not know anything about the reachability of \(d\) from a node \(x\): hence, we set the starting time of \(x\) equal to \(\infty\) for an arbitrary time interval (for example, \([t_{\omega}+1,t_{\omega}+2)\)) following \(t_{\omega}\) (line 1). When we read a new temporal edge \((x,y,t)\), we first set \(\tau_{d}=\{(t,t+1,t+1)\}\), since, clearly, the destination node can always reach itself even starting after the appearance of the edge (line 2). Let \(\tau_{x}=(l_{x},r_{x},s_{x})\) and \(\tau_{y}=(l_{y},r_{y},s_{y})\) be the two triples associated with \(x\) and \(y\), respectively. If \(l_{x}>l_{y}\), then we add to \(C(x,d)\) the contribution corresponding to the interval \([l_{x},r_{x})\) (line 3) and we update the triple associated with \(x\) by setting \(\tau_{x}=(l_{y},l_{x},t)\) (line 4). This update is justified by Lemma 2. When all temporal edges have been read, for each node \(x\), we add to \(C(x,d)\) the contribution corresponding to the interval \([l_{x},r_{x})\) and to the interval \([t_{\alpha},l_{x})\) (line 5), which are the last intervals for which the latest starting time has been computed. The way of computing the contribution to \(C(x,d)\) (lines 3 and 5) is justified by the proof of Theorem 2. ```
Data: Stream of temporal edges of a directed temporal graph \(G=(V,E)\) in non-increasing order with respect to their appearing time and destination \(d\). Result: Array of real number containing the \"contribution\" of \(d\) to the closeness of all other nodes.