Win a copy of Machine Learning for Business: Using Amazon SageMaker and JupyterE this week in the Jython/Python forum
or Object Design Style Guide in the Object-Oriented programming forum!
  • 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
  • Knute Snortum
Sheriffs:
  • Liutauras Vilda
  • Tim Cooke
  • Junilu Lacar
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Joe Ess
  • salvin francis
  • fred rosenberger

Calculating Betweenness centrality for a undirected weighted graph

 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • 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: 11188
244
  • Mark post as helpful
  • send pies
  • 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
  • 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



 
Rancher
Posts: 3419
34
  • Likes 2
  • Mark post as helpful
  • send pies
  • 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
  • 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
Rancher
Posts: 3419
34
  • Mark post as helpful
  • send pies
  • 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..
 
It's feeding time! Give me the food you were going to give to this tiny ad:
Sauce Labs - World's Largest Continuous Testing Cloud for Websites and Mobile Apps
https://coderanch.com/t/722574/Sauce-Labs-World-Largest-Continuous
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!