Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, the closeness centrality of a vertex $i$, denoted by $C(i)$, is defined to be the inverse of the mean distance of $i$ to all other vertices of $G$. (Here the distance $d\_{ij}=d\_{ji}$ between two vertices $i,j$ is simply the number of edges connecting them, orientation being irrelevant.) Formally $C(i) := \frac{N-1}{\sum\_{j \neq i}d\_{ij}}$. The denominator of $C(i)$ is the sum of all the distances of vertex $i$ to other vertices, and we may call this its peripherality (with respect to the other vertices) in the graph. Clearly, the lower the peripherality of $i$ the higher its closeness centrality $C(i)$, and vice versa.


My question is: if $G$ is a simple, directed graph of $N$ vertices (labelled by $0,1,...,N-1$) with a total of $N-1$ edges between them, such that every two vertices are connected by a path (not necessarily oriented), and that there is one and only such path between them, then, is there an efficient algorithm $\mathcal A$ for finding any vertex $i^\\*$ of G with
maximum closeness centrality $C(i^\*)$, equivalently, minimal peripherality, with average case time complexity and average case space complexity of $\mathcal O(N)$?


For example, let $G$ be the graph of $10$ vertices, labelled by integers $0,1,...,9$, described by the zero-indexed array $T = [9,1,4,9,0,4,8,9,0,1]$, where if $T[i] = t\_i \neq i$ then there is a (directed) edge going from vertex $i$ to vertex $t\_i$. Then such an algorithm $\mathcal A$ , if it exists, should return vertex $0$ as the vertex of highest closeness centrality in $G$, namely $1.66$, since it has the smallest total distance (of $15$) to all other $9$ vertices, and it will do so with an average case time and space complexity of $\mathcal O$$(10)$.


Sincerely, Sandeep Murthy.



Finding a vertex of least distance to all other vertices in a graph
A graph as you describe is normally called a tree, and yes, it is easy to compute the sum of distances to all other vertices in a tree.


First, choose one of the leaves (arbitrarily) to be the root of the tree, and then compute for each node the sum of the distances to its descendants, in a bottom-up traversal order, as the number of descendants plus the sum of the values computed at its children. In particular the root of the tree gets the correct sum of the distances to all nodes.


Next, in second traversal of the tree, in top-down order (from the root down towards the leaves), compute the sum of distances from all nodes. This is (sum of distances from all nodes at parent) + (number of nodes that are not descendants) - (number of descendants).


Obviously, once you know the sum of distances at all nodes, you can easily compute the closeness centralities of the nodes and pick out the one whose centrality is largest.


