Talk:Betweenness problem

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Would be useful to add Bandes' algorithm here.

Ulrik Brandes (2001) A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25 (2) 163--177.

http://ella.slis.indiana.edu/~katy/L579/brandes.pdf

Is the formula correct

See Wasserman & Faust, page 190. CB = Sum(Gjk(n)/Gjk) This can be normalized by dividing by (g-1)(g-2)

(Please sign your messages, it makes it easier for everyone to know who is talking to whom!) The answer is I believe you are correct, and I wrote the formula in the article! The article formula assumes that there is one and only one shortest geodesic path between s and t. Thus, the correct formula should include a division by the number of shortest paths between s and t. My formula uses the same notation as Brandes (now here [1]), and is clearly wrong. I will now correct on the article page. --stochata 09:03, 17 November 2005 (UTC)[reply]

I have now changed the formula to that found in Brandes (and other sources online) as well as Wasserman & Faust. However, I cannot find my copy of Freeman from which I wrote the original, so I am wondering if there was some difference in interpretation. Could someone please check it if you have it? (I've also removed 'approximately' from my above posting -- the formulae look the same now!) --stochata 10:40, 17 November 2005 (UTC)[reply]

Requested additions

Anyone want to add Edge Betweenness? Maybe I'll come back, but I don't have a lot of time.

We also need an entry for Geodesic (graph theory) to link to. No mention of graph geodesics on the geodesic page.

Walt 13:41, 28 April 2006 (UTC)[reply]

It's unclear what is meant by "geodesic path". Is this by any chance what rest of the world calls a shortest path? If not please define.