# Finding Top-\(k\) Nodes for Temporal Closeness in Large Temporal Graphs
## 1 Introduction
This implies that we have to perform a breadth-first search starting from each node of the graph, thus requiring time \(O(nm)\). This computational time is unavoidable (as shown in [10]), unless the strong exponential time hypothesis [11] fails. However, in the case of real-world complex networks, the number of nodes and of edges is typically so large that this algorithm is practically useless. For this reason, several approaches have been followed in order to deal with huge graphs, such as computing an approximation of the closeness centrality (see, for example, [4; 12]) or limiting ourselves to find the top-\(k\) nodes with respect to the closeness centrality [10]. These algorithms turn out to be so effective and efficient that several of them are already included in well-known and widespread used network analysis software libraries (such as [13; 14]). So far, we have talked about static graphs, that is, graphs whose topology does not change over time. In this paper, however, we will focus on (directed) relationships which have timestamps. This led the research community to the definition of temporal graphs, that is, (unweighted) graphs in which edges are active at specific time instants: for this reason, we call them temporal edges and we denote them by triples \((u,v,t)\), where \(t\) is the appearing time of the temporal edge connecting \(u\) and \(v\). Temporal graphs are ubiquitous in real life: phone call networks, physical proximity networks, protein interaction networks, stock exchange networks, and public transportation networks are all examples of temporal graphs, in which the nodes are related to each other at different time instants. Until recently, the time dimension has been often neglected by aggregating the contacts between vertices to (possibly weighted) edges, even in cases when detailed information on the temporal sequences of contacts or interactions would have been easily available. For example, almost all collaboration networks (such as the scientific or professional collaboration networks) have been almost always analyzed without taking into account the time of the collaboration, even when this information was easily available (such as in the case of the information given by the DBLP computer science bibliography web site). However, if the temporal information is just ignored, we can lose important properties of the graph and we can even deduce wrong consequences. For example, in the case of the temporal undirected graph shown in the left part of Figure 1, if we ignore the temporal information associated with the edges, we can erroneously conclude that there exists a path starting from node \(a\), arriving at node \(c\), and visiting the other node \(b\). However, this path does not correspond to a temporally-feasible path, since the edge connecting node \(a\) to node \(b\) appears after the edge connecting \(b\) to \(c\): in other words, when we arrive in \(b\) it is too late to take the edge towards \(c\). It is then important to analyze temporal graph properties by taking into account the temporal information concerning the time intervals in which specific edges appear in the graph. For this reason, the community has rethought several classical definitions of graph theory in terms of temporal graphs [15; 16; 17]. One of such definition is the one of closeness centrality, which has been repeatedly reconsidered in the case of temporal graphs [18; 19; 20; 21; 22; 23; 24; 25; 26; 27]. In several of these papers, the authors refer to the classical definition of closeness centrality (that is, the one based on the average temporal distance), but in many cases, they actually consider the temporal analogue of the harmonic closeness centrality. In both cases, however, the first step to perform in order to rethink the definition of closeness in terms of temporal graphs consists of defining the temporal distance between two nodes.