# Finding Top-\(k\) Nodes for Temporal Closeness in Large Temporal Graphs
## 2 Computing the Closeness  
In this section, we propose an algorithm for computing exactly the closeness of a node \(u\) of a temporal graph \(G\). This algorithm can be seen as a temporal version of the breadth-first search algorithm starting from a source node \(s\), in which the temporal edges are scanned in non-decreasing order with respect to their appearing time. In the following, we assume that the appearing times of all temporal edges are distinct: the algorithm can be adapted to the case in which this assumption is not satisfied, as we will see below. Moreover, we assume that the temporal graph is directed: if this is 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},a_{x})\), which indicates that, for any time instant \(t\) in \((l_{x},r_{x}]\), any earliest arrival \(t\)-path \(\mathbb{P}\) from \(s\) to \(x\) has ending time \(\eta(\mathbb{P})\) equal to \(a_{x}\) (see Algorithm 1). At the beginning, we do not know anything about the reachability of a node \(x\) from \(s\): hence, we set the arrival time of \(x\) equal to \(\infty\) for an arbitrary time interval (for example, \((t_{\alpha}-2,t_{\alpha}-1]\)) preceding \(t_{\alpha}\) (line 1). When we read a new temporal edge \((x,y,t)\), we first set \(\tau_{s}=\left\{(t-1,t,t-1)\right\}\), since, clearly, the source node is always reachable even before the appearance of the edge (line 2). Let \(\tau_{x}=(l_{x},r_{x},t_{x})\) and \(\tau_{y}=(l_{y},r_{y},t_{y})\) be the two triples associated with \(x\) and \(y\), respectively. If \(r_{x}>r_{y}\), then we add to the closeness of \(s\) the contribution of node \(y\) corresponding to the interval \((l_{y},r_{y}]\) (line 3) and we update the triple associated with \(y\) by setting \(\tau_{y}=(r_{y},r_{x},t)\) (line 4). This update is justified by Lemma 1. When all temporal edges have been read, we add to the closeness of \(s\) the contribution of a node \(x\) corresponding to the interval \((l_{x},r_{x}]\) (line 5), which is the last interval for which the earliest arrival time has been computed. The way of computing the contribution to the closeness of \(s\) (lines 3 and 5) is justified by the proof of Theorem 1. Lemma 1: _Let \(G=(V,E)\) be a temporal graph and \(s\in V\). For any \(u\in V\) with \(u\
eq s\), let \(\Xi_{u}=\langle\tau_{u,0},\tau_{u,1},\ldots,\tau_{u,h_{u}}\rangle\) be the sequence of triples \(\tau_{u,i}=(l_{u,i},r_{u,i},a_{u,i})\) such that \(l_{u,0}=t_{\alpha}-2,r_{u,0}=t_{\alpha}-1\), \(a_{u,0}=\infty\), and, for \(1\leq i\leq h_{u}\), \((l_{u,i},r_{u,i},a_{u,i})\) is the triple assigned to \(\tau[u]\) at the \(i\)-th execution of line 4 with \(y=u\) during the running of Algorithm 1 with input \(G\) and \(s\) (note that \(h_{u}=0\) if this line is never executed with \(y=u\)). Then, for any \(u\in V\) with \(u\
eq s\), the intervals \((l_{u,i},r_{u,i}]\), for \(0\leq i\leq h_{u}\), form a partition of the interval \((t_{\alpha}-2,r_{u,h_{u}}]\), and, for any \(t\in\mathcal{T}(G)\),  
\[d_{t}(s,u)=\left\{ \begin{array}{ll}a_{u,i}-t+1&\text{if $t\in(l_{u,i},r_{u,i}]$ with $1\leq i\leq h_{u}$,}\\ \infty&\text{otherwise.}\end{array} \right.\]  
**Proof. ** We prove the lemma by induction on the number \(k\) of temporal edges that have been read. In particular, for any \(k\) with \(0\leq k\leq|E|\), let \(\mathcal{A}(k)\) be the following statement. For any \(u\in V\) with \(u\
eq s\), let \(\Xi_{u}^{k}=\langle\tau_{u,0},\tau_{u,1},\ldots,\tau_{u,l_{u}^{k}}\rangle\) be the prefix of \(\Xi_{u}\) containing the triples assigned to \(\tau[u]\) at line \(4\) with \(y=u\) after having read \(k\) edges. The intervals \((l_{u,i},r_{u,i}]\), for \(0\leq i\leq l_{u}^{k}\), form a partition of the interval \((t_{\alpha}-2,r_{u,l_{u}^{k}}]\), and, for any \(t\in[t_{\alpha},r_{u,l_{u}^{k}}]\), if \(t\in(l_{u,i},r_{u,i}]\) then \(d_{t}(s,u)=a_{u,i}-t+1\). We now prove by induction on \(k\) that \(\mathcal{A}(k)\) is true for any \(k\) with \(0\leq k\leq|E|\).