4
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks. I thought a tree is undirected graph. The graph I describe was described to me as a directed acyclic graph, which I guess is a kind of tree, with partial ordering. Well, anyway, I can see the solution. P. S. Part of the problem with graph theory, being someone who is "just visiting" as it were, is that there are so many terms with overlapping or even inconsistent meanings. $\endgroup$
    – ramius
    Oct 17, 2011 at 22:28
  • $\begingroup$ @Sandeep: You are right, we don't even agree on what "graph" means. @David: For your next assignment, consider finding a vertex that minimizes $f$(multiset of distances to other nodes) for some given function $f$. Characterize those $f$ for which linear time is possible. $\endgroup$ Oct 18, 2011 at 1:58
  • $\begingroup$ It seems to me that we do not need to compute the distance sum of vertices. Surely if backwards iterate over the length of the the tree, such that inside each iteration, we iterate over the vertices of the current tree, testing whether the current vertex is a leaf, and stripping it from the tree if so, then when the current tree is down to 2 vertices, we can return any of those two vertices as the answer. Would this work? $\endgroup$
    – ramius
    Oct 19, 2011 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.