Hi,

I am having some problems with understanding the results of the betweenness centrality calculation for my network (a directed graph). I have several nodes with very high out-degree, but zero in-degree, or vice versa and these are receiving very high scores for betweeness centrality. As they can only be on the beginning or end of a path I would expect them to score zero in a directed network. Am I misunderstanding this?

Cheers, Alex

Alex:

Yes, you are misunderstanding this.  If a vertex has very high out-degree (or in-degree, for that matter), then it is on the shortest paths between many vertex pairs, namely each pair of its many adjacent vertices.  If A is connected to B, C, and D, for example, then A is on the shortest paths between B and C, C and D, and B and D.

A vertex's betweenness centrality is determined by the number of shortest paths that include the vertex, so your high-out-degree vertex has a high betweenness centrality.

Please see the http://en.wikipedia.org/wiki/Centrality#Betweenness_centrality article for information on the betweenness centrality algorithm.

-- Tony

I forgot to mention an important fact that might better answer your question: The direction of individual edges is not taken into account when the shortest paths are determined.

-- Tony

Hi Tony,

yes, thanks! The second answer was the one that I needed. I had previously found an answer on the forum that said that directionality was taken onto account on calculating betweenness centrality (discussion:261244  Edge Weights and Betweenness). I think it would be useful to flag this up in the documentation.

Cheers,

Alex

PS Do any of the other centrality measures take directionality into account? I need to gain a measure of the relative importance of my nodes as links in a metabolic/ecological network so directionality is key.

Thanks again

Alex:

You're confusing two different things here.  The direction of individual edges is NOT taken into account when the shortest paths are determined.  However, the directionality of the graph IS taken into account in the final step of the betweenness centrality calculations, where NodeXL has to decide whether to divide the result by 2 based on the graph's directionality.  (I would copy over the relevant equations from http://en.wikipedia.org/wiki/Centrality#Betweenness_centrality to show you what I mean, but I'm sure the equation formatting wouldn't paste properly.)

So my statements here and at http://nodexl.codeplex.com/discussions/261244 are both correct.

-- Tony

Alex:

The graph's directedness is ignored when calculating PageRank, closeness centrality and eigenvector centrality.  It is taken into account, obviously, when calculating degree, in-degree and out-degree, which are also considered a type of centrality (http://en.wikipedia.org/wiki/Centrality).

-- Tony