# Finding Top-\(k\) Nodes for Temporal Closeness in Large Temporal Graphs
## 3 Approximating the Closeness
for\(x\gets 1\)to\(|V|\)do \(C[x]\gets 0\);
1\(\tau[x]=(t_{\omega}+1,t_{\omega}+2,\infty)\); \(S[x]\leftarrow\infty\);  end while whilethere are other edges to be readdo  let \(e\leftarrow(x,y,t)\) be the next edge; \(\tau[d]\leftarrow(t,t+1,t+1)\); \(S[d]\gets t\); \((l_{x},r_{x},s_{x})\leftarrow\tau[x]\); \((l_{y},r_{y},s_{y})\leftarrow\tau[y]\); if\(l_{y}<l_{x}\)then \(C[x]\gets C[x]+\ln\frac{\min(t_{\omega},l_{x})-t+1}{\min(t_{\omega},l_{x}) -s_{x}+1}\); \(\tau[x]\leftarrow(l_{y},l_{x},t)\); \(S[x]\leftarrow s_{x}\);  end if  end for for\(x\gets 1\)to\(|V|\)do \((l_{x},r_{x},s_{x})\leftarrow\tau[x]\); \(C[x]\gets C[x]+\ln\frac{\min(t_{\omega},l_{x})-s_{x}+1}{\min(t_{\omega},l_ {x})-S[x]+1}+\ln\frac{l_{x}-l_{x}+1}{l_{x}-s_{x}+1}\);  end for return\(\frac{C}{l_{\omega}-l_{x}}\)
```  
**Algorithm 2**Algorithm for computing the closeness contribution of a node to all the others  
**Lemma 2**. : _Let \(G=(V,E)\) be a temporal graph and \(d\in V\). For any \(u\in V\) with \(u\
eq d\), let \(\Xi_{u}=\langle\tau_{u,1},\tau_{u,2},\ldots,\tau_{u,h_{u}}\tau_{u,h_{u}+1}\rangle\) be the sequence of triples \(\tau_{u,j}=(l_{u,i},r_{u,i},s_{u,i})\) such that \(l_{u,h_{u}+1}=t_{\omega}+1\), \(r_{u,h_{u}+1}=t_{\omega}+2\), \(s_{u,h_{u}+1}=\infty\), and, for \(1\leq i\leq h_{u}\), \((l_{u,i},r_{u,i},s_{u,i})\) is the triple assigned to \(\tau[u]\) at the \((h_{u}+1-i)\)-th execution of line 4 with \(x=u\) during the running of Algorithm 2 with input \(G\) and \(d\) (note that \(h_{u}=0\) if this line is never executed with \(x=u\)). Then, for any \(u\in V\) with \(u\
eq d\), the intervals \([l_{u,i},r_{u,i})\), for \(i\leq i\leq h_{u}+1\), form a partition of the interval \([l_{u,1},t_{\omega}+2)\), and, for any \(t\in\mathcal{T}(G)\),_  
\[d_{t}(u,d)=\left\{ \begin{array}{ll}r_{u,i}-t+1&\text{if $s_{u,i}<t\leq s_{u,i+1} $ 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{S}(k)\) be the following statement. For any \(u\in V\) with \(u\
eq s\), let \(\Xi_{u}^{k}=\langle\tau_{u,h_{u}^{k}},\ldots,\tau_{u,h_{u}+1}\rangle\) be the suffix of \(\Xi_{u}\) containing the triples assigned to \(\tau[u]\) at line 4 with \(x=u\) after having read \(k\) edges. The intervals \([l_{u,i},r_{u,i})\), for \(h_{u}^{k}\leq i\leq h_{u}+1\), form a partition of the interval \([l_{u,h_{u}^{k}},t_{\omega}+2)\), and, for any \(t\in[l_{u,h_{u}^{k}},t_{\omega}]\), if \(s_{u,i}<t\leq s_{u,i+1}\) then \(d_{t}(u,d)=r_{u,i}-t+1\). We now prove by induction on \(k\) that \(\mathcal{S}(k)\) is true for any \(k\) with \(0\leq k\leq|E|\). **Base case**. \(k=0\). In this case, no edge has been read yet and, hence, line 4 has never been executed with \(x=u\). We then have that, for any \(u\in V\) with \(u\
eq d\), \(h_{u}^{0}=h_{u}+1\), \(\Xi_{u}^{0}=\langle\tau_{u,h_{u}+1}\rangle\) with \(\tau_{u,h_{u}+1}=(t_{\omega}+1,t_{\omega}+2,\infty)\), and, hence, \([l_{u,h_{u}+1},r_{u,h_{u}+1})=[t_{\omega}+1,t_{\omega}+2)=[l_{u,h_{u}^{0}},t_{ \omega}+2)\). Moreover, the interval \([l_{u,h_{u}^{0}},t_{\omega}]=[t_{\omega}+1,t_{\omega}]\) is empty and the condition on the \(t\)-distances is \"vacuosyl\" true. Hence, \(\mathcal{S}(0)\) is true. **Induction step**. Given \(k\) with \(1\leq k\leq|E|\), suppose that \(\mathcal{S}(k-1)\) is true. We now prove that \(\mathcal{S}(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 \(x\) (since the graph is directed). Hence, we have just to prove that the value of \(\tau[x]\) is correctly updated. By the induction hypothesis, we know that the current value of \(\tau[x]=(l_{x},r_{x},s_{x})\) is such that, for any \(t^{\prime}\in[l_{x},t_{\omega}]\), the starting time of any latest starting \(t^{\prime}\)-path from \(x\) to \(d\) is at least \(s_{x}>t\). Hence, the edge \(e\) cannot improve these starting times since its appearing time is \(t\).