# Finding Top-\(k\) Nodes for Temporal Closeness in Large Temporal Graphs
## 3 Approximating the Closeness
Analogously, we know that the current value of \(\tau[y]=(l_{y},r_{y},s_{y})\) is such that \(s_{y}>t\) is the starting time of any latest starting \(t^{\prime}\)-path from \(y\) to \(d\) with \(t^{\prime}\in[l_{y},r_{y})\). If \(l_{y}\geq l_{x}\), the edge \(e\) does not add any information for the node \(x\), since we already know the starting time of any latest starting \(t^{\prime}\)-path from \(x\) to \(d\), for any \(t^{\prime}\geq l_{x}\). On the contrary (see the right part of Figure 3), if \(l_{y}<l_{x}\), then, for any time instant \(t^{\prime}\in[l_{y},l_{x})\) (for which we did not know yet the corresponding latest starting time from \(x\)), we can now say that we can first reach \(y\) (at time \(t\) with \(t<s_{y}\leq l_{y}\) by using the temporal edge \(e\)), and then wait until starting the path from \(y\) to \(d\) at time \(s_{y}\): hence, for all these time instants, the latest starting time at \(x\) can now be set equal to \(t\), that is, the value of \(\tau[x]\) becomes \((l_{y},l_{x},t)\) (note that subsequent edges cannot improve this value since their appearing times are smaller than \(t\)). Hence, if \(\Xi_{y}^{k-1}=\langle\tau_{x,h_{x}^{k-1}},\ldots,\tau_{u,h_{x}+1}\rangle\), we have that \(\Xi_{x}^{k}=\langle\tau_{x,h_{x}^{k}},\tau_{x,h_{x}^{k-1}},\ldots,\tau_{u,h_{ x}+1}\rangle\) with \(h_{x}^{k}=h_{x}^{k-1}-1\) and \(\tau_{u,h_{x}^{k}}=(l_{y},l_{x},t)\). By the induction hypothesis, the intervals \([l_{x,i},r_{x,i})\), for \(h_{x}^{k-1}\leq i\leq h_{x}\), form a partition of the interval \([l_{x,h_{x}^{k-1}},t_{\omega}+2)\): by adding the triple \((l_{y},l_{x},t)\), we obtain a partition of the interval \([l_{x,h_{x}^{k}},t_{\omega}+2)\) (since \(l_{x}=l_{x,h_{x}^{k-1}}\) and \(l_{y}=r_{x,h_{x}^{k}}\)). From the previous argument, it also follows that, for any \(t^{\prime}\in[l_{x,h_{x}^{k}},t_{\omega}]\), if \(s_{x,i}<t^{\prime}\leq s_{x,i+1}\) then \(d_{t^{\prime}}(x,d)=r_{x,i}-t^{\prime}+1\). We have thus proved that \(\mathcal{S}(k)\) is satisfied. The lemma follows from the fact that its statement is exactly equivalent to \(\mathcal{S}(|E|)\). Theorem 2: _Let \(G=(V,E)\) be a temporal graph and \(d\in V\). Algorithm 2 with input \(G\) and \(d\) correctly computes, for any \(u\in V\) with \(u\
eq d\), the value \(C(u,d)\). If the temporal edges are already ordered in decreasing order with respect to their appearing time, then the complexity of the algorithm is \(O(|E|)\) time and \(O(|V|)\) space._  
Proof: From Lemma 2, it follows that, with respect to the node \(u\), the interval \(\mathbb{I}=[l_{u,1},t_{\omega}+2]\) is partitioned into \(l_{u}+1\) intervals \([l_{u,i},r_{u,i})\), such that, for any \(t\in[t_{a},t_{\omega}]\), if \(s_{u,i}<t\leq s_{u,i+1}\), then \(d_{t}(u,d)=r_{u,i}-t+1\). That is, each time instant \(t\in(s_{u,i},s_{u,i+1}]\cap[t_{a},t_{\omega}]\) contributes to \(C(u,d)\) with the value \(\frac{1}{r_{u,i}-t+1}\). Hence, we have that  
\[C(u,d) = \frac{1}{t_{\omega}-t_{\alpha}}\left[\int_{t_{\alpha}}^{\min(s_{u,1},t_{\omega})}\frac{1}{l_{u,1}-t+1}\,\mathrm{d}t+\sum_{i=1}^{h_{u}}\int_{s_ {u,i}}^{\min(s_{u,i+1},t_{\omega})}\frac{1}{\min(r_{u,i},t_{\omega})-t+1}\, \mathrm{d}t\right]\] \[= \frac{1}{t_{\omega}-t_{\alpha}}\left[\ln\frac{l_{u,1}-t_{\alpha }+1}{l_{u,1}-\min(s_{u,1},t_{\omega})+1}+\sum_{i=1}^{h_{u}}\ln\frac{\min(r_{u, i},t_{\omega})-s_{u,i}+1}{\min(r_{u,i},t_{\omega})-\min(s_{u,i+1},t_{\omega})+1} \right].\]  
Note that we used the minimum function in order to deal with the last interval whose right extreme is greater than \(t_{\omega}\) and whose left extreme can also be greater than \(t_{\omega}\) (whenever \(u\) cannot reach \(d\) in the interval \([t_{\alpha},t_{\omega}]\)). Note also that the interval \([t_{\alpha},l_{u,1})\) might be non empty: if this the case, then we can conclude that if we start from \(u\) at time \(t\) in this interval, then we cannot reach \(d\) before \(l_{u,1}\).