# Finding Top-\(k\) Nodes for Temporal Closeness in Large Temporal Graphs
## 1 Introduction
### Definitions and Notations  
A temporal graph is a pair \(G=(V,E)\), where \(V\) is the set of nodes and \(E\) is the set of temporal edges. A temporal edge \(e\in E\) is a triple \((u,v,t)\), where \(u,v\in V\) are the source and destination nodes of the edge, respectively, and \(t\in\mathbb{N}\) is the appearing time of the edge. If the temporal edges are bidirectional, then \((u,v,t)\) can be also written as \((v,u,t)\). Let \(t_{\alpha}\) (respectively, \(t_{\omega}\)) denote the minimum (respectively, maximum) appearing time of a temporal edge in \(E\). The time horizon \(\mathcal{T}(G)\) of a temporal graph \(G\) is the interval \([t_{\alpha},t_{\omega}]\) of real numbers no smaller than \(t_{\alpha}\) and no greater than \(t_{\omega}\). In this paper, we will assume that the temporal edges are given to the algorithms one after the other (similarly, to the streaming model) either in non-decreasing or in non-increasing order with respect to the appearing time. A temporal path \(\mathbb{P}\) (also called a temporal walk [17]) in a temporal graph \(G=(V,E)\) from a node \(u\in V\) to a node \(v\in V\) is a sequence of temporal edges \(e_{1}=(u_{1},v_{1},t_{1}),e_{2}=(u_{2},v_{2},t_{2}),\ldots,e_{k}=(u_{k},v_{k}, t_{k})\) such that \(u=u_{1}\), \(v=v_{k}\), and, for each \(i\) with \(1<i\leq k\), \(u_{i}=v_{i-1}\) and \(t_{i}\geq t_{i-1}+1\). The length of a temporal path is the number of temporal edges included in it. The starting time (respectively, ending time) of a temporal path \(\mathbb{P}\), denoted by \(\sigma(\mathbb{P})\) (respectively, \(\eta(\mathbb{P})\)), is equal to the appearing time of the first (respectively, last) temporal edge in the path. Given a time \(t\in\mathcal{T}(G)\) and two nodes \(u\) and \(v\), we will denote by \(\mathcal{P}^{\geq}(u,v,t)\) the set of all temporal paths \(\mathbb{P}\) from \(u\) to \(v\) such that \(\sigma(\mathbb{P})\geq t\). Among all these temporal paths, in this paper we will distinguish the ones which allow us to arrive as early as possible. Definition 1: Given a temporal graph \(G=(V,E)\), two nodes \(u\) and \(v\) in \(V\), and a time \(t\in\mathcal{T}(G)\), a path \(\mathbb{P}\in\mathcal{P}^{\geq}(u,v,t)\) is said to be an earliest arrival \(t\)-path if \(\eta(\mathbb{P})=\min\{\eta(\mathbb{P}^{\prime}):\forall\mathbb{P}^{\prime} \in\mathcal{P}^{\geq}(u,v,t)\}\). Given a time \(t\in\mathcal{T}(G)\) and two nodes \(u\) and \(v\), the \(t\)-duration of a path \(\mathbb{P}\in\mathcal{P}^{\geq}(u,v,t)\) is defined as \(\delta(\mathbb{P})=\eta(\mathbb{P})-t+1\). Hence, an earliest arrival \(t\)-path is also a path in \(\mathcal{P}^{\geq}(u,v,t)\) with minimum \(t\)-duration. For this reason, we will also call these paths the shortest \(t\)-paths from \(u\) to \(v\). Definition 2: Given a temporal graph \(G=(V,E)\), two nodes \(u\) and \(v\) in \(V\), and a time \(t\in\mathcal{T}(G)\), the \(t\)-distance \(d_{t}(u,v)\) from \(u\) to \(v\) is equal to the \(t\)-duration of any shortest \(t\)-path from \(u\) to \(v\) (by convention, if \(\mathcal{P}^{\geq}(u,v,t)=\emptyset\), then we set \(d_{t}(u,v)=\infty\)). Once we have introduced the notion of \(t\)-distance, we can also define the analog of the harmonic closeness centrality in static graphs as follows. Definition 3: Given a temporal graph \(G=(V,E)\), a node \(u\), and a time \(t\in\mathcal{T}(G)\), the \(t\)-closeness of \(u\) is defined as  
\[C_{t}(u)=\frac{1}{n-1}\sum_{v\in V:u\
eq v}\frac{1}{d_{t}(u,v)}.\]  
The (temporal) closeness of \(u\) in \(\mathcal{T}(G)\) is then defined as  
\[C(u)=\frac{1}{t_{\omega}-t_{\alpha}}\int_{t_{\alpha}}^{t_{\omega}}C_{t}(u)\; \mathrm{d}t.\]  
An Example  
Let us consider the temporal graph shown in the left part of Figure 1. In this case, \(t_{\alpha}=1\), \(t_{\omega}=4\), and \(\mathcal{T}(G)=[1,4]\).