Manual calculation of closeness measure and comparing with igraph package in R

3
votes

I was trying to calculate closeness of a graph using igraph package in R. Sample data that I used for calculation is as follows,

1 2
1 5
2 3    
5 4
4 6
2 5
3 4

When I do it manually, the result doesn’t match. This is the definition given by igraph for closeness:

Closeness is the inverse of the average length of the shortest paths to/from all the other vertices in the graph

Here is how I manually calculate the closeness for Node 1:

  1. First I calculate the shortest path from node 1, to each other node:

    • Node 1 can reach node 2 in 1 step, which is also the shortest path.

    • Node 1 can reach node 5 in 1 step, which is also the shortest path.

    • Node 1 can reach node 6 in 3 steps, and so on.

  2. Then, I take the average of these shortest paths:

    (1 (1→2) + 1 (1→5) + 2 (1→3) + 2 (1→4) + 3 (1→6))/5 = (1+1+2+2+3)/5 = 9/5

  3. Finally I inverse it, giving a closeness value of 0.555

When I run the closeness method in R from the igraph package, the result I obtained for Node 1 is 0.1111.

Can someone help me to find what I missed in the calculation?

2
rgraphigraph
It is odd. ?closeness gives the definition in words as you provided, but the formula on the help page is 1/sum( d(v,i), i != v) which equates to the 0.1111 value, but is the inverse sum rather than the inverse average. Maybe an email to the maintainer? – Gavin Kelly
@GavinKelly thanks for pointing it out. I emailed the maintainer. – Janani
The text in the igraph manual is wrong. Instead of 'by the inverse of the average length', it should be 'by the inverse of the total length'. – Gabor Csardi

2 Answers

1
votes

I already wrote it in a comment, but just to have an answer. The text in the igraph manual is wrong. Instead of by the inverse of the average length, it should be by the inverse of the total length.

0
votes

Actually the definition is not wrong. It is an another form of closeness definition. Please refer enter link description here. 'Inverse of the total length' is Sabidussi’s definition of closeness. In Page 226, Freeman says that

"this measure is dependent upon the number of points in the network from which it is calculated. We cannot, therefore, compare values of(closeness) for points drawn from graphs of different sizes"

One can overcome this issue by following Beauchamp definition of closeness which is the inverse of the average length. In this case we take n-1 instead of n while measuring average. There is also an implementation of closeness measure based on Beauchamp's definition is available in statnet R package.