Skip to main content

1 What are communities?

What are communities? In networks, communities are subsets of nodes that have more interactions or connectivity within themselves than outside of themselves (these are sometimes called “modules” outside sociology). Communities thus exemplify the sociological concept of a group.

A network has community structure if it contains many such subsets or groups of nodes that interact preferentially with one another. Not all networks have to have community structure; a network in which all nodes interact with equal propensity doesn’t have communities.

So whether a network has community structure, and whether a given guess about what these communities are yields actual communities (a cluster of nodes that interact more among themselves than with outsiders) is an empirical question that needs to be answered with data.

But first, we need to develop a criterion for determining whether a given partition of the network into mutually exclusive node subsets actually produces communities as we defined them earlier. This criterion should be independent of particular methods and algorithms that claim to find communities, so that we can compare them with one another and see whether the partitions they recommend yield actual communities.

Mark Newman (2006b), who has done the most influential work in this area, proposed such a criterion and called it the modularity of a partition (e.g., the extent to which a partition has identified the “modules” or subsets of the network).

3 Modularity from the Adjacency Matrix

Note that while the “bag of links” idea is useful for illustrating the basic probabilistic principle behind modularity in a network, we can compute it directly from the adjacency matrix without going through the edge-list data-frame construction step.

A function that does this looks like:

Code
mod.Q2 <- function(x, c) {
  A <- as.matrix(as_adjacency_matrix(x))
  vol <- sum(A)
  Q <- 0
  for (k in unique(c)) {
    A.sub <- A[which(c == k), which(c == k)]
    vol.k <- sum(A.sub)
    A.i <- A[which(c == k), ]
    A.j <- A[, which(c == k)]
    Q <- Q + ((vol.k / vol) - ((sum(A.i) * sum(A.j)) / vol^2))
  }
  return(Q)
}

This function takes a graph and a vector indicating each node’s community membership, and returns the modularity. As with the bag of links, the modularity is the observed probability of a within-community link minus the probability we would expect if communities played no role. It works like this:

  • Line 2 turns the graph into a plain adjacency matrix, which we need because the code below selects rows and columns by position. Line 3 counts every entry in that matrix, giving the total number of links in the network, and line 4 sets the running total to zero.

  • Line 5 loops over each distinct community in c, so that each one’s contribution can be computed and added on.

  • Lines 6-7 pull out the within-community block: the rows and columns belonging to community \(k\), and then the sum of every link inside it. Dividing that sum by the total from line 3 gives the share of all links that stay inside community \(k\).

  • Lines 8-9 take a different kind of slice. Here only one dimension is restricted to community \(k\): line 8 keeps all rows for nodes in \(k\) (every link leaving the community), and line 9 keeps all columns for nodes in \(k\) (every link entering it). These are slices of the full matrix, not of the within-community block, which is why they count above and beyond the internal links.

  • Line 10 combines these into community \(k\)’s contribution. The first term is the observed share from line 7; the second multiplies the two marginal counts and divides by the square of the total, which turns two counts-over-the-whole-matrix into two probabilities and then into their product—the link rate we would expect if a source’s community and a destination’s community had nothing to do with each other.

  • Line 12 returns the accumulated total once every community has been visited, which is the modularity of that partition.

In symbols:

\[ Q = \sum_{k=1}^m \left[\frac{\sum_{i \in k} \sum_{j \in k} a_{ij}}{\sum_i \sum_j a_{ij}} - \frac{(\sum_{i \in k} \sum_j a_{ij})(\sum_i \sum_{j \in k} a_{ij})}{(\sum_i \sum_j a_{ij})^2} \right] \tag{1}\]

Where \(\sum_i \sum_ja_{ij}\) is the sum of all the entries in the network adjacency matrix, \(\sum_{i \in k} \sum_{j \in k} a_{ij}\) is the sum of all the entries of the sub-adjacency matrix where both the row and column nodes come from community \(k\), \(\sum_{i \in k} \sum_j a_{ij}\) is the sum of all the entries in the sub-adjacency matrix where only the row nodes come from community \(k\), and \(\sum_i \sum_{j \in k} a_{ij}\) is the sum of all the entries in the sub-adjacency matrix where only the column nodes come from community \(k\).

We can easily see that this approach gives us the same answer as the bag of links version:

Code
mod.Q2(g, V(g)$status)
[1] 0.2715221
Code
mod.Q2(g, V(g)$gender)
[1] 0.07495538

Of course, you don’t even have to use a custom function like the above, because igraph has one, called (you guessed it) modularity:

Code
modularity(g, V(g)$status)
[1] 0.2715221
Code
modularity(g, V(g)$gender)
[1] 0.07495538

But at least now you know what’s going on inside of it!

4 The Modularity Matrix

Obviously, modularity wouldn’t be widely used if it were merely a way to measure the quality of a community partition produced by other methods. It can be used to find community partitions by a method that produces a node partition capturing the largest values it can take in a graph.

