Talk:Betweenness problem

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.