Djikstra's shortest path vs Brandes algorithm for betweeness centrality

Question

I have a couple of Python scripts that calculate various network measures.

Given a graph (G), the first script calculates the average shortest path from each node to all other nodes and stores this in an Nx1 matrix (L). An implemntation of Djikstra's algorithm from the NetworkX Python library is used for this:

for i in range(num_nodes):
    for j in range(num_nodes):
        dj_path_matrix[i,j] = nx.dijkstra_path_length(G, i, j)

L = np.sum(dj_path_matrix, axis=0)/(num_nodes - 1)

Given the same graph (G), the second script uses an implementation of Brande's algorithm in the NetworkX library to calculate betweenness centrality and stores this in an Nx1 matrix (BC):

BC = nx.betweenness_centrality(G, normalized=True)

My question is: why does it take so much longer to calculate L compared to BC?

The way I understand it, BC of a node is a measure of how often a shortest path travels through that node. As such, to calculate BC, surely you would need to calculate all possible shortest paths in the graph. And surely then, BC should take at least as long as L? Using my scripts, given the same graph, it will take a couple of seconds to calculate BC, but up to half an hour to calculate L.

Answer 1

The way I understand it, BC of a node is a measure of how often a shortest path travels through that node. As such, to calculate BC, surely you would need to calculate all possible shortest paths in the graph.

This isn't necessarily true. Perhaps there is a different algorithm that is faster than what you outline. One possible explanation for the discrepancy in running times is that the NetworkX library uses a smarter algorithm. However, it's hard to know because you haven't told us how the function betweenness_centrality is implemented in NetworkX. It is also possible that it uses an algorithm along similar lines, but employs some optimizations that don't affect the asymptotic running time (big O) but does save a large constant factor.