A useful tool in this quest is the modularity matrix \(\mathbf{B}\) (Newman 2006b), which is defined as a variation on the adjacency matrix \(\mathbf{A}\), where each cell of the modularity matrix \(b_{ij}\) takes the value:

\[ b_{ij} = a_{ij} - \frac{k^{out}_ik^{in}_j}{\sum_i\sum_j a_{ij}} \]

Where \(k^{out}_i\) is node \(i\)’s outdegree and \(k^{in}_j\) is node j’s indegree. Note that the modularity matrix has the same “observed minus expected” structure as the formulas for the modularity. In this case, we compare whether we see a link from \(i\) to \(j\) as given by \(a_{ij}\) against the chances of observing a link in a graph in which nodes connect at random with probability proportional to their degrees (as given by the right-hand side fraction).

Note that if the graph is undirected, the modularity matrix is just:

\[ b_{ij} = a_{ij} - \frac{k_ik_j}{\sum_i\sum_j a_{ij}} \]

A function to compute the modularity matrix by looping through every element of the adjacency matrix for a directed graph looks like:

Code
mod.mat <- function(x) {
  A <- as.matrix(as_adjacency_matrix(x)) # adjacency matrix
  od <- rowSums(A) # outdegrees
  id <- colSums(A) # indegrees
  vol <- sum(A) # number of links
  n <- nrow(A) # number of nodes
  B <- matrix(0, n, n)
  for (i in 1:n) {
    for (j in 1:n) {
      B[i, j] <- A[i, j] - ((od[i] * id[j]) / vol)
    }
  }
  return(B)
}

It works like this:

  • Line 2 converts the graph to a plain adjacency matrix so that individual entries can be picked out by position, and lines 3-4 record how many links leave each node (row sums) and how many arrive at each node (column sums). Keeping these separate matters because in a directed graph a node’s outdegree and indegree rarely match.

  • Line 5 counts every entry in the matrix, giving the total number of links, which is the baseline the expectations are measured against. Line 6 records the number of nodes, and line 7 sets up an empty matrix of the right size to be filled one cell at a time.

  • Lines 8-10 walk over every cell of that matrix, one row and one column at a time. For each cell, line 10 compares the observed entry with what random pairing would produce: the chance that a link starts at node \(i\) multiplied by the chance that it ends at node \(j\), scaled by the total number of links. A positive result means the tie is more frequent than chance, a negative one means it is rarer.

  • Line 13 returns the filled matrix. Because every cell is built as an observed minus expected quantity with the expected part fixed by the node’s degrees, the rows and columns of the result each add up to zero.

Peeking inside the resulting matrix:

Code
round(mod.mat(g)[1:10, 1:10], 3)
        [,1]   [,2]   [,3]   [,4]   [,5]   [,6]   [,7]   [,8]   [,9]  [,10]
 [1,] -0.035  0.930 -0.028  0.902 -0.035 -0.014 -0.014  0.951 -0.098 -0.028
 [2,] -0.035 -0.070 -0.028 -0.098 -0.035 -0.014 -0.014 -0.049 -0.098 -0.028
 [3,]  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000
 [4,] -0.131  0.739  0.895 -0.366 -0.131 -0.052 -0.052 -0.183  0.634 -0.105
 [5,] -0.026 -0.052 -0.021 -0.073 -0.026 -0.010  0.990 -0.037 -0.073 -0.021
 [6,]  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000
 [7,] -0.017 -0.035  0.986 -0.049  0.983 -0.007 -0.007 -0.024 -0.049 -0.014
 [8,] -0.009 -0.017 -0.007 -0.024 -0.009 -0.003 -0.003 -0.012 -0.024 -0.007
 [9,] -0.052 -0.105 -0.042  0.854 -0.052 -0.021 -0.021 -0.073 -0.146 -0.042
[10,] -0.122  0.756 -0.098 -0.341 -0.122 -0.049 -0.049  0.829  0.659 -0.098

Interestingly, the matrix has some negative entries, some positive entries, and some close to or actually zero. We interpret these as follows: If an entry is negative, it means that a link between the row and column nodes is much less likely to happen than expected given each node’s degrees, a positive entry indicates the opposite; a larger than expected chance of a link forming. Entries close to zero indicate those nodes have odds close to a random chance of forming a tie.

Of course, igraph has a function, called modularity_matrix, which gives us the same result:

Code
B <- modularity_matrix(g)
round(B[1:10, 1:10], 3)
        [,1]   [,2]   [,3]   [,4]   [,5]   [,6]   [,7]   [,8]   [,9]  [,10]
 [1,] -0.035  0.930 -0.028  0.902 -0.035 -0.014 -0.014  0.951 -0.098 -0.028
 [2,] -0.035 -0.070 -0.028 -0.098 -0.035 -0.014 -0.014 -0.049 -0.098 -0.028
 [3,]  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000
 [4,] -0.131  0.739  0.895 -0.366 -0.131 -0.052 -0.052 -0.183  0.634 -0.105
 [5,] -0.026 -0.052 -0.021 -0.073 -0.026 -0.010  0.990 -0.037 -0.073 -0.021
 [6,]  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000
 [7,] -0.017 -0.035  0.986 -0.049  0.983 -0.007 -0.007 -0.024 -0.049 -0.014
 [8,] -0.009 -0.017 -0.007 -0.024 -0.009 -0.003 -0.003 -0.012 -0.024 -0.007
 [9,] -0.052 -0.105 -0.042  0.854 -0.052 -0.021 -0.021 -0.073 -0.146 -0.042
