# Finding Top-\(k\) Nodes for Temporal Closeness in Large Temporal Graphs
## 1 Introduction
Even if different notions of distance have been introduced while working with temporal graphs (see, for example, [28]), in this paper, we will focus only on one specific distance definition, which is, in our opinion, one of the most natural ones: that is, the time duration of the earliest arrival path starting no earlier than a specific time instant. This definition is motivated, for example, by the following typical query one could pose to a public transport network: if I want to leave no earlier than time \(t\), how long does it take to me to go from a (bus/metro/train) station to another station? More precisely, for any time instant \(t\), a temporal \(t\)-path (also called \(t\)-journey) is a sequence of edges such that the first edge appears no earlier than \(t\) and each edge appears later than the edges preceding it. Its arrival time is the appearing time of its last edge and its duration is the difference between its arrival time and \(t\) (plus one in order to include the traveling time along the last edge). The \(t\)-distance \(d_{t}(u,v)\) from a node \(u\) to a node \(v\) is then the minimum duration of any temporal \(t\)-path connecting \(u\) to \(v\) and having the smallest arrival time (once again, if there is no \(t\)-path from \(u\) to \(v\), we will assume that \(d_{t}(u,v)=\infty\)). For instance, in the case of the temporal triangle in the left part of Figure 1, we have that \(d_{1}(c,a)=2-1+1=2\), while \(d_{2}(c,a)=4-2+1=3\): indeed, if we insist in leaving after time \(1\), we cannot arrive at \(a\) before time \(4\). Note that, for any \(t\in(2,4]\), \(d_{t}(b,a)=d_{t}(b,c)=\infty\), since there are no temporal edges incident to \(b\) with appearing time greater than \(2\). Once we have a definition of distance from a node to another node, we can define the notion of temporal closeness centrality of a node \(u\) at a given time instant \(t\) by simply applying the harmonic definition of closeness in the case of a static graph (see, for example, [9]). Note that we refer to the harmonic closeness centrality, since, as in the case of weakly connected directed graphs, this definition allows us to deal with the fact that two nodes might not be connected by a temporal path. More precisely, the \(t\)-closeness of a node \(u\) is defined as \(C_{t}(u)=\frac{1}{n-1}\sum_{v\in V:v\
eq\mu}\frac{1}{d_{t}(u,v)}\). In [22], the evolution of \(C_{t}(u)\) was analysed in the case of two social networks (an e-mail graph and a contact graph). To this aim, the authors used an algorithm (inspired by [29]) for computing the \(t\)-closeness of a node of a temporal graph, whose time complexity is linear in the number \(m\) of temporal edges and whose space complexity is linear in the number \(n\) of nodes. For example, we can apply this algorithm to analyse and compare the evolution of the \(t\)-closeness in the case of two actors, by referring to the IMDB collaboration graph,  
Figure 1: An example of a temporal undirected graph with the three temporal edges \((a,b,2)\), \((a,c,4)\), and \((b,c,1)\) (**left**) and of the corresponding \(t\)-distances (**right**). where the nodes are the actors and the temporal edges correspond to collaborations in the same (non TV) movie (the appearing time of an edge is the year of the movie). In the left part of Figure 2, we show the evolution of the \(t\)-closeness of [PERSON] and [PERSON] (two actors who were alive approximately in the same period) (Note that the \(t\)-closeness is greater than zero even when \(t\) is less than the birth year of the corresponding actor. This is not a contradiction, since, in general, a temporal edge may contribute to the \(t\)-closeness of a node for all \(t\) preceding the appearing time of the temporal edge itself). As can be seen, the two plots are quite similar until the end of the sixties (even if the plot of [PERSON] has a smaller peak).