CODEWITHSUNDEEP
rsocial-networkingigraph
user2658742
user2658742

Reputation: 149

Calculation of betweenness in iGraph

I've seen some info suggesting that closeness in iGraph weighted graphs is calculated using the weights as costs, rather than strengths.

I'm wondering if this is also true for betweenness. i.e, if I have two paths between vertices, one of them (a) with edge weights summing to 100 and the other (b) to 200, betweenness will interpret path a as the least costly path and include this edge weight value in the numerator of the betweenness calculation.

If so, to obtain betweenness based on strength, I assume one would transform the weights to equal 1/weight?

I've tried to test this with a three node edge file as follows:

V1  V2 weight
1    2      1
1    3      4
2    3      1

Using the weights as supplied above, node 2 has a betweenness of 1, and others=0. This seems to indicate that the betweenness calculation is avoiding the path from 2->1->3 because it's viewing the high weights as a cost.

However, if I create a new weighting variable: E(g)$weightI <- 1/E(g)$weight

And run betweenness: b<-data.frame(betweenness(g, V(g), directed=FALSE, weights=E(g)$weightI)),

all the betweenness values are 0, which is unexpected and not especially helpful in sorting out my initial question

Upvotes: 4

Views: 5757

Answers (1)

Tam&#225;s
Tam&#225;s

Reputation: 48101

Indeed, igraph assumes that the weights of the edges in betweenness calculation are costs, not strengths. This is because (as far as I know) betweenness is defined in terms of shortest paths, and the "length" of a path in graph theory is the sum of the lengths (weights) of the edges involved. There is no clear definition of "betweenness based on strengths". You can try to transform your "strengths" to costs, but you can get different results depending on the transformation you choose as some transformation may indicate that one particular path is shorter in the transformed graph and some other transformation may indicate that some other path is shorter.

Upvotes: 7

Related Questions