[10,] -0.122  0.756 -0.098 -0.341 -0.122 -0.049 -0.049  0.829  0.659 -0.098

In the case of an undirected graph, computing the modularity is even simpler:

Code
mod.mat.u <- function(x) {
  A <- as.matrix(as_adjacency_matrix(x))
  d <- rowSums(A) # degrees
  vol <- sum(A)
  n <- nrow(A)
  B <- A - (d %*% t(d) / vol)
  return(B)
}

Let’s see the function in action:

Code
ug <- as_undirected(g, mode = "collapse")
Bu <- mod.mat.u(ug)
round(Bu[1:10, 1:10], 2)
       [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]  [,9] [,10]
 [1,] -0.08  0.90 -0.04  0.78 -0.06 -0.02 -0.03  0.93 -0.14 -0.14
 [2,]  0.90 -0.13 -0.05  0.72 -0.08 -0.03 -0.04 -0.09 -0.18  0.82
 [3,] -0.04 -0.05 -0.02  0.89 -0.03 -0.01  0.98 -0.04 -0.07 -0.07
 [4,]  0.78  0.72  0.89 -0.61 -0.17 -0.06 -0.08 -0.19  0.61 -0.39
 [5,] -0.06 -0.08 -0.03 -0.17 -0.05 -0.02  0.98 -0.05 -0.11 -0.11
 [6,] -0.02 -0.03 -0.01 -0.06 -0.02 -0.01 -0.01 -0.02 -0.04 -0.04
 [7,] -0.03 -0.04  0.98 -0.08  0.98 -0.01 -0.01 -0.03 -0.05 -0.05
 [8,]  0.93 -0.09 -0.04 -0.19 -0.05 -0.02 -0.03 -0.06 -0.12  0.88
 [9,] -0.14 -0.18 -0.07  0.61 -0.11 -0.04 -0.05 -0.12 -0.25  0.75
[10,] -0.14  0.82 -0.07 -0.39 -0.11 -0.04 -0.05  0.88  0.75 -0.25

Which gives us the same results as using igraph:

Code
Bu <- modularity_matrix(ug, directed = FALSE)
round(Bu[1:10, 1:10], 2)
       [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]  [,9] [,10]
 [1,] -0.08  0.90 -0.04  0.78 -0.06 -0.02 -0.03  0.93 -0.14 -0.14
 [2,]  0.90 -0.13 -0.05  0.72 -0.08 -0.03 -0.04 -0.09 -0.18  0.82
 [3,] -0.04 -0.05 -0.02  0.89 -0.03 -0.01  0.98 -0.04 -0.07 -0.07
 [4,]  0.78  0.72  0.89 -0.61 -0.17 -0.06 -0.08 -0.19  0.61 -0.39
 [5,] -0.06 -0.08 -0.03 -0.17 -0.05 -0.02  0.98 -0.05 -0.11 -0.11
 [6,] -0.02 -0.03 -0.01 -0.06 -0.02 -0.01 -0.01 -0.02 -0.04 -0.04
 [7,] -0.03 -0.04  0.98 -0.08  0.98 -0.01 -0.01 -0.03 -0.05 -0.05
 [8,]  0.93 -0.09 -0.04 -0.19 -0.05 -0.02 -0.03 -0.06 -0.12  0.88
 [9,] -0.14 -0.18 -0.07  0.61 -0.11 -0.04 -0.05 -0.12 -0.25  0.75
[10,] -0.14  0.82 -0.07 -0.39 -0.11 -0.04 -0.05  0.88  0.75 -0.25

The modularity matrix has some interesting properties. For instance, both its rows and columns sum to zero:

Code
round(rowSums(Bu), 2)
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
[39] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Code
round(colSums(Bu), 2)
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
[39] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Which makes \(\mathbf{B}\) doubly centered a neat but so far useless property.

5 Using the Modularity Matrix to Find the Modularity of a Partition

A more interesting property of the modularity matrix is that we can use it to compute the actual modularity of a given binary partition of the network into clusters. Let’s take status in the law_friends network as an example.

First, we create a new vector \(\mathbf{s}\) that equals one when node \(i\) is in the first group (partners) and minus one when node \(i\) is in the second group (associates):

Code
s.contrast <- V(g)$status
s.contrast[which(s.contrast == 1)] <- 1
s.contrast[which(s.contrast == 2)] <- -1
s.contrast
 [1]  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
