How does NodeXL compute betweenness

Sep 30, 2014 at 3:36 PM
Doesn't seem to use Freeman's method. For example, in a chain, number the vertices from left to right: 1, 2, 3, 4, 5. Vertex 3, in the middle of the chain is between (i.e. is an interior vertex on a geodesic between) 4 other pairs of vertices (1,4), (1,5), (2,4), (2,5), and when you divide through by the total possible (n-1)(n-2)/2, i.e., in this case 6, you get two thirds, or about .67, which agrees with the example in Freeman's centrality article. Vertex 2 is between three 3 pairs: (1,3), (1,4), (1,5), making its betweenness 3/6 = .5, again agreeing with Freeman's article.

However, when I run this network in NodeXL, the betweenness for vertex 3 is given as 1.000 and the betweenness for vertex 2 is given as .750., which does not agree with the results above. In fact for every network I have tried, one of the vertices is given a betweennees of 1.00, which makes me think that NodeXL is somehow "stretching" the Freeman betweenness to fit a zero-one scale for that network. For example, if I multiply the Freeman betweennesses in the chain by 3/2, I get 1.00 for vertex 3 and .75 for vertex 2 (and the other vertices also agree).

Why would one want to compute them this way (if in fact that's what they are doing)? In order to turn a NodeXL betweenness into a Freeman betweeenness I would have to compute the Freeman betweenness of the most central vertex to figure out how to "de-scale" the NodeXL betweennesses into Freeman betweennesses.

Any insight?

Thanks,
--frank
Coordinator
Oct 13, 2014 at 6:59 AM
A vertex that occurs on many shortest paths between other vertices has a larger betweenness centrality than vertices that do not.

Betweenness centrality is defined in this article:
NodeXL uses the algorithm described in the paper "A Faster Algorithm for Betweenness Centrality," by Ulrik Brandes.

The paper can be found here:
Oct 14, 2014 at 12:03 AM
Marc, thanks for replying.

I checked out both references. The Wikipedia page defines the usual Freeman betweenness measure from his 1978/1979 Social Networks article (though with a slight notational change), a measure I'm very familiar with.

As for the Brandes article, I confess I have not worked through the algorithm in detail (though will do so when I can set aside some time), but his definition matches Freeman/Wikipedia, and that's what he purports to compute. My brief perusal leads me to believe that he is simply counting (appropriately weighted in the case of multiple geodesics) the number of times a node is between others. If that is the case, then for the center node of a five-person chain you should get a betweenness of 4 (unnormalized) or .67 (normalized). Yet NodeXL reports the betweenness centrality of such a node as 1.00.

In a network with no multiple geodesics between nodes (the chain is such a network), the only way you can get a betweenness of 1.00 is, in the unnormalized case, if you are between only one pair of nodes (obviously not the case), or, in the normalized case, if you are between all pairs of nodes, again not the case for the center node of a chain.

That's why I surmise that NodeXL is using the Brandes algorithm to count the number of times a node is between other node, but then taking the node with the highest betweenness and assigning it a score of 1.00, proportionally adjusting the scores of the nodes with lower centrality to fit into this new 0-1 scale. Am I off base?
Thanks again!
--frank
Dec 5, 2014 at 12:08 PM
Dear Frank,
I think you are 100% correct but the new version of Node XL does not not normalise it anymore. I´m using version 1.0.1.334.
I´m struggling with a somewhat related issue and I found a comment in the NodeXL Teaching Resources page (in the part of the NodeXL Sample Files ) that I think answers (at least parcially) your question:

"ABC-D_email list network - Discussion list network discussed in Chapter 9 of the book. Note that Eigenvector centrality is calculated slightly differently, as is Betweeness Centrality (which used to be normalized to the node with the highest score, but no longer is)."

http://nodexl.codeplex.com/wikipage?title=NodeXL%20Teaching%20Resources

Hope this helps.
Sonia
Dec 6, 2014 at 1:34 AM
Thanks!

Sent from my iPhone - Frank