Closeness centrality in networks with disconnected components

Closeness centrality in networks with disconnected components

A key node centrality measure in networks is closeness centrality (Freeman, 1978; Opsahl et al., 2010; Wasserman and Faust, 1994). It is defined as the inverse of farness, which in turn, is the sum of distances to all other nodes. As the distance between nodes in disconnected components of a network is infinite, this measure cannot be applied to networks with disconnected components (Opsahl et al., 2010; Wasserman and Faust, 1994). This post highlights a possible work-around, which allows the measure to be applied to these networks and at the same time maintain the original idea behind the measure.

This network gives a concrete example of the closeness measure. The distance between node G and node H is infinite as a direct or indirect path does not exist between them (i.e., they belong to separate components). As long as at least one node is unreachable by the others, the sum of distances to all other nodes is infinite. As a consequence, researchers have limited the closeness measure to the largest component of nodes (i.e., measured intra-component). The distance matrix for the nodes in the sample network is:

	Nodes												All inclusive		Intra-component
	A	B	C	D	E	F	G	H	I	J	K		Farness	Closeness	Farness	Closeness
A	…	1	1	2	2	3	3	Inf	Inf	Inf	Inf		Inf	0	12	0.08
B	1	…	1	2	1	2	3	Inf	Inf	Inf	Inf		Inf	0	10	0.10
C	1	1	…	1	2	2	2	Inf	Inf	Inf	Inf		Inf	0	9	0.11
D	2	2	1	…	2	1	1	Inf	Inf	Inf	Inf		Inf	0	9	0.11
E	2	1	2	2	…	1	3	Inf	Inf	Inf	Inf		Inf	0	11	0.09
F	3	2	2	1	1	…	2	Inf	Inf	Inf	Inf		Inf	0	11	0.09
G	3	3	2	1	3	2	…	Inf	Inf	Inf	Inf		Inf	0	14	0.07
H	Inf	Inf	Inf	Inf	Inf	Inf	Inf	…	1	2	Inf		Inf	0	3	0.33
I	Inf	Inf	Inf	Inf	Inf	Inf	Inf	1	…	1	Inf		Inf	0	2	0.50
J	Inf	Inf	Inf	Inf	Inf	Inf	Inf	2	1	…	Inf		Inf	0	3	0.33
K	Inf	Inf	Inf	Inf	Inf	Inf	Inf	Inf	Inf	Inf	…		Inf	0	0	Inf

Although the intra-component closeness scores are not infinite for all the nodes in the network, it would be inaccurate to use them as a closeness measure. This is due to the fact that the sum of distances would contain different number of paths (e.g., there are two distance from node H to other nodes in its component, while there are six distances from node G to other nodes in its component). In fact, nodes in smaller components would generally be seen as being closer to others than nodes in larger components. Thus, researchers has focused solely on the largest component. However, this leads to a number of methodological issues, including sample selection.

To develop this measure, I went back to the original equation:

where  is the focal node,  is another node in the network, and  is the shortest distance between these two nodes. In this equation, the distances are inversed after they have been summed, and when summing an infinite number, the outcome is infinite. To overcome this issue while staying consistent with the existing measure of closeness, I took advantage of the fact that the limit of a number divided by infinity is zero. Although infinity is not an exact number, the inverse of a very high number is very close to 0. In fact, 0 is returned if you enter 1/Inf in the statistical programme R. By taking advantage of this feature, it is possible to rewrite the closeness equation as the sum of inversed distances to all other nodes instead of the inversed of the sum of distances to all other nodes. The equation would then be:

To exemplify this change, for the example network above, the inversed distances and closeness scores are:

	Nodes												Closeness
	A	B	C	D	E	F	G	H	I	J	K		Sum	Normalized
A	…	1.00	1.00	0.50	0.50	0.33	0.33	0	0	0	0		3.67	0.37
B	1.00	…	1.00	0.50	1.00	0.50	0.33	0	0	0	0		4.33	0.43
C	1.00	1.00	…	1.00	0.50	0.50	0.50	0	0	0	0		4.50	0.45
D	0.50	0.50	1.00	…	0.50	1.00	1.00	0	0	0	0		4.50	0.45
E	0.50	1.00	0.50	0.50	…	1.00	0.33	0	0	0	0		3.83	0.38
F	0.33	0.50	0.50	1.00	1.00	…	0.50	0	0	0	0		3.83	0.38
G	0.33	0.33	0.50	1.00	0.33	0.50	…	0	0	0	0		3.00	0.30
H	0	0	0	0	0	0	0	…	1.00	0.50	0		1.50	0.15
I	0	0	0	0	0	0	0	1.00	…	1.00	0		2	0.20
J	0	0	0	0	0	0	0	0.50	1.00	…	0		1.50	0.15
K	0	0	0	0	0	0	0	0	0	0	…		0	0

As can be seen from this table, a closeness score is attained for all nodes taking into consideration an equal number of distances for each node irrespective of the size of the nodes’ component. Moreover, nodes belonging to a larger component generally attains a higher score. This is deliberate as these nodes can reach a greater number of others than nodes in smaller components. The normalized scores are bound between 0 and 1. It is 0 if a node is an isolate, and 1 if a node is directly connected all others.

This measure can easily be extended to weighted networks by introducing Dijkstra’s (1959) algorithm as proposed in Average shortest distance in weighted networks.

References

Dijkstra, E. W., 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269-271.

Freeman, L. C., 1978. Centrality in social networks: Conceptual clarification. Social Networks 1, 215-239.

Opsahl, T., Agneessens, F., Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks 32, 245-251.

Wasserman, S., Faust, K., 1994. Social Network Analysis: Methods and Applications. Cambridge University Press, New York, NY.

What to try it with your data?

Below is the code to calculate the closeness measure on the sample network above.

1 2 3 4 5 6 7 8 9 10 11 12

# Load tnet library(tnet)   # Load network # Node K is assigned node id 8 instead of 10 as isolates at the end of id sequences are not recorded in edgelists net <- cbind(   i=c(1,1,2,2,2,3,3,3,4,4,4,5,5,6,6,7,9,10,10,11),   j=c(2,3,1,3,5,1,2,4,3,6,7,2,6,4,5,4,10,9,11,10),   w=c(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1))   # Calculate measures closeness_w(net, gconly=FALSE)

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