[26]  1  1  1  1  1  1  1  1  1  1  1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
[51] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Once we have this vector, the modularity is just:

\[ Q = \frac{\mathbf{s}^T\mathbf{B}\mathbf{s}}{2\sum_i\sum_ja_{ij}} \]

Which we can readily check in R:

Code
A <- as.matrix(as_adjacency_matrix(g))
as.numeric(t(s.contrast) %*% B %*% s.contrast) / (2 * sum(A))
[1] 0.2715221

You can think of the \(\mathbf{s}\) vector as identifying the binary community membership via contrast coding.

We can also use the modularity matrix to find the modularity of a partition via dummy coding. To do this, we create two vectors for each level of the group membership variable with \(u^{(1)}_i = 1\) when node \(i\) is a partner (otherwise \(u^{(1)}_i = 0\)), and \(u^{(2)}_i = 1\) when node \(i\) is an associate (otherwise \(u^{(2)}_i = 0\)).

In R, we can do this as follows:

Code
u1 <- rep(0, length(V(g)$status))
u2 <- rep(0, length(V(g)$status))
u1[which(V(g)$status == 1)] <- 1
u2[which(V(g)$status == 2)] <- 1

We then join the two vectors into a matrix \(\mathbf{U}\) of dimensions \(n \times 2\):

Code
U <- cbind(u1, u2)
head(U)
     u1 u2
[1,]  1  0
[2,]  1  0
[3,]  1  0
[4,]  1  0
[5,]  1  0
[6,]  1  0
Code
tail(U)
      u1 u2
[63,]  0  1
[64,]  0  1
[65,]  0  1
[66,]  0  1
[67,]  0  1
[68,]  0  1

Once we have this matrix, the modularity of the partition is given by:

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

Where \(tr\) denotes the trace operation in a matrix, namely, taking the sum of its diagonal elements.

We can check that this gives us the correct solution in R as follows:

Code
sum(diag(t(U) %*% B %*% U)) / sum(A)
[1] 0.2715221

Neat! It makes sense (given the name of the matrix) that we can compute the modularity from \(\mathbf{B}\), and we can do it in multiple ways.

6 Using the Modularity Matrix to Find Communities

Here’s an even more useful property of the modularity matrix. Remember the network distribution game we played to define our various reflective status measures in our discussion of prestige?

Code
status1 <- function(w) {
  x <- rep(1, nrow(w)) # initial status vector set to all ones of length equal to the number of nodes
  d <- 1 # initial delta
  k <- 0 # initializing counter
  while (d > 1e-10) {
    o.x <- x # old status scores
    x <- w %*% o.x # new scores are a function of old scores and adjacency matrix
    x <- x / norm(x, type = "E") # normalizing new status scores
    d <- abs(sum(abs(x) - abs(o.x))) # delta between new and old scores
    k <- k + 1 # incrementing while counter
  }
  return(as.vector(x))
}

What if we played it with the modularity matrix?

Code
s.eig <- status1(Bu)
round(s.eig, 2)
 [1] -0.10 -0.14 -0.02 -0.21 -0.03  0.00  0.01 -0.05 -0.21 -0.18 -0.16 -0.24
[13] -0.13 -0.06 -0.04 -0.12 -0.24  0.08 -0.03 -0.17 -0.18 -0.15 -0.09 -0.14
[25] -0.11 -0.17 -0.19  0.04 -0.10 -0.02  0.11  0.06  0.06 -0.06  0.10  0.01
[37] -0.05  0.04 -0.05  0.12  0.19 -0.02  0.07  0.05  0.02  0.08  0.08  0.09
[49]  0.17  0.00  0.20  0.06  0.20  0.13  0.20  0.09  0.08  0.05  0.06  0.02
[61]  0.24  0.14  0.17  0.06  0.13  0.09  0.09  0.09

This seems more interesting. The resulting “status” vector has both negative and positive entries. What if I told you that this vector is actually a partition of the original graph into two communities?

Not only that, I have even better news. This is the partition that maximizes the modularity in the graph, the best two-group partition that has the most edges within groups and the least edges going across groups.1

Let’s see some evidence for these claims in real data.

First, let’s turn the “status” vector into a community indicator vector. We assign all nodes with scores larger than zero to one community and nodes with scores equal to zero or less to the other one:

Code
C <- rep(0, length(s.eig))
C[which(s.eig <= 0)] <- 1
C[which(s.eig > 0)] <- 2
names(C) <- 1:length(C)
C
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
 1  1  1  1  1  2  2  1  1  1  1  1  1  1  1  1  1  2  1  1  1  1  1  1  1  1 
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 
 1  2  1  1  2  2  2  1  2  2  1  2  1  2  2  1  2  2  2  2  2  2  2  2  2  2 
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 
 2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2 

And for the big check:

Code
modularity(ug, C)
[1] 0.2935153

This is a pretty big score, at least larger than we obtained earlier using the exogenous indicator of status in the law firm as the basis for a binary partition. Figure 2 shows visual evidence that this is indeed an optimal binary partition of the law_friends network.

