CODEWITHSUNDEEP
rigraph
akki
akki

Reputation: 19

Betweenness of a vertex and edge in a graph

I created a graph using a code 

g <- graph.ring(10)

and then used betweenness function which outputted value 8 for every vertex and 12.5 for every edge. However, what I have understood this function does, according to me answer must be 7 for every vertex .

Can someone explain me how is it 8 and for edge 12.5?

Upvotes: 1

Views: 150

Answers (1)

Gabor Csardi
Gabor Csardi

Reputation: 10825

Assume the following graph:

str(g)
# IGRAPH U--- 10 10 -- Ring graph
# + attr: name (g/c), mutual (g/l), circular (g/l)
# + edges:
#  [1] 1-- 2 2-- 3 3-- 4 4-- 5 5-- 6 6-- 7 7-- 8 8-- 9 9--10 1--10

Let's take vertex 2, it appears on eight shortest paths:

1-2-3
1-2-3-4
1-2-3-4-5
1-2-3-4-5-6 (non-unique, 1-10-9-8-7-6)
3-2-1-10-9-8 (non-unique, 3-4-5-6-7-8)
3-2-1-10-9
3-2-1-10
4-3-2-1-10-9 (non-unique, 4-5-6-7-8-9)
4-3-2-1-10
5-4-3-2-1-10 (non-unique, 5-6-7-8-9-10)

So this is altogether 6 unique shortest paths, and four that each count as 1/2, as there is one alternative path without 2 for each. This is 6 plus 2, which is 8.

Upvotes: 1

Related Questions