Social Network Analysis

Worksheet 4a: Network Concepts and Descriptives II ¹

Author

Termeh Shafie

library(igraph)
library(networkdata)
library(netUtils)
library(ggraph)
library(kableExtra)
library(corrplot)
library(tidygraph)

Blockmodels using CONCOR

The example we considered in lecture concerns the relatively small network. What happens when we apply the method of iterated correlations (CONCOR) to a bigger network, something like the one shown below?

First save the function below for computing the correlation distance between pairs of nodes:

#function:
corr.dist <- function(x) {
         r <- nrow(x)
         c <- ncol(x)
         r.c <- matrix(0, r, r)
         c.c <- matrix(0, c, c)
         r.m <- rowMeans(x)
         c.m <- colMeans(x)
         
         for (i in 1: r) {
              for (j in 1:r) {
                   r.x <- x[i, ] - r.m[i]
                   r.y <- x[j, ] - r.m[j]
                   r.xy <- r.x * r.y
                   r.xx <- r.x^2
                   r.yy <- r.y^2
                   r.num <- sum(r.xy)
                   r.den <- sqrt(sum(r.xx)) * sqrt(sum(r.yy))
                   r.c[i, j] <- round(r.num / r.den, 2)
              }
         }
         rownames(r.c) <- rownames(x)
         colnames(r.c) <- rownames(x)
         return(r.c)
}

Let’s start by definig the graph:

fr <- c(rep(1, 5), rep(2, 5), rep(3, 5), rep(4, 3), rep(20, 3))
    to <- c(5:9, 10:14, 15:19, 1:3, 5, 21, 22)
    edge.dat <- data.frame(fr, to)
    node.dat <- data.frame(name = toupper(letters[union(fr, to)]))
    gr <- tbl_graph(edges = edge.dat, nodes = node.dat, directed = FALSE)
    gr <- as_tbl_graph(simplify(gr))

Well, we can begin by computing the correlation distance across all the \(22\) nodes in that network.

Note that even before we do any iterated correlations of correlation matrices we can see that the peripheral, single-connection nodes \(E, F, G, H\), \(I, J, K, L, M\) and \(N, O, P, Q, R\) are perfectly structurally equivalent. This makes sense, because all the nodes in each of these three groups have identical neighborhoods, since they happen to be connected to the same central node \(A\) for the first group, \(B\) for the second group and \(C\) for the third group. Note also that \(U\) and \(V\) are structurally equivalent, since their neighborhoods are the same: Their single connection is to node \(S\).

a <- matrix(as_adjacency_matrix(gr), nrow = length(V(gr)))
    rownames(a) <- V(gr)$name
    colnames(a) <- V(gr)$name
    
b <- corr.dist(a)

What happens when we take the correlation distance of the correlation distance matrix shown in Table 1 (a), and the correlation distance of the resulting matrix, and keep going until we only have zeros and ones? The results is Table 1 (b). This matrix seems to reveal a much deeper pattern of commonalities in structural positions across the nodes in Figure 1.

b <- corr.dist(a)
c <- b
k <- 1
while (mean(abs(c)) != 1) {
      c <- corr.dist(c)
      k <- k + 1
  }

(a) Original Correlation Distance Matrix.

	A	B	C	D	T	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	U	V