Of course, you may also remember from the Status and Prestige lesson that the little status game we played above is also a method (called the “power” method) of computing the leading eigenvector (the one associated with the largest eigenvalue) of a matrix. So turns out that the modularity maximizing bi-partition of a graph is just given by this vector:

\[ \mathbf{B}\mathbf{v} = \lambda\mathbf{v} \tag{2}\]

Solving for \(\mathbf{v}\) in Equation 2 yields the nodes’ community memberships. In R, you can do this using the native eigen function as we did for the status scores:

Code
v <- eigen(Bu)$vectors[, 1]
round(v, 2)
 [1] -0.10 -0.14 -0.02 -0.21 -0.03  0.00  0.01 -0.05 -0.21 -0.18 -0.16 -0.24
[13] -0.13 -0.06 -0.04 -0.12 -0.24  0.08 -0.03 -0.17 -0.18 -0.15 -0.09 -0.14
[25] -0.11 -0.17 -0.19  0.04 -0.10 -0.02  0.11  0.06  0.06 -0.06  0.10  0.01
[37] -0.05  0.04 -0.05  0.12  0.19 -0.02  0.07  0.05  0.02  0.08  0.08  0.09
[49]  0.17  0.00  0.20  0.06  0.20  0.13  0.20  0.09  0.08  0.05  0.06  0.02
[61]  0.24  0.14  0.17  0.06  0.13  0.09  0.09  0.09

Which look like the same values we obtained earlier.

We can package all of the steps above into a simple function:

Code
split.two <- function(x) {
  e <- eigen(x)$vectors[, 1]
  v <- rep(0, length(e))
  v[e <= 0] <- 1
  v[e > 0] <- 2
  names(v) <- 1:length(v)
  c1 <- rep(0, length(v))
  c2 <- rep(0, length(v))
  c1[which(v == 1)] <- 1
  c2[which(v == 2)] <- 1
  dummy <- cbind(c1, c2)
  return(list(v = v, dummy = dummy))
}

It works like this:

  • Line 1 defines a function whose input, despite the graph-flavored examples around it, is a matrix—in practice the modularity matrix. Line 2 pulls out its leading eigenvector, the vector tied to the largest eigenvalue, whose entries serve as each node’s score.

  • Lines 3-5 turn those scores into a two-group label. A vector of zeros is created to hold the labels, then nodes with a non-positive score are given the label 1 and nodes with a positive score the label 2. Note that the sign of an eigenvector is arbitrary, so the computer may return the mirror image of the same vector and swap which group gets which label; the partition itself is unaffected.

  • Line 6 names the labels after node positions, so the result lines up with the vertex order of the graph rather than with an arbitrary order.

  • Lines 7-10 build the same partition in dummy form: two columns of zeros and ones, one for each group, marking which nodes belong to it. This second version is needed because the trace-based formula for modularity takes an indicator matrix rather than a single label vector.

  • Line 12 returns both versions in a named list, since the divisive routine below uses the scalar labels to describe the split and the indicator matrix to evaluate its modularity.

And check to see if it works:

Code
split.two(Bu)$v
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
 1  1  1  1  1  2  2  1  1  1  1  1  1  1  1  1  1  2  1  1  1  1  1  1  1  1 
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 
 1  2  1  1  2  2  2  1  2  2  1  2  1  2  2  1  2  2  2  2  2  2  2  2  2  2 
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 
 2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2 

Indeed, it splits the nodes in a graph into two modularity-maximizing communities.

It is clear that this approach hints at a divisive partitioning strategy, where we begin with two communities and then try to split one (or both) of those communities into two more, as with CONCOR.

However, unlike CONCOR, we don’t want to be unprincipled here because splitting a well-defined community into two just for the hell of it can actually lead to worse modularity than keeping the original larger communities.

So we need an approach that tries out splitting one of the original two communities into two smaller ones, checks the new modularity, compares it with the old, and only proceeds with the partition if the new modularity is greater than the old.

Here’s one way of doing that:

Code
split.mult <- function(B, vol, u, v, s = 0.01) {
  split <- list()
  delta.Q <- rep(0, max(v))
  for (i in 1:max(v)) {
    old.Q <- t(u[, i]) %*% B %*% u[, i] # Using dummy coding to compute Q
    sub <- which(u[, i] == 1)
    new.B <- B[sub, sub]
    new.u <- split.two(new.B)$dummy
    new.v <- split.two(new.B)$v
    Q1 <- t(new.u[, 1]) %*% new.B %*% new.u[, 1] # Using dummy coding to compute Q
    Q2 <- t(new.u[, 2]) %*% new.B %*% new.u[, 2] # Using dummy coding to compute Q
    new.Q <- Q1 + Q2
    delta.Q[i] <- (new.Q - old.Q) * (1 / vol)
    if (delta.Q[i] > s) {
      split[[i]] <- new.v
      names(split[[i]]) <- which(u[, i] == 1)
    } else if (delta.Q[i] <= s) {
      split[[i]] <- NULL
    }
  }
  return(list(delta.Q = round(delta.Q, 3), v = v, split = split))
}

This function uses the output of the split.two function to check whether either of the current communities should be split into two further sub-communities, by comparing the modularity before and after the proposed split. It works like this:

  • Line 1 takes the modularity matrix B, the total number of links vol (needed to put the matrix-based score back on the modularity scale), the dummy indicator matrix u for the current communities, the current labels v, and a minimum improvement s, which defaults to 0.01.

  • Lines 2-4 set up the machinery: an empty list to hold any splits that get accepted, one slot per community, a vector of zeros to record each community’s change in modularity, and a loop that visits each community in turn.

  • Line 5 computes the current modularity for community i. This uses the same trace formula as before, applied to that community’s indicator column, but without dividing by the total number of links. That division is deferred to line 13, where it is applied once to the difference instead.

  • Lines 6-7 restrict attention to the part of the matrix that the split could possibly change. Line 6 finds the nodes belonging to community i, and line 7 takes the square block made of just those rows and columns; links to nodes outside the community are untouched by subdividing it, so they can be ignored.

  • Lines 8-12 run the eigenvector split on that block and score the result. The block is split into two candidate sub-communities, and the two halves’ modularities are computed and added together, giving the modularity the partition would have if this split were adopted.

  • Lines 13-19 compare the new modularity with the old one, scaled by the total number of links. If the gain exceeds the threshold s, the split is kept and its labels are re-attached to the original node numbers so they line up with the graph; otherwise nothing is stored for that community, so it is left alone (assigning NULL to a list element in R removes it rather than adding a blank slot). Line 21 returns the per-community changes, the unchanged labels, and the list of accepted splits.

Here are the results applied to the law_friends network:

Code
splits1 <- split.mult(
  B = Bu,
  vol = sum(as.matrix(as_adjacency_matrix(ug))),
  u = split.two(Bu)$dummy,
  v = split.two(Bu)$v
)
splits1
$delta.Q
[1] 0.000 0.048

$v
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
 1  1  1  1  1  2  2  1  1  1  1  1  1  1  1  1  1  2  1  1  1  1  1  1  1  1 
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 
 1  2  1  1  2  2  2  1  2  2  1  2  1  2  2  1  2  2  2  2  2  2  2  2  2  2 
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 
 2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2 

$split
$split[[1]]
NULL

$split[[2]]
 6  7 18 28 31 32 33 35 36 38 40 41 43 44 45 46 47 48 49 50 51 52 53 54 55 56 
 2  2  2  2  2  2  2  2  2  1  1  1  1  1  1  1  2  2  1  1  1  1  1  1  2  2 
57 58 59 60 61 62 63 64 65 66 67 68 
 2  1  1  2  1  1  1  1  1  1  1  1 

The delta.Q vector stores the results of our modularity checks. In this case, the test in the first community failed; the modularity didn’t change (the difference between the old and the new is zero) when we tried to split into two smaller communities. This is usually indicative that the original community was a well-defined group with lots of within-cluster ties, so that splitting it makes no difference (that’s the orange nodes in Figure 2 below).

Nevertheless, the test in the second community was positive, indicating we should split it into two. Because we left one of the original communities alone, the resulting network will have three communities after splitting the second one in two.

Note that the function returns the original two-split named vector of community assignments v, a NULL result for the first split, and a new vector assigning nodes in the second original split to two other communities (split[[2]]).

We now create a new three-community vector from these results:

Code
splits1$v[as.numeric(names(splits1$split[[2]]))] <- splits1$split[[2]] + 1
splits1$v
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
 1  1  1  1  1  3  3  1  1  1  1  1  1  1  1  1  1  3  1  1  1  1  1  1  1  1 
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 
 1  3  1  1  3  3  3  1  3  3  1  2  1  2  2  1  2  2  2  2  3  3  2  2  2  2 
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 
 2  2  3  3  3  2  2  3  2  2  2  2  2  2  2  2 

Figure 3 shows the results of the three-community partition.

Now let’s say we wanted to check if we should further split any of these three communities into two. All we need to do is create “dummy” variables for the new three community partition and feed these (and the three community membership vector) to the split.mult function, while keeping the original modularity matrix (Newman 2006a):

Code
c1 <- rep(0, length(splits1$v))
c2 <- rep(0, length(splits1$v))
c3 <- rep(0, length(splits1$v))
c1[which(splits1$v == 1)] <- 1
c2[which(splits1$v == 2)] <- 1
c3[which(splits1$v == 3)] <- 1
dummies <- cbind(c1, c2, c3)
splits2 <- split.mult(
  B = Bu,
  vol = sum(as.matrix(as_adjacency_matrix(ug))),
  u = dummies,
  v = splits1$v
)
splits2
$delta.Q
[1]  0.000  0.000 -0.002

