# Finding Top-\(k\) Nodes for Temporal Closeness in Large Temporal Graphs
## 2 Computing the Closeness
**Base case**. \(k=0\). In this case, no edge has been read yet and, hence, line \(4\) has never been executed with \(y=u\). We then have that, for any \(u\in V\) with \(u\
eq s\), \(h_{u}^{0}=0\), \(\Xi_{u}^{0}=\langle\tau_{u,0}\rangle\) with \(\tau_{u,0}=(t_{\alpha}-2,t_{\alpha}-1,\infty)\), and, hence, \((l_{u,0},r_{u,0}]=(t_{\alpha}-2,t_{\alpha}-1]=(t_{\alpha}-2,r_{u,l_{u}^{k}}]\). Moreover, the interval \([t_{\alpha},r_{u,h_{u}^{0}}]=[t_{\alpha},t_{\alpha}-1]\) is empty and the condition on the \(t\)-distances is \"vacuosly\" true. Hence, \(\mathcal{A}(0)\) is true. **Induction step**. Given \(k\) with \(1\leq k\leq|E|\), suppose that \(\mathcal{A}(k-1)\) is true. We now prove that \(\mathcal{A}(k)\) is also true. Let \(e=(x,y,t)\) be the \(k\)-th temporal edge read by the algorithm. Clearly, this edge has no influence on any other node than \(y\) (since the graph is directed). Hence, we have just to prove that the value of \(\tau[y]\) is correctly updated. By the induction hypothesis, we know that the current value of \(\tau[y]=(l_{y},r_{y},a_{y})\) is such that, for any \(t^{\prime}\in[t_{\alpha},r_{y}]\), the ending time of any earliest arrival \(t^{\prime}\)-path from \(s\) to \(y\) is at most \(a_{y}<t\). Hence, the edge \(e\) cannot improve these ending times since its appearing time is \(t\). Analogously, we know that the current value of \(\tau[x]=(l_{x},r_{x},a_{x})\) is such that \(a_{x}<t\) is the ending time of any earliest arrival \(t^{\prime}\)-path from \(s\) to \(x\) with \(t^{\prime}\in(l_{x},r_{x}]\). If \(r_{x}\leq r_{y}\), the edge \(e\) does not add any information for the node \(y\), since we already know the ending time of any earliest arrival \(t^{\prime}\)-path from \(s\) to \(y\), for any \(t^{\prime}\leq r_{y}\). On the contrary (see the left part of Figure 3), if \(r_{x}>r_{y}\), then, for any time instant \(t^{\prime}\in(r_{y},r_{x}]\) (for which we did not know yet the corresponding ending time of any earliest arrival \(t^{\prime}\)-path from \(s\) to \(y\)), we can now say that we can first reach \(x\) (at time \(a_{x}\) with\(r_{x}\leq a_{x}<t\)), and then wait until the temporal edge \(e\) appears to move to \(y\) at time \(t\): hence, for all these time instants, the earliest arrival time at \(y\) can now be set equal to \(t\), that is, the value of \(\tau[y]\) becomes \((r_{y},r_{x},t)\) (note that subsequent edges cannot improve this value since their appearing times are greater than \(t\)). Hence, if \(\Xi_{y}^{k-1}=\langle\tau_{y,0},\tau_{y,1},\ldots,\tau_{u,\lambda_{y}^{k-1}}\rangle\), we have that \(\Xi_{y}^{k}=\langle\tau_{y,0},\tau_{y,1},\ldots,\tau_{u,\lambda_{y}^{k}}\rangle\) with \(h_{y}^{k}=h_{y}^{k-1}+1\) and \(\tau_{u,\lambda_{y}^{k}}=(r_{y},r_{x},t)\). By induction hypothesis, the intervals \((l_{y,i},r_{y,i}]\), for \(0\leq i\leq h_{y}^{k-1}\), form a partition of the interval \((t_{\alpha}-2,r_{y,h_{y}^{k-1}}]\): by adding the triple \((r_{y},r_{x},t)\), we obtain a partition of the interval \((t_{\alpha}-2,r_{y,h_{y}^{k}}]\) (since \(r_{y}=r_{y,h_{y}^{k-1}}\) and \(r_{x}=r_{y,h_{y}^{k}}\)). From the previous argument, it also follows that, for any \(t^{\prime}\in[t_{x},r_{y,h_{y}^{k}}]\), if \(t^{\prime}\in(l_{y,i},r_{y,i}]\) then \(d_{t^{\prime}}(s,y)=a_{y,i}-t^{\prime}+1\). We have thus proved that \(\mathcal{A}(k)\) is satisfied. The lemma follows from the fact that its statement is exactly equivalent to \(\mathcal{A}(|E|)\). Theorem 4.1: _Let \(G=(V,E)\) be a temporal graph and \(s\in V\). Algorithm 1 with input \(G\) and \(s\) correctly computes the closeness of \(s\) in \(G\). If the temporal edges are already ordered in increasing order with respect to their appearing time, then the complexity of the algorithm is \(O(|E|)\) time and \(O(|V|)\) space._  
Proof: From Lemma 1, it follows that, with respect to the node \(u\), the interval \(\mathbb{I}=(t_{\alpha}-2,r_{u,\lambda_{u}}]\) is partitioned into \(h_{u}+1\) intervals \((l_{u,i},r_{u,i}]\), such that, for any \(t\in[t_{\alpha},t_{\omega}]\), if \(t\in(l_{u,i},r_{u,i}]\), then \(d_{t}(s,u)=a_{u,i}-t+1\).