Closeness for seperated networks

Jun 30, 2010 at 8:08 AM
Edited Jun 30, 2010 at 12:26 PM
Hello, First of all, I would like express my total thanks to the great efforts you're putting into nodeXL. I'm using the API for WPF.

In order to compute closeness, I'm using BrandesFastCentralityCalculator in my generated graph.
The problem comes when there are clusters in the graph. For example as show below:

A--B

E----C----D

A is connected to B. E,C and D are connected together. No connection between both clusters.
In this case, both A and C have closeness = 1
C has a closeness equal to 0.5.
E and D have a closeness equal to 0.3.
Is there way to calculate closeness values that take into consideration the whole graph instead of computing clusters all together?
I've seen that happen in UCINet.

Thank you for your help!
Jul 1, 2010 at 6:29 AM

Ninjusto:

I'm glad you've found the API to be useful.

Closeness centrality, by definition, treats each connected component separately.  (For reference, NodeXL uses the second equation in this Web page section: http://en.wikipedia.org/wiki/Centrality#Closeness_centrality.)  I'm not familiar with a closeness centrality algorithm that looks at the graph as a whole instead of at the graph's connected components.  Can you tell me more about what UCINET is doing, and in particular what algorithm it's using?

-- Tony

Jul 1, 2010 at 8:38 AM
Edited Jul 1, 2010 at 8:40 AM
Hi Tony,

A workaround for closeness with disconnected graphs has been suggested by Tore Opsahl here:

http://toreopsahl.com/2010/03/20/closeness-centrality-in-networks-with-disconnected-components/

And it has been mentioned in Wikipedia's Closeness paragraph in the last line:

An extension to networks with disconnected components has been proposed by Opsahl (2010).

The idea is that this closeness value (Labeled by UCINet as Harmonic Closeness) is the sum of reversed shortest path to each node, and not the reverse of the sum as in normalized closeness.

This is quite useful because 1/infinity = 0 and it works rather well for showing a scale of closeness all over the graph.
For the previous example I have provided:

C(A) = 1/P(A-B) = 1/1 = C(B) 1
C(E) = 1/P(E-C) + 1/P(E-D) = 1/1 + 1/2 = C(D) = 1.5
C(C) = 1/P(C-E) + 1/P(C-D) = 1/1 + 1/1 = 2

Values can then be normalized by n-1 to render a [0..1] value where 1 is a node connected to all other nodes.
Is there a way SNAP can calculate "Harmonic" closeness? Because otherwise, I'd have to recalculate myself, and it doesn't seem quite simple :(

Thank you for your most appreciated help and support!
Jul 5, 2010 at 5:05 PM

We will be looking into the possibility of adding this graph metric, although I can't say when it might be done.  Thank you for pointing it out.

-- Tony

Jul 7, 2010 at 8:40 AM

I managed to get my desired results by altering the source code of a previous version of BrandesFastCentralityCalculator.
Still, thank you for your input.