Find center of a sparse graph

Question

I'm currently working on the following problem: Given a directed graph G = (V, E) I use Dijkstra's Algorithm to find the shortest distance d_i for each node v_i ∈ V from a startnode v₀.

Now I want to find the node *v** for which the sum of all nodes shortest distances ∑d_i from this node is minimized.

In the following example the startnode v₀ is yellow and obviously has the distance 0. The shortest distances for all other nodes are given.

In the first figure (startnode in the bottom left) the sum of all shortest distances is

∑d_i = 1+2+2+2+3+3+3 = 16

In the second figure (startnode in the middle) the sum of all shortest distances is

∑d_i = 1+1+1+2+2+2+2 = 11

The edge-weights are floats, in the example they are chosen to be 1 for the sake of simplicity.

Obiously I could try for every node to find the minimum but that of course is way too slow. I can't wait to hear your ideas! :-)

Answer 1

In the context of social networks, the centrality metrics that you describe was defined by Sadibussi in 1966 (see here or in an unofficial link here It is also described and recommended by Freeman here (p.225) as a measure of decentrality). It is sometimes called farness (see here).

Breadth-first search allows one to calculate the lengths of the shortest paths from every vertex on a graph to every other. See the accepted answers here and here. Other methods for calculating All-Pairs Shortest Paths are described here.

Edit:

Since you noted that you are interested in an aproximate solution, have a look at the following paper by Baswana and Kavitha. Table 1.1 summerizes known results. The best approximate solutions to date requires O(n^(3/2)) space for 3-stretch solution (which means that the estimated distance would be more than the real distance, but less than 3 times the real distance). I guess this is not good enough for most practical purposes. There are no known APASP (All-Pairs Approximate Shortest Paths) algorithms with stretch<3 and less than O(n^2) space requirements.

Practical solutions:

Most implementations exploits the hierarchy inherent in real world road networks. See for example this, this and this.