[igraph] betweenness on small graph

[Matthew Galati]

I am trying to understand the results of a betweenness calculation.

 

Vertices: 4

Edges: 5

Directed: FALSE

Edges:

             

[0] '0' -- '1'

[1] '0' -- '2'

[2] '0' -- '3'

[3] '1' -- '3'

[4] '2' -- '3'

> g<-read.graph(file="\\\\sanyo\\u42\\magala\\pp\\optgraphNEW\\test\\Rdata\\centr1.txt", format="ncol");

> betweenness(g,V(g),directed=FALSE)

[1] 0.5 0.0 0.0 0.5

 

For this graph, there are n*n-1 shortest paths to calculate. All are trivial except (s,t) = (2,1) and (1,2).

 

s-t, shortest path, sigma_st(v) / sigma_st

0-1, 0-1

0-2, 0-2

0-3, 0-3

1-0, 1-0

1-2, 1-0-2, 1-3-2

1-3, 1-3

2-0, 2-0

2-1, 2-0-1, 2-3-1

2-3, 2-3

3-0, 3-0

3-1, 3-1

3-2, 3-2

 

For the definition of betweenness: http://en.wikipedia.org/wiki/Centrality#Betweenness_centrality

 

So, for node 0,

C_B(0) = 1/2 + 1/2 = 1

    (contribution from 1-2 and 2-1)

 

But, igraph is giving 0.5. Can someone explain why?

 

Thanks,

Matt