A	1.00	-0.15	-0.15	-0.24	-0.19	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	0.05	-0.13	-0.13
B	-0.15	1.00	-0.15	-0.24	-0.19	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.24	-0.13	-0.13
C	-0.15	-0.15	1.00	-0.24	-0.19	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.13	-0.24	-0.13	-0.13
D	-0.24	-0.24	-0.24	1.00	0.34	0.55	0.55	0.55	0.55	0.55	0.55	0.55	0.55	0.55	0.55	0.55	0.55	0.55	0.55	-0.16	-0.09	-0.09
T	-0.19	-0.19	-0.19	0.34	1.00	0.69	0.69	0.69	0.69	-0.07	-0.07	-0.07	-0.07	-0.07	-0.07	-0.07	-0.07	-0.07	-0.07	-0.13	0.69	0.69
E	-0.13	-0.13	-0.13	0.55	0.69	1.00	1.00	1.00	1.00	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.09	-0.05	-0.05
F	-0.13	-0.13	-0.13	0.55	0.69	1.00	1.00	1.00	1.00	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.09	-0.05	-0.05
G	-0.13	-0.13	-0.13	0.55	0.69	1.00	1.00	1.00	1.00	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.09	-0.05	-0.05
H	-0.13	-0.13	-0.13	0.55	0.69	1.00	1.00	1.00	1.00	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.09	-0.05	-0.05
I	-0.13	-0.13	-0.13	0.55	-0.07	-0.05	-0.05	-0.05	-0.05	1.00	1.00	1.00	1.00	1.00	-0.05	-0.05	-0.05	-0.05	-0.05	-0.09	-0.05	-0.05
J	-0.13	-0.13	-0.13	0.55	-0.07	-0.05	-0.05	-0.05	-0.05	1.00	1.00	1.00	1.00	1.00	-0.05	-0.05	-0.05	-0.05	-0.05	-0.09	-0.05	-0.05
K	-0.13	-0.13	-0.13	0.55	-0.07	-0.05	-0.05	-0.05	-0.05	1.00	1.00	1.00	1.00	1.00	-0.05	-0.05	-0.05	-0.05	-0.05	-0.09	-0.05	-0.05
L	-0.13	-0.13	-0.13	0.55	-0.07	-0.05	-0.05	-0.05	-0.05	1.00	1.00	1.00	1.00	1.00	-0.05	-0.05	-0.05	-0.05	-0.05	-0.09	-0.05	-0.05
M	-0.13	-0.13	-0.13	0.55	-0.07	-0.05	-0.05	-0.05	-0.05	1.00	1.00	1.00	1.00	1.00	-0.05	-0.05	-0.05	-0.05	-0.05	-0.09	-0.05	-0.05
N	-0.13	-0.13	-0.13	0.55	-0.07	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	1.00	1.00	1.00	1.00	1.00	-0.09	-0.05	-0.05
O	-0.13	-0.13	-0.13	0.55	-0.07	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	1.00	1.00	1.00	1.00	1.00	-0.09	-0.05	-0.05
P	-0.13	-0.13	-0.13	0.55	-0.07	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	1.00	1.00	1.00	1.00	1.00	-0.09	-0.05	-0.05
Q	-0.13	-0.13	-0.13	0.55	-0.07	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	1.00	1.00	1.00	1.00	1.00	-0.09	-0.05	-0.05
R	-0.13	-0.13	-0.13	0.55	-0.07	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	1.00	1.00	1.00	1.00	1.00	-0.09	-0.05	-0.05
S	0.05	-0.24	-0.24	-0.16	-0.13	-0.09	-0.09	-0.09	-0.09	-0.09	-0.09	-0.09	-0.09	-0.09	-0.09	-0.09	-0.09	-0.09	-0.09	1.00	-0.09	-0.09
U	-0.13	-0.13	-0.13	-0.09	0.69	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.09	1.00	1.00
V	-0.13	-0.13	-0.13	-0.09	0.69	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.05	-0.09	1.00	1.00

(b) Original Correlation Distance Matrix After Ten Iterations.

	A	B	C	D	T	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	U	V
A	1	1	1	-1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1
B	1	1	1	-1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1
C	1	1	1	-1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1
D	-1	-1	-1	1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1
T	1	1	1	-1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1
E	1	1	1	-1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1
F	1	1	1	-1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1
G	1	1	1	-1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1
H	1	1	1	-1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1
I	-1	-1	-1	1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1
J	-1	-1	-1	1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1
K	-1	-1	-1	1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1
L	-1	-1	-1	1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1
M	-1	-1	-1	1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1
N	-1	-1	-1	1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1
O	-1	-1	-1	1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1
P	-1	-1	-1	1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1
Q	-1	-1	-1	1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1
R	-1	-1	-1	1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1
S	1	1	1	-1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1
U	1	1	1	-1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1
V	1	1	1	-1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1

	V	U	S	H	G	F	E	T	C	A	B	R	Q	P	O	N	M	L	K	J	D	I
V	1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
U	1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
S	1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
H	1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
G	1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
F	1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
E	1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
T	1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
C	1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
A	1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
B	1	1	1	1	1	1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
R	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	1
Q	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	1
P	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	1
O	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	1
N	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	1
M	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	1
L	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	1
K	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	1
J	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	1
D	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	1
I	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	1	1

Table 1: Correlation Distance Matrices Corresponding to an Undirected Graph.

Running the below code to reshufffke nodes gives the result in Table 1 (c):

rs <- corrMatOrder(c, order = "hclust")
d <- c[rs, rs]

