CODEWITHSUNDEEP
graphnetworkxgraph-theorysocial-networking
theodosis
theodosis

Reputation: 1026

How do we define betweenness centrality when weights have a positive meaning?

I've read that betweenness centrality is defined as the number of times a vertex lies on the shortest path of the other pairs of nodes.

However, in case weights have a positive meaning (i.e. the more the weight of an edge the merrier), then how does one define betweenness centrality?

In this case, is there another way to calculate betweenness centrality? Or is it simply interpreted in a different way?

Upvotes: 3

Views: 1753

Answers (1)

Matthieu Latapy
Matthieu Latapy

Reputation: 183

Computing the betweenness centrality of a vertex v relies on the following fraction, for any u and w: s(u,w,v) / s(u,w) where s(u,w,v) is the number of shortest paths between u and w that involve v, and s(u,w) is the total number of shortest paths between u and w.

With positive edge weights, I would suggest that you count each shortest path with its own weight: replace s(u,w,v) by the sum of weights of shortest paths between u and w that involve v; and s(u,w) by the sum of weights of all shortest paths between u and w.

Then, you have to define the weight of paths, and this depends on what you have in mind. You may for instance consider the sum of edge weights, their product, their minimum or maximal value, etc.

Warning: this definition still relies on shortest unweighted paths; if longer paths with higher weights exist, they will be ignored, which means that graph structure prevails. This may not be satisfactory.

Note: this approach is somewhat equivalent, if edges have integer weight and a path weight is its edge weight product, to use the classical definition on a multi-graph (an unweighted graph where several edges may exist between two same vertices).

Upvotes: 3

Related Questions