Tore Opsahl

Node Centrality in Two-mode Networks

The centrality of nodes, or the identification of which nodes are more “central” than others, has been a key issue in network analysis (Freeman, 1978). Freeman (1978) argued that central nodes were those “in the thick of things” or focal points. Based on this concept, he formalised three measures: degree, closeness, and betweenness. For a more complete background on these measures, see Node Centrality in Weighted Networks.

Degree

Degree is the number of ties a node has or the number other nodes that a node is connected to. In two-mode networks, this concept can be directly applied. Nevertheless, there is a slight complications. In two-mode networks, “the number of other nodes that a node is connected to” is ambiguous. It could either be the number of secondary nodes a primary node is connected to (and vice versa), or the number of primary nodes a primary node is connected to. To clarify the difference between these two numbers, I referred to them as nodes’ two-mode and one-mode degree, respectively. To exemplify the difference, the image below shows the local network surrounding Flora in the Davis’ (1940) Southern Women Dataset (adapted from Opsahl, 2011).

The local network surrounding Flora

As can be seen from this diagram, Flora’s two-mode degree is 2 and the one-mode degree is 12. If the network was projected to a one-mode network, the standard degree measure would be 12.

It is also possible to get at nodes’ two-mode degree after a network has been projected using Newman’s (2001) method. This projection method was developed for scientific co-authorship networks, and sets the tie weight between two authors equal to the sum across co-authored papers of 1 over number of authors on that paper minus 1. In other words, for each co-authored paper, a node divides 1 by the other authors. As such, the total tie weight is equal to the number of co-authored papers. The only difference between this method and the two-mode degree is single authored papers. These are excluded in the first and included in the second method.

Closeness and Betweenness

The main part of the closeness and betweenness measures is shortest paths and their length. Closeness is the inverse sum of the shortest paths’ lengths, and betweenness is the number of shortest paths that pass through a node. By taking advantage of the two-mode shortest path algorithm, it is possible easily extend these two measures to two-mode networks. To quickly recap this algorithm:

1. Use an appropriate projection method
2. Use the method for identifying the shortest paths, and calculating their length, in weighted one-mode networks (Brandes, 2001; Dijkstra, 1959; Newman, 2001)

When the length of the shortest paths are found, the closeness measure would simply be the inverse sum of them. Similarly, betweenness would easily be calculate by looking at the intermediary nodes on the shortest paths, and count, for each node, the number of times that node is an intermediary. Note: if there are multiple shortest paths, it is important to divide by the number of them to ensure that each path only counts once.

Example

To illustrate the four measures, I rely Davis’ (1940) Southern Women Dataset. The meeting attendance of 18 women at 14 meetings is recorded in this dataset. The table below shows the result of the four measures (Newman’s, 2001, projection method is used for closeness and betweenness as the interaction-level among participants at smaller events are likely to be higher).

A key limitation of the betweenness measure can be seen in this table: most people attain a score of 0 (i.e., the measure is zero-inflated). The pair-wise correlations among the measures are reported below. While all measure have high correlations, it is interesting to note that the two-mode degree-measure has a higher correlation with closeness and betweenness than the one-mode degree-measure. This might suggests that the computationally cheap two-mode degree-measure is better able to replicate the computationally expensive closeness and betweenness measures.

Want to try it with your data?

The measures can be calculated using tnet. First, you need to download and install tnet in R. Then, you need to create an edgelist of your network (see the data structures in tnet for two-mode networks). The commands below show how the tables above were created.

# Load tnet and the Southern Women Dataset
library(tnet)
data(tnet)
net <- Davis.Southern.women.2mode 

# Calculate two-mode degree
out <- degree_tm(net, measure="degree")

# Create one-mode projection
net1 <- projecting_tm(net, "Newman")

# Calculate one-mode degree
tmp <- degree_w(net1)[,"degree"]

# Append to table
out <- data.frame(out, onemodedegree=tmp)

# Calculate closeness and append to table
tmp <- closeness_w(net1 )[,"closeness"]
out <- data.frame(out, closeness=tmp)

# Calculate betweenness and append to table
tmp <- betweenness_w(net1 )[,"betweenness"]
out <- data.frame(out, betweenness=tmp)

# Download and set names
out[,"node"] <- read.table("http://opsahl.co.uk/tnet/datasets/Davis_southern_club_women-name.txt")

# Pair-wise correlation table
tmp <- matrix(nrow=4, ncol=4)
tmp[lower.tri(tmp)] <- apply(which(lower.tri(tmp), arr.ind=TRUE)+1, 1, function(a) cor.test(out[,a[1]], out[,a[2]])$estimate)

References

Brandes, U., 2001. A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25, 163-177.

Davis, A., Gardner, B. B., Gardner, M. R., 1941. Deep South. University of Chicago Press, Chicago, IL.

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.

Newman, M. E. J., 2001. Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. Physical Review E 64, 016132.

Opsahl, T., 2013. Triadic closure in two-mode networks: Redefining the global and local clustering coefficients. Social Networks 35, doi:10.1016/j.socnet.2011.07.001.

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