wrong normalization in betweenness_centrality(endpoints=True)

[leonardomaccari]

I would expect that the normalized centrality should be in the [0,1] range, but when including the endpoints this does not happen.

g = nx.star_graph(2)
nx.betweenness_centrality(g)
{0: 1.0, 1: 0.0, 2: 0.0}
nx.betweenness_centrality(g, endpoints=True)
{0: 3.0, 1: 2.0, 2: 2.0}

The documentation (and code) says that the normalization multiplies by 2/((n-1)(n-2)). I spent some time to understand this number, and i tracked down the following:

In the original paper from Freeman (A set of measures of centrality based on betweenness, pag 38) he introduces a normalization by dividing per (n(n-1)*1/2)-(n-1) where:
n(n-1)*1/2 : number of shortest paths in the undirected graph
(n-1) : number of shortest paths ending/beginning in the node for which we compute centrality

this leads to division by (n*n - 3n + 2)*1/2 == (n-1)(n-2)*1/2 but, this implicitly removes the node we compute centrality on from the enpoints, as Freeman says. When centrality is computed with the endpoints, this term should be removed, and normalization should be applied simply with the potential number of paths: n(n-1)*1/2

In general, normalization could be done with whatever constant, but:

• I think most people expect betweenness to be in [0,1]
• This was noted in the edge_betweenness_centrality() and corrected in Bug in edge_betweenness_centrality (migrated from Trac #620) #611, so right now edge and node centrality is normalized differently, which is pretty awkward.

So I suggest normalization is changed when betweenness is computed including the endpoints.

[hagberg]

Thanks for tracking this down. I agree with you that it is reasonable to normalize by the potential number of paths. This should be a pretty easy fix.

[manoelhortaribeiro]

Can I give it a try?

[hagberg]

Yes, go for it.

[bakerwho]

I'm interested in contributing and this does seem like it might have a simple fix. However, it looks @regstrtn has already tried a fix that has failed the Travis CI build. Any way I can help?