# Finding Top-\(k\) Nodes for Temporal Closeness in Large Temporal Graphs
## 1 Introduction  
Determining indices capable of capturing the importance of a node in a complex network has been an active research area since the end of the forties, especially in the field of social network analysis where the ultimate goal has always been to develop theories \"to explain the human behavior\" [1]. After observing \"that centrality is an important structural attribute of social networks\", and that there \"is certainly no unanimity on exactly what centrality is or on its conceptual foundations\", in [2] the author proposed such a conceptual foundation of centrality by making use of graph theory concepts. The node indices proposed in that paper (that is, the degree centrality, the betweenness centrality, and the closeness centrality) have become quite standard notions in complex network analysis. For two of them in particular, that is, closeness and betweenness, a quite large amount of literature has been devoted to the design, analysis and experimental validation of efficient algorithms for computing them, either exactly (e.g., the well-celebrated Brandes' algorithm for computing the betweenness [3]) or approximately (e.g., the sampling approximation algorithm for estimating the closeness [4]), especially after that very large network data have become available, thus making the searching of very efficient algorithms a necessity. Reporting all the results obtained in this direction is clearly out of the scope of this paper: we refer the interested reader to one of the several surveys that appeared in the literature(such as [5]), to one of the several more conceptual works (such as [6]), or to the excellent periodic table of network centrality shown in [7]. In this paper, we focus our attention to the closeness centrality measure, which associates to each node of a graph its average distance from all the other nodes (since we will deal with unweighted graphs only, the distance between two nodes \(u\) and \(v\) is simply the number of edges included in the shortest path from \(u\) to \(v\)). In order to deal with the case of (weakly connected) directed graphs, two main alternatives are available when formally defining this measure: one approach assumes that the number of nodes reachable from a node \(u\) is known (see, for example, [8]), while the other, which is also called harmonic centrality, uses the inverse of the distances in order to deal with disconnected pairs of nodes (see, for example, [9]). Since in this paper we will use the temporal analogue of the second alternative, we limit ourselves to give the following formal definition. Given a directed graph \(G=(V,E)\), the (harmonic) closeness of a node \(u\in V\) is defined as \(C(u)=\frac{1}{n-1}\sum_{v\in V:v\
eq u}\frac{1}{d(u,v)}\), where \(d(u,v)\) denotes the number of edges included in the shortest path from \(u\) to \(v\) (by convention, \(d(u,v)=\infty\) if there is no path connecting \(u\) to \(v\)). The harmonic closeness of a node is a value between \(0\) and \(1\): the closer is \(C(u)\) to \(1\), the more important the node \(u\) is usually considered. For instance, in a directed star with \(n\) nodes, there is one node whose closeness is equal to \(1\), while all other nodes have closeness equal to \(0\). On the contrary, in a directed cycle with \(n\) nodes, all nodes have closeness \(H_{n-1}\), where \(H_{k}\) denotes the \(k\)-th harmonic number (that is, the sum of the reciprocals of the first \(k\) natural numbers). Computing the closeness of a node \(u\) in a directed (unweighted) graph is simple: we just have to perform a breadth-first search starting from \(u\) and sum the inverse of the distances to all the nodes reached by the search. This requires \(O(m)\) time and \(O(n)\) space, where \(n\) denotes the number of nodes and \(m\) denotes the number of edges. However, we are usually interested in comparing the closeness of all the nodes of the graph in order to rank them according to their centrality.