All-pairs shortest paths, tie breaking

Question

I am creating a program which will calculate Betwenness Centrality for all nodes in a unweighted graph. To do that I have to find ASSSP (All Single Source Shortest Paths). While creating the program, I came to realize that eventually I will have ties (same distance from source to destination but different paths). This lead me to this question. How should I resolves these ties? If I use random tie breakers, then each output of the Betweenness Centrality might be slightly different for the same input. Let me make a small exemplary graph:

   A
  / \
B    C
  \ /
   D

Now lets say that the A node is our source for which we wish to find ASSSP. It can be clearly seen that There exist two paths (A->B->D and A->C->D), bot of them have the same length, both of them are the shortest ones. Now which one should I choose, and on what condition?

Random Tie breakers (problem)

If I use random tie breakers, like the first one to be found, is marked as the shortest path (the program is distributed so this solution will work in a random fashion). Then I will have problem with Betweenness Centrality, as the value will vary for nodes B and C; depending on which path was marked as the shortest.

Does anyone know how to solve this issue, or am I just missing something?

Answer 1

To calculate the betweenness centrality properly, you must take into account every shortest path in the graph. If two nodes A and B have k shortest paths between them, each shortest path will contribute 1/k to the total betweenness scores of the nodes that the paths pass through. In general, you should not calculate betweenness centrality by actually finding (and storing) all the shortest paths in the networks; see the following paper for a more efficient algorithm:

A Faster Algorithm for Betweenness Centrality

Answer 2

Yes, SSSP, or Single Source Shortest Path, is a very common problem in computer science. One standard practice is that the first path you came across is shorter than the others with the same distance.

For instance, in your example, if in your algorithm you processed A->B->D before A->C->D, then A->B->D would be the shortest path.

If things are still unclear, I believe Dijkstra's algorithm is what you're after.

Answer 3

Pretty much because of the problems you noticed, Betweenness Centrality is not actually calculated by examining just a single path between a source and a target, but by counting the number of shortest paths. You need to modify a sutiable shortest path algorithm for this, for example the Floyd–Warshall algorithm or Johnson's algorithm.