betweenness_centrality (), a logical error? (with examples)

[SU]

Dear all,

Nice day. 

The betweenness centrality of a node v is the sum of the fraction of all-pairs shortest paths that pass through v. The api is described here. 

I calculated  the betweenness centrality for the following example:

But the result doesn't make sense. Based on definitions,

(i). the number of all-pairs shortest paths is (n-1)(n-2)/2 = 55 where n denotes the number of nodes, since there is  only one shortest path between any two nodes;

(ii). the number of paths passing through say node A: 4(X--->B) + 4(X---->C)  + 4*4(X----->Y)=24

Thus, the betweenness centrality of node A equals 24/55=0.44, not 0.53.

Take another example Florentine families graph generated by networkx as follows:

First, I listed all shortest path pairs. The resulted is attached. Within this file, we can get the statistical result:

The total number of shortest paths is: 137
The number of those paths including 'Medici' is: 86
The number of those paths begin with 'Medici' is: 17
The number of those paths begin with 'Medici' is: 2
The number of those paths passing through 'Medici' is: 67

The betweenness centrality of node 'Medici' is: 0.489051 which does not correspond to 0.52.

Expect to hear from you.

Nice weekeed.

SU

[Raf Guns]

Hi,

On Fri, Sep 12, 2014 at 11:42 AM, SU <qiank...@gmail.com> wrote:

I calculated  the betweenness centrality for the following example:

But the result doesn't make sense. Based on definitions,

(i). the number of all-pairs shortest paths is (n-1)(n-2)/2 = 55 where n denotes the number of nodes, since there is  only one shortest path between any two nodes;

(ii). the number of paths passing through say node A: 4(X--->B) + 4(X---->C)  + 4*4(X----->Y)=24

Thus, the betweenness centrality of node A equals 24/55=0.44, not 0.53.

In this case, n = 11 and hence, (n-1)(n-2) / 2 = 45. This yields a betweenness centrality of 24/45 = 0.53.

Best,

Raf

[SU]

Dear Raf,

Thanks for your reply. I know where I've gone wrong. I calculated the total number of shortest path pairs including begin with node k, thus n*(n-1)=55 (sorry for mistyping last letter). 

But I am still confused by the second example.

The total number of shortest path pairs without beginning with node Medici is 118 (there are more than one shortest path for some pairs)

The number of those paths passing through 'Medici' is: 67

Thus, the betweenness centrality of node Medici is 67/118=0.57 not 0.52

Expect to hear from u again. Thank you very much.

Best regards,

SU