closeness centrality

Mar 27, 2012 at 4:01 AM

I have been trying to understand how NodeXL calculates the closeness centrality metric. I thought that the method for calculating closeness centrality for a given node was to calculate the number of steps for the shortest path between the given node and every other node, take the average, and then take the reciprocal. When I do this for the Kite dataset, I get a value of 9/14 for Fernando, but NodeXL gives a value of .071. I went to the Wikipedia page that is listed for additional information on this measure, but there are at least three different measures in that section. If someone can help me, I would appreciate it! 

Mar 27, 2012 at 5:35 AM

Which version of NodeXL are you using?  Earlier versions normalized the closeness centralities; the current version (1.0.1.205) does not.

You can tell which version you have by going to NodeXL, Help, Help in the Excel ribbon.

-- Tony

Mar 27, 2012 at 5:43 AM

Ignore that last question.  I can tell by the value you quoted that you are using a later version.

-- Tony

Mar 27, 2012 at 6:11 AM

The comments in NodeXL's Graph Metrics dialog box are wrong.  NodeXL calculates closeness centrality as the inverse of the sum of the shortest distances to the graph's other vertices.  So in Fernando's case, the sum of the shortest distances is 14, and the inverse is 1/14 = 0.071.

I'll correct the dialog box comments.  Thank you for pointing out this mistake.

By the way, NodeXL actually uses a graph library called SNAP to calculate closeness centrality, because SNAP was written by some graph metric experts and calculates numbers very fast.  If you have further questions about why SNAP uses this particular definition of closeness centrality, as opposed to one of the others, you might want to contact Jure Leskovec, SNAP's leader.  He can be reached via http://snap.stanford.edu/index.html.

-- Tony

Mar 27, 2012 at 3:19 PM

Thanks Tony, that solves it. I don't know why 1/14 didn't occur to me, except I was just fixated on average distance.

This all happened because I gave my students a homework on the 9/11 hijacker network, asking them to calculate degree, closeness and betweenness measures for Hamza al-Ghamdi. I told them the rest, calculating the scores using NodeXL. When I was writing up the answers, I realized NodeXL wasn't getting the same answers I was, which I can tell you wasn't a good feeling. But it is all clear to me now, thanks to you.

Thanks also for correcting the dialog box -- although i am sure other people would have seen 1/14 sooner than I did. And thanks for the reference to SNAP -- I checked their website, but wasn't able to find what I needed, although I am sure it is there somewhere.

Doug

Mar 27, 2012 at 4:50 PM
Edited Mar 27, 2012 at 4:50 PM

Hi, Doug:

I'm surprised no one noticed my outdated dialog box comments before.  I guess it's because they're hidden behind a Details link.

If you were looking for Jure's contact information, it's at http://cs.stanford.edu/people/jure/contact.html.  Or if you were looking for the actual SNAP code that calculates closeness centrality, it's available at http://snap.stanford.edu/snap/download.html as a Zip file.  It's the method called GetClosenessCentr() in the file centr.cpp.  Like all of SNAP, it's written in C++.

-- Tony