• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Tim Cooke
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Paul Clapham
  • Rob Spoor
  • Junilu Lacar
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Piet Souris
  • Carey Brown
Bartenders:

Calculating Betweenness centrality for a undirected weighted graph

 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have to implement an algorithm to calculate the betweenness centrality for an undirected weighted graph.

According wikipedia:

Calculating the betweenness and closeness centralities of all the vertices in a graph involves calculating the shortest paths between all pairs of vertices on a graph, which takes {\displaystyle \Theta (|V|^{3})}\Theta (|V|^{3}) time with the Floyd–Warshall algorithm, modified to not only find one but count all shortest paths between two nodes.




I currently did not find any explanation how to modify the floyd algorithm in order to get all shortest paths between all pairs of vertices. Can someone give me a hint or advise?
Any help is appreciated.

Thank you in advance for an answer !
 
Saloon Keeper
Posts: 14672
330
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Wikipedia mentions this pseudo-code:

I imagine what you need is something like this:

I only took a very quick look though. It's probably not correct but maybe it's enough to help you on your way.
 
Adam Ocean
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Wikipedia mentions this pseudo-code:

I imagine what you need is something like this:

I only took a very quick look though. It's probably not correct but maybe it's enough to help you on your way.




I do not understand what is meant with your multiplication



 
Master Rancher
Posts: 4353
59
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Adam Ocean wrote:I do not understand what is meant with you multiplication


Basically, when you're looking for ways to travel from i to j, and you find a new point k where it's shorter to travel from i to k and then k to j, in that case you need to update the count of ways to travel that route.  If there are X equally-short ways to travel from i to k, and there are Y equally short ways to travel from k to j, then there are X * Y ways to travel from i to j by going through k.

Simpler explanation, if you have 3 different routes to go from Los Angeles to Chicago, and 2 different ways to go from Chicago to New York, then you have 2 * 3 = 6 different ways to go from Los Angeles to New York via Chicago.

I think there are some additional changes needed whenever you find a route through k that is equal in distance to the previous best route from i to j:

So whenever you find a better distance than the previous best distance, you ignore the old count and calculate a new one.  but when you find the same distance as the previous best distance, you add to the existing count.
 
Adam Ocean
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:

Adam Ocean wrote:I do not understand what is meant with you multiplication


Basically, when you're looking for ways to travel from i to j, and you find a new point k where it's shorter to travel from i to k and then k to j, in that case you need to update the count of ways to travel that route.  If there are X equally-short ways to travel from i to k, and there are Y equally short ways to travel from k to j, then there are X * Y ways to travel from i to j by going through k.

Simpler explanation, if you have 3 different routes to go from Los Angeles to Chicago, and 2 different ways to go from Chicago to New York, then you have 2 * 3 = 6 different ways to go from Los Angeles to New York via Chicago.

I think there are some additional changes needed whenever you find a route through k that is equal in distance to the previous best route from i to j:

So whenever you find a better distance than the previous best distance, you ignore the old count and calculate a new one.  but when you find the same distance as the previous best distance, you add to the existing count.




Thank you, I did understand your explanation. I have only one problem in my implementation, it calculates the 'doubled' centrality betweenness. Let s,v,t be nodes in my program. The betwenness centrality is defined as the sum of the amount of shortest paths from s to t which include v devided with the amout of shortest paths from s to t.(s,t and v are not equal) In order to get the amount of shortest path from I am using following lemma:


Lemma: v is contained in a shortest path from s to t if:
d(s,t) = d(s,v)+ d(v,t)



d(s,t) denotes the distance from s to t

From this lemma it can be concluded that:
amount of shortest paths from s to t which include v = 0, if d(s,t) < d(s,v) + d(v,t) case
else amount of shortest paths from s to t which include v  = count[s][v]* count[v][t], else case

In order to get the centrality betweenness of a node v, I iterate over each node s,t and sum up if s,v and t are not equal.

My problem is that my algorithm returns the 'doubled' centrality betweenness. I am possible to divide it simply by 2, but I want to understand why ?
 
Mike Simmons
Master Rancher
Posts: 4353
59
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hard to say without seeing more code.  I wonder if you are initializing the counts correctly?  I'm thinking that before you run the loop with k, all count values should be either 0 or 1, nothing else.  If two nodes i and j are directly connected, then count[i][j] = 1 and count[j][i] = 1.  Otherwise both are 0.  However if you used count[i][j]++, you might have accidentally counted twice?  If you initialize count with 2's instead of 1's, then all subsequent count recalculations will be double as well..
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic