Community Detection in Two-Mode Networks Using CA

You may have noticed that the CA analysis of two-mode networks looks a lot like the identification of communities in one-mode networks. The main difference is that in a two-mode network, good communities are composed of clusters of persons and groups well-separated from other clusters of persons and groups.

As Barber (2007) noted, we can extend Newman’s modularity approach to ascertain whether a given partition identifies a good “community” in the bipartite case. For that, we need a bi-adjacency analog of the modularity matrix \(\mathbf{B}\). This is given by:

\[ \mathbf{B}_{(ij)} = \mathbf{A}_{(ij)} - \frac{k^p_ik^g_j}{|E|} \]

Where \(k^p_i\) is the number of memberships of the \(i^{th}\) person, \(k^g_i\) is the number of members of the \(j^{th}\) group, and \(|E|\) is the number of edges in the bipartite graph.

So in the Southern Women data case, this would be:

    library(networkdata)
    library(igraph)
    g <- southern_women
    A <- as_biadjacency_matrix(g)
    dp <- as.matrix(rowSums(A))
    dg <- as.matrix(colSums(A))
    dpdg <- dp %*% t(dg) #person x group degree product matrix
    B <- A - dpdg/sum(A)
    round(B, 2)

           6/27   3/2  4/12  9/26  2/25  5/19  3/15  9/16   4/8  6/10  2/23
EVELYN     0.73  0.73  0.46  0.64  0.28  0.28 -0.90 -0.26 -0.08 -0.45 -0.36
LAURA      0.76  0.76  0.53 -0.31  0.37  0.37  0.21 -0.10 -0.94 -0.39 -0.31
THERESA   -0.27  0.73  0.46  0.64  0.28  0.28  0.10 -0.26 -0.08 -0.45 -0.36
BRENDA     0.76 -0.24  0.53  0.69  0.37  0.37  0.21 -0.10 -0.94 -0.39 -0.31
CHARLOTTE -0.13 -0.13  0.73  0.82  0.64 -0.36  0.55 -0.63 -0.54 -0.22 -0.18
FRANCES   -0.13 -0.13  0.73 -0.18  0.64  0.64 -0.45  0.37 -0.54 -0.22 -0.18
ELEANOR   -0.13 -0.13 -0.27 -0.18  0.64  0.64  0.55  0.37 -0.54 -0.22 -0.18
PEARL     -0.10 -0.10 -0.20 -0.13 -0.27  0.73 -0.34  0.53  0.60 -0.17 -0.13
RUTH      -0.13 -0.13 -0.27 -0.18  0.64 -0.36  0.55  0.37  0.46 -0.22 -0.18
VERNE     -0.13 -0.13 -0.27 -0.18 -0.36 -0.36  0.55  0.37  0.46 -0.22 -0.18
MYRNA     -0.13 -0.13 -0.27 -0.18 -0.36 -0.36 -0.45  0.37  0.46  0.78 -0.18
KATHERINE -0.20 -0.20 -0.40 -0.27 -0.54 -0.54 -0.67  0.06  0.19  0.66 -0.27
SYLVIA    -0.24 -0.24 -0.47 -0.31 -0.63 -0.63  0.21 -0.10  0.06  0.61 -0.31
NORA      -0.27 -0.27 -0.54 -0.36 -0.72  0.28  0.10 -1.26 -0.08  0.55  0.64
HELEN     -0.17 -0.17 -0.34 -0.22 -0.45 -0.45  0.44  0.21 -0.67  0.72  0.78
DOROTHY   -0.07 -0.07 -0.13 -0.09 -0.18 -0.18 -0.22  0.69  0.73 -0.11 -0.09
OLIVIA    -0.07 -0.07 -0.13 -0.09 -0.18 -0.18 -0.22 -0.31  0.73 -0.11  0.91
FLORA     -0.07 -0.07 -0.13 -0.09 -0.18 -0.18 -0.22 -0.31  0.73 -0.11  0.91
            4/7 11/21   8/3
EVELYN    -0.54 -0.27 -0.27
LAURA     -0.47 -0.24 -0.24
THERESA   -0.54 -0.27 -0.27
BRENDA    -0.47 -0.24 -0.24
CHARLOTTE -0.27 -0.13 -0.13
FRANCES   -0.27 -0.13 -0.13
ELEANOR   -0.27 -0.13 -0.13
PEARL     -0.20 -0.10 -0.10
RUTH      -0.27 -0.13 -0.13
VERNE      0.73 -0.13 -0.13
MYRNA      0.73 -0.13 -0.13
KATHERINE  0.60  0.80  0.80
SYLVIA     0.53  0.76  0.76
NORA       0.46  0.73  0.73
HELEN      0.66 -0.17 -0.17
DOROTHY   -0.13 -0.07 -0.07
OLIVIA    -0.13 -0.07 -0.07
FLORA     -0.13 -0.07 -0.07

Neat! Like before the numbers in this matrix represent the expected probability of observing a tie in a world in which people keep their number of memberships and groups keep their observed sizes, but otherwise, people and groups connect at random.

We can also create a bipartite matrix version of the bi-adjacency modularity, as follows:

   n <- vcount(g)
   Np <- nrow(A)
   names <- c(rownames(A), colnames(A))
   B2 <- matrix(0, n, n) #all zeros matrix of dimensions (p + g) X (p + g)
   B2[1:Np, (Np + 1):n] <- B #putting B in the top right block
   B2[(Np + 1):n, 1:Np] <- t(B) #putting B transpose in the lower-left block
   rownames(B2) <- names
   colnames(B2) <- names
   round(B2, 2)

          EVELYN LAURA THERESA BRENDA CHARLOTTE FRANCES ELEANOR PEARL  RUTH
EVELYN      0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
LAURA       0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
THERESA     0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
BRENDA      0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
CHARLOTTE   0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
FRANCES     0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
ELEANOR     0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
PEARL       0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
RUTH        0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
VERNE       0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
MYRNA       0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
KATHERINE   0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
SYLVIA      0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
NORA        0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
HELEN       0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
DOROTHY     0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
OLIVIA      0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
FLORA       0.00  0.00    0.00   0.00      0.00    0.00    0.00  0.00  0.00
6/27        0.73  0.76   -0.27   0.76     -0.13   -0.13   -0.13 -0.10 -0.13
3/2         0.73  0.76    0.73  -0.24     -0.13   -0.13   -0.13 -0.10 -0.13
4/12        0.46  0.53    0.46   0.53      0.73    0.73   -0.27 -0.20 -0.27
9/26        0.64 -0.31    0.64   0.69      0.82   -0.18   -0.18 -0.13 -0.18
2/25        0.28  0.37    0.28   0.37      0.64    0.64    0.64 -0.27  0.64
5/19        0.28  0.37    0.28   0.37     -0.36    0.64    0.64  0.73 -0.36
3/15       -0.90  0.21    0.10   0.21      0.55   -0.45    0.55 -0.34  0.55
9/16       -0.26 -0.10   -0.26  -0.10     -0.63    0.37    0.37  0.53  0.37
4/8        -0.08 -0.94   -0.08  -0.94     -0.54   -0.54   -0.54  0.60  0.46
6/10       -0.45 -0.39   -0.45  -0.39     -0.22   -0.22   -0.22 -0.17 -0.22
2/23       -0.36 -0.31   -0.36  -0.31     -0.18   -0.18   -0.18 -0.13 -0.18
4/7        -0.54 -0.47   -0.54  -0.47     -0.27   -0.27   -0.27 -0.20 -0.27
11/21      -0.27 -0.24   -0.27  -0.24     -0.13   -0.13   -0.13 -0.10 -0.13
8/3        -0.27 -0.24   -0.27  -0.24     -0.13   -0.13   -0.13 -0.10 -0.13
          VERNE MYRNA KATHERINE SYLVIA  NORA HELEN DOROTHY OLIVIA FLORA  6/27
EVELYN     0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00  0.73
LAURA      0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00  0.76
THERESA    0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.27
BRENDA     0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00  0.76
CHARLOTTE  0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.13
FRANCES    0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.13
ELEANOR    0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.13
PEARL      0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.10
RUTH       0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.13
VERNE      0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.13
MYRNA      0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.13
KATHERINE  0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.20
SYLVIA     0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.24
NORA       0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.27
HELEN      0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.17
DOROTHY    0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.07
OLIVIA     0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.07
FLORA      0.00  0.00      0.00   0.00  0.00  0.00    0.00   0.00  0.00 -0.07
6/27      -0.13 -0.13     -0.20  -0.24 -0.27 -0.17   -0.07  -0.07 -0.07  0.00
3/2       -0.13 -0.13     -0.20  -0.24 -0.27 -0.17   -0.07  -0.07 -0.07  0.00
4/12      -0.27 -0.27     -0.40  -0.47 -0.54 -0.34   -0.13  -0.13 -0.13  0.00
9/26      -0.18 -0.18     -0.27  -0.31 -0.36 -0.22   -0.09  -0.09 -0.09  0.00
2/25      -0.36 -0.36     -0.54  -0.63 -0.72 -0.45   -0.18  -0.18 -0.18  0.00
5/19      -0.36 -0.36     -0.54  -0.63  0.28 -0.45   -0.18  -0.18 -0.18  0.00
3/15       0.55 -0.45     -0.67   0.21  0.10  0.44   -0.22  -0.22 -0.22  0.00
9/16       0.37  0.37      0.06  -0.10 -1.26  0.21    0.69  -0.31 -0.31  0.00
4/8        0.46  0.46      0.19   0.06 -0.08 -0.67    0.73   0.73  0.73  0.00
6/10      -0.22  0.78      0.66   0.61  0.55  0.72   -0.11  -0.11 -0.11  0.00
2/23      -0.18 -0.18     -0.27  -0.31  0.64  0.78   -0.09   0.91  0.91  0.00
4/7        0.73  0.73      0.60   0.53  0.46  0.66   -0.13  -0.13 -0.13  0.00
11/21     -0.13 -0.13      0.80   0.76  0.73 -0.17   -0.07  -0.07 -0.07  0.00
8/3       -0.13 -0.13      0.80   0.76  0.73 -0.17   -0.07  -0.07 -0.07  0.00
            3/2  4/12  9/26  2/25  5/19  3/15  9/16   4/8  6/10  2/23   4/7
EVELYN     0.73  0.46  0.64  0.28  0.28 -0.90 -0.26 -0.08 -0.45 -0.36 -0.54
LAURA      0.76  0.53 -0.31  0.37  0.37  0.21 -0.10 -0.94 -0.39 -0.31 -0.47
THERESA    0.73  0.46  0.64  0.28  0.28  0.10 -0.26 -0.08 -0.45 -0.36 -0.54
BRENDA    -0.24  0.53  0.69  0.37  0.37  0.21 -0.10 -0.94 -0.39 -0.31 -0.47
CHARLOTTE -0.13  0.73  0.82  0.64 -0.36  0.55 -0.63 -0.54 -0.22 -0.18 -0.27
FRANCES   -0.13  0.73 -0.18  0.64  0.64 -0.45  0.37 -0.54 -0.22 -0.18 -0.27
ELEANOR   -0.13 -0.27 -0.18  0.64  0.64  0.55  0.37 -0.54 -0.22 -0.18 -0.27
PEARL     -0.10 -0.20 -0.13 -0.27  0.73 -0.34  0.53  0.60 -0.17 -0.13 -0.20
RUTH      -0.13 -0.27 -0.18  0.64 -0.36  0.55  0.37  0.46 -0.22 -0.18 -0.27
VERNE     -0.13 -0.27 -0.18 -0.36 -0.36  0.55  0.37  0.46 -0.22 -0.18  0.73
MYRNA     -0.13 -0.27 -0.18 -0.36 -0.36 -0.45  0.37  0.46  0.78 -0.18  0.73
KATHERINE -0.20 -0.40 -0.27 -0.54 -0.54 -0.67  0.06  0.19  0.66 -0.27  0.60
SYLVIA    -0.24 -0.47 -0.31 -0.63 -0.63  0.21 -0.10  0.06  0.61 -0.31  0.53
NORA      -0.27 -0.54 -0.36 -0.72  0.28  0.10 -1.26 -0.08  0.55  0.64  0.46
HELEN     -0.17 -0.34 -0.22 -0.45 -0.45  0.44  0.21 -0.67  0.72  0.78  0.66
DOROTHY   -0.07 -0.13 -0.09 -0.18 -0.18 -0.22  0.69  0.73 -0.11 -0.09 -0.13
OLIVIA    -0.07 -0.13 -0.09 -0.18 -0.18 -0.22 -0.31  0.73 -0.11  0.91 -0.13
FLORA     -0.07 -0.13 -0.09 -0.18 -0.18 -0.22 -0.31  0.73 -0.11  0.91 -0.13
6/27       0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
3/2        0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
4/12       0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
9/26       0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
2/25       0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
5/19       0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
3/15       0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
9/16       0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
4/8        0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
6/10       0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
2/23       0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
4/7        0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
11/21      0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
8/3        0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
          11/21   8/3
EVELYN    -0.27 -0.27
LAURA     -0.24 -0.24
THERESA   -0.27 -0.27
BRENDA    -0.24 -0.24
CHARLOTTE -0.13 -0.13
FRANCES   -0.13 -0.13
ELEANOR   -0.13 -0.13
PEARL     -0.10 -0.10
RUTH      -0.13 -0.13
VERNE     -0.13 -0.13
MYRNA     -0.13 -0.13
KATHERINE  0.80  0.80
SYLVIA     0.76  0.76
NORA       0.73  0.73
HELEN     -0.17 -0.17
DOROTHY   -0.07 -0.07
OLIVIA    -0.07 -0.07
FLORA     -0.07 -0.07
6/27       0.00  0.00
3/2        0.00  0.00
4/12       0.00  0.00
9/26       0.00  0.00
2/25       0.00  0.00
5/19       0.00  0.00
3/15       0.00  0.00
9/16       0.00  0.00
4/8        0.00  0.00
6/10       0.00  0.00
2/23       0.00  0.00
4/7        0.00  0.00
11/21      0.00  0.00
8/3        0.00  0.00

Which is a bipartite version of modularity matrix (\(\mathbf{\hat{B}}\)) with the same block structure as the bipartite adjacency matrix:

\[ \mathbf{\hat{B}} = \left[ \begin{matrix} \mathbf{O}_{M \times M} & \mathbf{B}_{M \times N} \\ \mathbf{B}^T_{N \times M} & \mathbf{O}_{N \times N} \end{matrix} \right] \]

Note that in \(\mathbf{\hat{B}}\) the modularity (expected number of edges) is set to zero for nodes of the same set (people and people; groups and groups), and to non-zero values for nodes of different sets (persons and groups).

Now, we can use the same approach we used in the unipartite case to check the modularity of some hypothetical partition of the nodes in the graph.

Take for instance, the CA scores in the first dimension that we saw in the lecture on CA. They do seem to divide the persons and groups into distinct communities.

So let’s bring them back (using the CA function in the package FactoMineRand transform them into membership vectors (using dummy coding):

    library(FactoMineR)
    ca.res <- CA(A, graph = FALSE)
    eig.vec.p <- ca.res$row$coord[, 1] #CA scores for persons in first dim.
    eig.vec.g <- ca.res$col$coord[, 1] #CA scores for groups in first dim
    u1 <- rep(0, n)
    u2 <- rep(0, n)
    d <- c(eig.vec.p, eig.vec.g) #original CA scores
    d <- Re(d)
    u1[which(d > 0)] <- 1
    u2[which(d <= 0)] <- 1
    U <- cbind(u1, u2)
    rownames(U) <- rownames(B2)
    U

          u1 u2
EVELYN     0  1
LAURA      0  1
THERESA    0  1
BRENDA     0  1
CHARLOTTE  0  1
FRANCES    0  1
ELEANOR    0  1
PEARL      0  1
RUTH       0  1
VERNE      1  0
MYRNA      1  0
KATHERINE  1  0
SYLVIA     1  0
NORA       1  0
HELEN      1  0
DOROTHY    1  0
OLIVIA     1  0
FLORA      1  0
6/27       0  1
3/2        0  1
4/12       0  1
9/26       0  1
2/25       0  1
5/19       0  1
3/15       0  1
9/16       0  1
4/8        1  0
6/10       1  0
2/23       1  0
4/7        1  0
11/21      1  0
8/3        1  0

Recall that we can check the modularity of a partition coded in a dummy matrix like U using the formula:

\[ \frac{tr(U^TBU)}{\sum_i\sum_ja_{ij}} \]

Where \(tr\) is the trace matrix operation (sum of the diagonals).

Let’s check it out:

   A2 <- as.matrix(as_adjacency_matrix(g))
   round(sum(diag(t(U) %*% B2 %*% U))/sum(A2), 3)

[1] 0.318

Which looks pretty good!

Here’s a plot of the bipartite graph with nodes colored by the CA induced community bipartition:

Southern Women’s bipartite graph by the best two-community partition according to CA.

References

Barber, Michael J. 2007. “Modularity and Community Detection in Bipartite Networks.” Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 76 (6): 066102.