# Finding Top-\(k\) Nodes for Temporal Closeness in Large Temporal Graphs
## 3 Approximating the Closeness
That is, \(d_{t}(u,d)=l_{u,1}-t+1\) for any \(t\in[t_{\alpha},l_{u,1})\) and, hence, this interval contributes to \(C(u,d)\) with the first integral in the previous equation. Hence, Algorithm 2 correctly computes the contribution \(C(u,d)\) of node \(d\) to the closeness of node \(u\). The time complexity of the algorithm is clearly \(O(|E|)\), since each temporal edge is analyzed once only, and the update operation requires constant time. The space complexity is linear in the number of nodes, since, for each node \(u\), we have to maintain (apart from the value \(C\)) just four numbers corresponding to the current value of \(\tau[u]\) and to the starting value of the previous tuple. From the definition of closeness and of \(C(u,d)\), it follows that  
\[C(u)=\frac{1}{n-1}\sum_{d\in V}C(u,d).\]  
This formula immediately suggests the following definition of an estimator of the closeness of a node. **Definition 6**. : _Given a temporal graph \(G=(V,E)\), a node \(u\), and a (multi)set \(X=\{x_{1},\ldots,x_{h}\}\) of vertices in \(V\), we define the closeness \(X\)-estimator of \(u\) in \(\mathcal{T}(G)\) as_  
\[C^{X}(u)=\frac{1}{n-1}\frac{n}{h}\sum_{i=1}^{h}C(u,x_{i}).\]  
**Theorem 3**. : _Let \(G=(V,E)\) be a temporal graph and \(X\subseteq V\) be a randomly chosen (multi)set of \(h\) nodes in \(G\). If \(h=\Theta(\log n/\epsilon^{2})\), then, for any node \(u\in V\), \(|C(u)-C^{X}(u)|\leq\epsilon\) with high probability._  
The proof of the above theorem uses the same techniques of [4], and is very similar to the one given in [40] to analyze the absolute error of a sampling-based algorithm for computing distance distribution approximations in static graphs. For the sake of completeness, we give the complete proof. As a first step, the following lemma shows that the closeness estimator is unbiased. **Lemma 3**. : _Given a temporal graph \(G=(V,E)\) and a uniformly randomly chosen node \(x\in V\), the expected value of \(C^{\{x\}}(u)\) is equal to \(C(u)\)._  
Proof. : Since \(x\) has been randomly chosen in a uniform way, we have that  
\[\mathbb{E}[C^{\{x\}}(u)]=\frac{1}{n}\sum_{d\in V}C^{\{d\}}(u).\]  
From the definition of the estimator and from the fact that \(h=1\), it follows that  
\[\mathbb{E}[C^{\{x\}}(u)]=\frac{1}{n}\frac{1}{n-1}n\sum_{d\in V}C(u,d)=\frac{1} {n-1}\sum_{d\in V}C(u,d)=C(u).\]  
The lemma is thus proved. In order to prove Theorem 3, we make use of the following application of the [PERSON]'s inequality (see, for example, [41]). **Theorem 4**. : _If \(A_{1},A_{2},\ldots,A_{h}\) are independent random variables such that \(\mu=\mathbb{E}[\sum_{i=1}^{h}A_{i}/h]\) and, for each \(i\), \(0\leq A_{i}\leq 2\), then, for any \(\epsilon\geq 0\),_  
\[Pr\left\{\left|\frac{\sum_{i=1}^{h}A_{i}}{h}-\mu\right|\geq\epsilon\right\} \leq 2e^{-\frac{h\epsilon^{2}}{2}}.\]  
Proof Theorem 3.: Given a temporal graph \(G=(V,E)\), a node \(u\), and a randomly chosen (multi)set \(X\) of nodes in \(V\) with \(X=\{x_{1},\ldots,x_{h}\}\), we apply the above theorem by setting \(A_{i}=C^{\{x_{i}\}}(u)\), for each \(i\) with \(1\leq i\leq h\).