is this betweenness calculation correct?

Question

I try to calculate betweenness for all nodes for the path from 2 to 6 in this simple graph.

G=nx.Graph()
edge=[(1,5),(2,5),(3,5),(4,5),(4,6),(5,7),(7,6)]
G.add_edges_from(edge)
btw=nx.betweenness_centrality_subset(G,[2],[6])

However the result is:

{1: 0.0, 5: 0.5, 2: 0.0, 3: 0.0, 4: 0.25, 6: 0.0, 7: 0.25}

I was wondering why the betweenness for node 5 is 0.5 while it should be 1 since the number of total shortest path is 2 and both of them include 5 and node 4 and 7 should be 0.5

As noted by @abc, this looks like a bug. I've submitted a bug report. Until the bug is fixed in a later update, the correction is to multiply all results by 2 (as long as the graph is undirected). Luckily this bug will not affect any rankings. — Joel
There is another problem I found and I'm not sure why it's in this way. If you consider a graph with edges (1,2) (1,5) (2,3) (3,6) (6,5) (4,2) then the betweenness should be {1:1.5, 2:2.5, 3:2.5, 4:0, 5:1, 6:1}. However, the results are these but multiply by 0.1. I can't understand why — Mohammad.sh
For this new graph, it's not clear to me what betweenness you are calculating (between which nodes?). The betweenness should be greater than 1 - the betweenness of v is the probability a shortest path from source to target goes through v. — Joel
well, I calculated the betweenness for all possible pairs for each node. However, the problem is that the output from networkx is less than 1. the output is : {1: 0.15, 2: 0.25, 3: 0.25, 4: 0, 5: 0.1, 6: 0.1} — Mohammad.sh

abc abc · Accepted Answer · 2019-06-12T22:56:05

It looks like a bug.

Here my guess. The bug seems coming from the _rescale function. Here, if the graph is indirected the computed values are multiplied by 0.5.

Since in the general betweenness_centrality a node is considered twice (shortest paths are computed for each node in the graph) for the betweenness_centrality_sub this is not necessary since shortest paths are only computed for the sources nodes.

Example:

nx.betweenness_centrality_subset(G,[2,6],[2,6])
# {1: 0.0, 5: 1.0, 2: 0.0, 3: 0.0, 4: 0.5, 6: 0.0, 7: 0.5}

So, if my guess is right, you just need to multiply by 2 the computed result.

is this betweenness calculation correct?

2 Answers