$v
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
 1  1  1  1  1  3  3  1  1  1  1  1  1  1  1  1  1  3  1  1  1  1  1  1  1  1 
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 
 1  3  1  1  3  3  3  1  3  3  1  2  1  2  2  1  2  2  2  2  3  3  2  2  2  2 
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 
 2  2  3  3  3  2  2  3  2  2  2  2  2  2  2  2 

$split
list()

Here, the three modularity-split checks failed, as indicated by the delta.Q vector. So no further splits were made (hence the split object is an empty list). This tells us that, according to this method, three communities are the optimal partition.

Of course, if you are working on your project, you don’t have to mess with all of the functions above, because igraph has implemented Newman’s leading eigenvector (of the modularity matrix) community detection method (Newman 2006a) in a single function called cluster_leading_eigen.

To use it, just feed it the relevant graph:

Code
le.res <- cluster_leading_eigen(ug)

And examine the membership object stored in the results list:

Code
names(le.res$membership) <- 1:length(le.res$membership)
le.res$membership
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
 1  1  1  1  1  2  2  1  1  1  1  1  1  1  1  1  1  2  1  1  1  1  1  1  1  1 
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 
 1  2  1  1  2  2  2  1  2  2  1  3  1  3  3  1  3  2  3  3  2  2  3  3  3  3 
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 
 3  3  2  2  2  3  3  2  3  3  3  3  3  3  3  3 

Which returns nearly identical community assignments as above (with the labels between communities 2 and 3 flipped, and a single node classified differently).

7 Communities versus Exogenous Attributes

Remember, we began this discussion using an exogenous criterion (law firm status as partner or associate) to examine the network’s community structure (which performs pretty well according to modularity). But now we have also used a pure link-based approach to finding communities. How do they compare? Here’s a way to find out:

Code
library(kableExtra)
t <- table(V(ug)$status, le.res$membership)
kbl(t, row.names = TRUE, align = "c", format = "html") %>%
  column_spec(1, bold = TRUE) %>%
  kable_styling(
    full_width = TRUE,
    bootstrap_options = c("hover", "condensed", "responsive")
  )
1 2 3
1 27 9 0
2 3 7 22

This is just a contingency table listing status in the rows (1 = partner) and the three leading eigenvector communities in the columns.

We find that community one (the most coherent, in orange) is 90% partners (it contains 30 members, of whom only 3 are associates). So it is a high-status clique. Community three (in blue), on the other hand, is composed entirely of associates, a less dense but completely homogeneous, low-status clique. Finally, community two (green) is a status-mixed clique, composed of nine partners and seven associates.

So in this network, both status and endogenous group dynamics seem to be at play.

8 An Agglomerative Approach Based on the Modularity

The leading eigenvector approach discussed above is a divisive clustering algorithm. All nodes begin in one community; we split into two, then try to split one of those two into two others (if the modularity increases), and so forth.

But as we noted in the previous handout, another way to cluster is bottom up. All nodes begin in their own singleton cluster, and we join nodes if they maximize some criterion, in this case, the modularity. We then join new nodes to that group. If they increase the modularity, we try other joins, merging communities as we go, until we can’t increase it any further.

This agglomerative approach to clustering is not guaranteed to reach a global maximum, but it can work in most applied settings, even at the risk of getting stuck in a local optimum.

Newman (2004) developed a fast agglomerative algorithm that optimizes the modularity, a more recent version of which is included in an igraph function called cluster_fast_greedy (Clauset et al. 2004).

Let’s try it out to see how it works:

Code
fg.res <- cluster_fast_greedy(ug)

Before looking at what igraph barfs back, it is worth looking at the “greedy” part itself, since that’s the conceptually important part (the “fast” is just optimization stuff for large networks).

The Newman agglomerative approach works as follows. At each stage we ask which pair of current communities, if merged, would raise the modularity the most, and we make that merge. The gain from merging two groups turns out to be a simple quantity: the sum of the modularity-matrix entries that fall between them, divided by the total number of links.

Here’s a function that does that:

Code
greedy <- function(x) {
  B <- mod.mat(x)
  m <- ecount(x)
  comm <- 1:nrow(B) # every node starts in its own community
  repeat {
    best <- 0
    pair <- NULL
    for (i in unique(comm)) {
      for (j in unique(comm)) {
        if (i < j) {
          d <- sum(B[comm == i, comm == j]) / m # gain in modularity from merging i and j
          if (d > best) { # if best merge so far
            best <- d  # replace best
            pair <- c(i, j) # record the pair of communities the best gain came from
          }
        }
      }
    }
    if (is.null(pair)) break # no merge improved modularity
    comm[comm == pair[2]] <- pair[1] # merge community j into i from the best remaining gain
  }
  return(comm)
}

