Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, with $A = (A_{ij}) = A^T$ being the $N \times N$ (symmetric) adjacency matrix of $G$, then for $1 \leq k < N$, the $k^{th}$ power $A^k$ has the property that its $(i,j)$ entry $(A^k)_{ij}$ is equal to the number of paths of length $k$ connecting vertices $i$ and $j$ in $G$. For a vertex $i$ its closeness centrality, 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 first 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 $i \neq T_i$, and $T[i] = t_i$ is the vertex to which there is a (directed) edge going from vertex $i$. Then such an algorithm $\mathcal A$ , if it exists, will 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)$.

I have a second question about the same kind of graph $G$ as described in the first question, but first an observation. The graph $G$, as described above, is connected (in the weak sense), and will have the property that the $k^{th}$ power $A^k$ of its adjacency matrix $A$ will contain a $1$ in its $(i,j)$ entry if and only if there is a path of length $k$ connecting vertices $i$ and $j$. Since $G$, by definition, is such that any two distinct vertices $i \neq j$ of $G$ are connected by one and only one path of some length $1 \leq d_{ij}=d_{ji} \leq N - 1$, it seems to follow that the distance $d_{ij}$ is equal to some such $k$, i.e. for any distinct vertices $i \neq j$ there is a $1 \leq k \leq N - 1$, such that $(A^k)_{ij} = 1$.

My second question is whether the following algorithm, regardless of its efficiency, is functionally correct, i.e. will it produce, in principle, a correct result for every possible valid test input? (I am thinking the input can be given as a zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ of integers $0 \leq t_i \leq N-1$ labelling the graph vertices, such that $T[i]=t_i$ is the vertex to which there is a (directed) edge going from vertex $i$, where $i \neq t_i$ . Note that in the graph $G$ I described, if there is an edge or path connecting vertices $i$ and $j$, then one and only such edge or path exists for these vertices.)

INPUT: Zero-indexed array $T = [t_0, t_1,..., t_{N-1}]$ representing the graph $G$, as described above.

OUTPUT: An integer $i^*$ labelling a vertex of $G$ with the maximum closeness centrality $C(i^*)$.

START:

1. Compute adjacency matrix $A = (A_{ij})$ as $A_{ij}=A_{ji}=1$ if $i \neq T[i]$ and $T[i]=j$, or $A_{ij}=A_{ji}=0$ if either $i=j$ or $T[i] \neq j$.
2. Compute powers $A^k$, for $2 \leq k \leq N - 1$.
3. For all vertex pairs $(i,j)$, where $i < j$, compute distance $d_{ij} = k$, where $1 \leq k \leq N-1$ necessarily exists, such that $(A^k)_{ij} = 1$.
4. For each vertex $i$ of $G$, compute its total distance $T(i) = \sum_{j \neq i}d_{ij}$ to all other vertices.
5. Return a first vertex $i^*$ with the property $T(i^*)$ is a minimum.

END

Is this algorithm functionally correct? If so, what would be its average case time and space complexity?

Sincerely, Sandeep Murthy.