So it turns out that there is indeed a secret pattern! The reshuffling shows that the nodes in the network can be divided into two blocks such within blocks all nodes are structurally similar (and some structurally equivalent) and across blocks, all nodes are structurally dissimilar. Thus \(V, U, S, H, G, F, E, T, C, A, B\) are members of one structurally similar block (let’s called them “Block 1”), and nodes \(R, Q, P, O, N, M, L, K, J, D, I\) are members of another structurally similar block (let’s called them “Block 2”). Nodes in “Block 1” are structurally dissimilar from nodes in “Block 2,” but structurally similar to one another and vice versa. To illustrate, Figure 2 is the same as Figure 1, but this time nodes are colored by their memberships in two separate blocks.

    node.color <- c(rep("tan3",3), "steelblue", "tan3", rep("tan3", 4), rep("steelblue", 10), "tan3", rep("tan3", 2))
    p <- ggraph(gr, layout = 'kk') 
    p <- p + geom_edge_link(color = "black", width = 1.15) 
    p <- p + geom_node_point(aes(x = x, y = y), color = node.color, size = 22)
    p <- p + geom_node_text(aes(label = name), size = 10, color = "white")
    p <- p + theme_graph()
    p

Figure 2: An undirected graph with block membership indicated by node color.

Note that we haven’t changed any of the information in Table 1 (b) to get Table 1 (c). If you check, the row and column entries for each node in both figures are identical. It’s just that we changed the way the rows ordered vertically and the way the columns are ordered horizontally. For instance, node \(A\)’s pattern of connections is negatively correlated with node \(I\)’s in Table 1 (b), and has the same negative correlation entry in Table 1 (c). The same goes for each one of node \(A\)’s other correlations, and the same for each node in the table. Table 1 (b) and Table 1 (c) contain the same information it’s just that Table 1 (c) makes it easier to see a hidden pattern.

This property of the method of iterated correlations is the basis of a strategy for uncovering blocks of structurally similar actors in a network developed by a team of sociologists, physicists, and mathematicians working at Harvard in the 1970s. The technique is called blockmodeling. Let’s see how it works.

We Need to go Deeper!

Of course, as Leo says: “We need to go deeper.” And indeed we can. What happens if we do the same analysis as above, but this time in the two node-induced subgraphs defined by the set of structurally similar nodes in each of the two blocks we uncovered in the original graph?

Running the below codes gives you the results in Table 2 (a) and Table 2 (b):

    b1 <- b[rs[1:11], rs[1:11]]
    b2 <- b[rs[12:22], rs[12:22]]
    
    c1 <- b1
    while (mean(abs(c1)) != 1) {
      c1 <- corr.dist(c1)
      }
    
    c2 <- b2
    while (mean(abs(c2[c2 != 0])) != 1) {
      c2 <- corr.dist(c2)
      }
    rs1 <- corrMatOrder(c1, order = "hclust")
    d1 <- c1[rs1, rs1]
    d1
    rs2 <- corrMatOrder(c2, order = "hclust")
    d2 <- c2[rs2, rs2]
    d2

Table 2: Subgraph Blockmodels

(a) Blockmodel of a subgraph.

	B	A	C	S	V	U	T	E	F	H	G
B	1	1	1	1	1	1	-1	-1	-1	-1	-1
A	1	1	1	1	1	1	-1	-1	-1	-1	-1
C	1	1	1	1	1	1	-1	-1	-1	-1	-1
S	1	1	1	1	1	1	-1	-1	-1	-1	-1
V	1	1	1	1	1	1	-1	-1	-1	-1	-1
U	1	1	1	1	1	1	-1	-1	-1	-1	-1
T	-1	-1	-1	-1	-1	-1	1	1	1	1	1
E	-1	-1	-1	-1	-1	-1	1	1	1	1	1
F	-1	-1	-1	-1	-1	-1	1	1	1	1	1
H	-1	-1	-1	-1	-1	-1	1	1	1	1	1
G	-1	-1	-1	-1	-1	-1	1	1	1	1	1

(b) Another Blockmodel of another subgraph

	I	J	K	M	L	D	N	O	P	R	Q
I	1	1	1	1	1	0	-1	-1	-1	-1	-1
J	1	1	1	1	1	0	-1	-1	-1	-1	-1
K	1	1	1	1	1	0	-1	-1	-1	-1	-1
M	1	1	1	1	1	0	-1	-1	-1	-1	-1
L	1	1	1	1	1	0	-1	-1	-1	-1	-1
D	0	0	0	0	0	1	0	0	0	0	0
N	-1	-1	-1	-1	-1	0	1	1	1	1	1
O	-1	-1	-1	-1	-1	0	1	1	1	1	1
P	-1	-1	-1	-1	-1	0	1	1	1	1	1
R	-1	-1	-1	-1	-1	0	1	1	1	1	1
Q	-1	-1	-1	-1	-1	0	1	1	1	1	1