It works like this:

  • Lines 1-4 take a graph as input, compute the modularity matrix (B), store the number of edges in the graph in object m, and give every node a unique label (a number between 1 and \(N\) where \(N\) is the number of nodes) stored in the comm vector. Because the algorithm is agglomerative, every node starts in a community of one.

  • Lines 5-7 and 19 control how long the merging continues. The repeat loop keeps going until a full pass finds no improving pair which means that pair remains set to NULL. The object best records the largest gain seen so far in the for loop and pair the two communities that gain came from.

  • Lines 8-9 loop over every pair of current communities (note we use unique on the comm vector because it will eventually contain repeated values for nodes assigned to the same community). Because the modularity matrix is symmetric in this case of an undirected graph, the condition on line 10 restricts the scan to pairs with i < j, so each unordered pair of communities is visited once rather than twice.

  • Line 11 scores a candidate merge as the sum of the matrix entries lying between the two groups, divided by the total number of links. Because line 10 reads only one of the two symmetric blocks, that sum is half the total weight between the groups, but the denominator is also half the matrix’s own scale: the modularity matrix divides by the sum of all entries, which for an undirected graph is twice the number of edges.

  • Lines 12-14 keep the pair with the largest positive gain, and line 20 makes that merge by relabelling every node in the second community with the label of the first. When no pair clears zero, line 22 returns the labels.

The result matches igraph exactly—the same three communities and the same modularity:

Code
gr.res <- greedy(ug)
modularity(ug, gr.res)
[1] 0.3605433
Code
modularity(ug, fg.res$membership)
[1] 0.3605433

The difference between our little function above and the igraph version is speed (not particularly noticeable in a small network like our example). The igraph version keeps the candidate gains in a heap and updates only the pairs affected by each merge, instead of rescanning every pair after every merge; that change in bookkeeping efficiency is what the “fast” in cluster_fast_greedy refers to.

The resulting fg.res list object in igraph has various sub-objects as components. One of them is called merges, which provides a history of the various merges that led to the final communities. This means we can view the results as a dendrogram, just as we did with structural similarity analyses based on hierarchical clustering of a distance matrix.

To do this, we just transform the resulting object into an hclust object and plot:

Code
hc <- as.hclust(fg.res)
par(cex = 0.5) # smaller labels
plot(hc)

This gives us the sense that the network is divided into three communities, as we saw earlier. If we wanted to see which nodes are in which, we could just cut the dendrogram at \(k = 3\):

Code
library(dendextend)
cutree(hc, k = 3)
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
 1  1  2  1  2  2  2  1  1  1  1  1  1  2  1  1  1  2  1  1  1  1  1  1  2  1 
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 
 1  2  1  2  2  2  2  1  2  2  1  3  1  3  3  3  3  3  3  3  2  2  3  1  3  3 
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 
 3  3  3  2  3  3  3  2  3  3  3  3  3  3  3  3 

This provides the relevant assignment to communities (if we wanted more communities, we would cut the tree at a lower height).

Of course, this information was already stored in our results in the membership object:

Code
names(fg.res$membership) <- 1:length(fg.res$membership)
fg.res$membership
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
 1  1  2  1  2  2  2  1  1  1  1  1  1  2  1  1  1  2  1  1  1  1  1  1  2  1 
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 
 1  2  1  2  2  2  2  1  2  2  1  3  1  3  3  3  3  3  3  3  2  2  3  1  3  3 
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 
 3  3  3  2  3  3  3  2  3  3  3  3  3  3  3  3 
Figure 2: Law Firm Friendship Network by The Best Binary Partition Using the Leading Eigenvector of the Modularity Matrix Approach.
Figure 3: Law Firm Friendship Network by The Best Three-Community Partition Using the Leading Eigenvector of the Modularity Matrix Approach.
Figure 4: Law Firm Friendship Network by The Best Three-Community Partition Using the Fast-Greedy Modularity Maximization Approach.

Figure 4 visualizes the resulting three-community partition, which is pretty close to what we got using the leading eigenvector method.

References

Brandes, Ulrik, Daniel Delling, Marco Gaertler, et al. 2007. “On Modularity Clustering.” IEEE Transactions on Knowledge and Data Engineering 20 (2): 172–88.
Clauset, Aaron, Mark EJ Newman, and Cristopher Moore. 2004. “Finding Community Structure in Very Large Networks.” Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 70 (6): 066111.
Lazega, Emmanuel. 2001. The Collegial Phenomenon: The Social Mechanisms of Cooperation Among Peers in a Corporate Law Partnership. Oxford University Press.
Newman, Mark EJ. 2004. “Fast Algorithm for Detecting Community Structure in Networks.” Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 69 (6): 066133.
Newman, Mark EJ. 2006a. “Finding Community Structure in Networks Using the Eigenvectors of Matrices.” Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 74 (3): 036104.
Newman, Mark EJ. 2006b. “Modularity and Community Structure in Networks.” Proceedings of the National Academy of Sciences 103 (23): 8577–82.

Footnotes

  1. Actually, this is not true; finding the partition that maximizes the modularity in a graph is an NP hard problem (Brandes et al. 2007), so this is just a pretty good approximation of that.↩︎