12 deleted 609 characters in body; edited title

# Finding a vertex of least distance to all other vertices , in a simple graphusingadjacencymatrices

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 closeness centrality of length $k$ connecting vertices $i$ and $j$ in $G$. For a vertex $i$ its closeness centrality, 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). There is an obvious matrix-based algorithm for finding i^* that uses k^{th} powers of the adjacency matrix, which encode information about the path lengths of paths that connect two given vertices. But this algorithm, for a graph of N vertices, uses a total of \mathcal O(N^4) steps and uses \mathcal O(N^2) space. Sincerely, Sandeep Murthy. 11 added 330 characters in body 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 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)$. There is an obvious matrix-based algorithm for finding$i^*$that uses$k^{th}$powers of the adjacency matrix, which encode information about the path lengths of paths that connect two given vertices. But this algorithm, for a graph of$N$vertices, uses a total of$\mathcal O(N^4)$steps and uses$\mathcal O(N^2)$space. Sincerely, Sandeep Murthy. 10 deleted 2312 characters in body; [made Community Wiki] 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 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)$. 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}]$of size$N$representing the graph$G$, of the kind described above. OUTPUT: An integer$i^*$labelling a vertex of$G$with the maximum closeness centrality $C(i^*)$. START: • 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$. • Compute powers$A^k$, for$2 \leq k \leq N - 1$. • 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$. • For each vertex$i$of$G$, compute its total distance $T(i) = \sum_{j \neq i}d_{ij}$ to all other vertices. • 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?

9 Simplified title
8 Corrected error.; added 2 characters in body; added 21 characters in body
7 edited tags
6 Improved formatting.; added 4 characters in body
5 added 2 characters in body
4 Improved clarity.; edited body
3 deleted 5 characters in body
2 Corrected erroneous statement in 1st paragraph.
 
1