We can see that Table 1 (b) separates our original Block 2 into two further sub-blocks. Let’s call them “Block 2a” and “Block 2b.” Block 2a is composed of nodes \(A, B, C, S, U, V\) and Block 2b is composed of nodes \(E, F, G, H, T\).

Let’s separates our original Block 2 into three further sub-blocks, as shown in Table 1 (b). There’s the block composed of nodes \(I, J, K, L, M\). Let’s call this “Block 2a”, the block composed of nodes \(N, O, P, Q, R\). Let’s call this “Block 2b.” Then, there’s node \(D\). Note that this node is only structurally similar to itself and is neither similar nor dissimilar to the other nodes in the subgraph \(d^{corr} = 0\), so it occupies a position all by itself! Let’s call it “Block 2c.”

    n <- c("B", "A", "C", "S", "V", "U")
    b3 <- b[n, n]

    c3 <- b3
    while (mean(abs(c3)) != 1) {
      c3 <- corr.dist(c3)
    }
    rs3 <- corrMatOrder(c3, order = "hclust")
    d3 <- c3[rs3, rs3]
    d3
    
    n <- c("B", "A", "C", "S")
    b4 <- b[n, n]
    c4 <- b4
    while (mean(abs(c4)) != 1) {
      c4 <- corr.dist(c4)
    }
    rs4 <- corrMatOrder(c4, order = "hclust")
    d4 <- c4[rs4, rs4]
    d4

Table 3: Subgraph Blockmodels

(a) Blockmodel of a subgraph.

	S	C	B	A	V	U
S	1	1	1	1	-1	-1
C	1	1	1	1	-1	-1
B	1	1	1	1	-1	-1
A	1	1	1	1	-1	-1
V	-1	-1	-1	-1	1	1
U	-1	-1	-1	-1	1	1

(b) Another Blockmodel of another subgraph

	B	C	A	S
B	1	1	-1	-1
C	1	1	-1	-1
A	-1	-1	1	1
S	-1	-1	1	1

Now let’s do a couple of final splits of the subgraph composed of nodes \(A, B, C, S, U, V\). This is shown in Table 3. The first split separates nodes in block \(A, B, C, S\) from those in block \(U, V\) (Table 3 (a)). The second splits the nodes in subgraph \(A, B, C, S\) into two blocks composed of \(A, S\) and \(B, C\), respectively (Table 3 (b)).

node.color <- c("firebrick", rep("steelblue", 2), "purple", rep("tan3", 5), rep("darkgreen", 5), rep("#CC79A7", 5), "firebrick", rep("darkturquoise", 2))
    p <- ggraph(gr, layout = 'kk') 
    p <- p + geom_edge_link(color = "black", width = 1.15) 
    p <- p + geom_node_point(aes(x = x, y = y), color = node.color, size = 22)
    p <- p + geom_node_text(aes(label = name), size = 10, color = "white")
    p <- p + theme_graph()
    p

Figure 3: An undirected graph with block membership indicated by node color.

Figure 3 shows the nodes in Figure 1 colored according to our final block partition. It is clear that the blockmodeling approach captures patterns of structural similarity. For instance, all the single-connection nodes connected to more central nodes get assigned to their own position: Block 1b: \(E, F, G, H, T\), Block 2a: \(I, J, K, L, M\), and Block 2b: \(N, O, P, Q, R\). The most central node \(D\) (in terms of Eigenvector centrality) occupies a unique position in the graph. Two of the three central nodes (in terms of degree centrality) \(B, C\) get assigned to their own position. Meanwhile \(A, S\) form their own structurally similar block. Finally, \(U, V\) also form their own structurally similar block as both are structurally equivalent in the orignal graph.

The Blocked Adjacency Matrix

What happens if we were to go back fo the adjacency matrix corresponding to Figure 1, and then reshuffle the rows and columns to correspond to all these wonderful blocks we have uncovered? Well, we would en up with something like Table 4. This is called the blocked adjacency matrix. In the blocked adjacency matrix, the division between the nodes corresponding to each block of structurally similar nodes in Table 2 and Table 3 is marked by thick black lines going across the rows and columns.

Each diagonal rectangle in Table 4 corresponds to within-block connections. Each off-diagonal rectangle corresponds to between block connections. There are two kinds of rectangles in the blocked adjacency matrix. First, there are rectangles that only contains zero entries. These are called zero blocks. For instance the top-left rectangle in Table 4 is a zero block. Then there rectangles that have some non-zero entries in them (ones, since this is a binary adjacency matrix). These are called one blocks. For instance, the fourth rectangle going down the rows (corresponding to the block that nodes \(B, C\) belong to) is a one block.

	I	J	K	L	M	N	O	P	Q	R	T	E	F	G	H	B	C	A	S	U	V	D
I	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
J	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
K	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
L	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
M	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
N	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
O	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
P	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
Q	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
R	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
T	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	0	0
E	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
F	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
G	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
H	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
B	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
C	0	0	0	0	0	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	1
A	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	0	0	0	0	0	0	1
S	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	1	1	0
U	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
V	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
D	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0	0	0	0

Table 4: Blocked adjancency matrix.

Zero-blocks indicate that the members of the row block don’t have any connections with the members the column block (which can include themselves!). For instance, the zero-block in the top-left corner of the blocked adjacency matrix in Table 4 indicates that the members of this block are not connected to one another in the network (and we can verify from Figure 3 that this is indeed the case).

One blocks indicate that the members of the column block share some connections with the members of the column block (which can also include themselves!). For instance, the one-block in the fourth rectangle going down the rows (corresponding to the block that nodes \(B, C\) belong to) tells us that members of this block are connected to at least one member of the \(I, J, K, L, M\) block (and we can verify from Figure 3 that this is indeed the case, since \(B\) is connected to all of them).

The Image Matrix

From this reshuffled adjacency matrix, we can get to a reduced image matrix containing the relations not between the nodes in the graph, but between the blocks in the graph. The way we proceed to construct the image matrix is as follows:

First we create an empty matrix \(\mathbf{B}\) of dimensions \(b \times b\) where \(B\) is the number of blocks in the blockmodel. In our example, \(b = 7\) so the image matrix has seven rows and seven columns. The \(ij^{th}\) cell in the image matrix \(\mathbf{B}\) records the relationship between row block i and column block j in the blockmodel.
Second, we put a zero in the image matrix if the rectangle corresponding to the relationship between blocks i and j in Table 4 is a zero-block.
Third, we put a one in the image matrix if the rectangle corresponding to the relationship between blocks i and j in Table 4 is a one-block.

The result is Table 5:

c <- matrix(c(0, 0, 0, 1, 0, 0, 0,
                0, 0, 0, 1, 0, 0, 0,
                0, 0, 0, 0, 1, 0, 0,
                1, 1, 0, 0, 0, 0, 1,
                0, 0, 1, 0, 0, 1, 1,
                0, 0, 0, 0, 1, 0, 0,
                0, 0, 0, 1, 1, 0, 0), 
              nrow = 7)
rownames(c) <- c("I, J, K, L", "N, O, P, Q, R", "T, E, F, G, H", "B, C", "A, S", "U, V", "D")
colnames(c) <- c("I, J, K, L", "N, O, P, Q, R", "T, E, F, G, H", "B, C", "A, S", "U, V", "D")
c

	I, J, K, L	N, O, P, Q, R	T, E, F, G, H	B, C	A, S	U, V	D
I, J, K, L	0	0	0	1	0	0	0
N, O, P, Q, R	0	0	0	1	0	0	0
T, E, F, G, H	0	0	0	0	1	0	0
B, C	1	1	0	0	0	0	1
A, S	0	0	1	0	0	1	1
U, V	0	0	0	0	1	0	0
D	0	0	0	1	1	0	0

Table 5: Image matrix corresponding to the blockmodel of an undirected graph.

So the big blocked adjacency matrix in Table 1 (c) can be reduced to the image matrix shown Table 5, summarizing the relations between the blocks in the graph. This matrix, can then even be represented as a graph, so that we can see the pattern of relations between blocks! This is shown in Figure 4

    gr <- graph_from_adjacency_matrix(c) %>% 
      as_tbl_graph() %>% 
      activate(nodes) %>% 
      mutate(names =  c("I, J, K, L", "N, O, P, Q, R", "T, E, F, G, H", "B, C", "A, S", "U, V", "D"))
    p <- ggraph(gr, layout = 'tree') + 
         geom_edge_link(color = "black", width = 1.15)  + 
         geom_node_label(aes(label = names), size = c(5, 5, 5, 7, 7, 5, 10))
    p <- p + theme_graph()
    p

Figure 4: Graph representation of reduced image matrix from a blockmodel.

This is how blockmodeling works!

Note that the final plot is done using tidygraph. You can try yourself to plot it with ggraph instead.

Footnotes

This worksheet is inspired and adapted from this source ↩︎