Modularity versus mincut

  when dividing an organization

An example graph

The graph contains three nodes with strong coupling to each other and weak coupling to the rest. These nodes are labeled B1, B2 and B3.

The Gomory Hu tree

The Gomory Hu tree of the example graph is shown on the left. The minimal cut in this tree is the link between A3 and B1. The weight of the cut is only 2, the smallest value in the tree. Removing this link from the tree results in two subtrees: B1, B2 and B2 on one side and the rest of the nodes on the other side.

The minimal cut

The figure on the left shows the minimal cut, which isolates nodes B1, B2 and B3, cutting only two edges with weight 1. However, this partitioning appears not to have a good modularity. (only 0.19)
This is because the cluster with then B-nodes is too small. The contribution of the internal links to the modularity is not optimal.
The partitioning with the best modularity (for two partitions) is shown in the next picture.

Best modularity with two clusters

Although the sum of the weights of the links that are cut is now 4, this negative effect is more than compensated by the positive effect of the many internal links to the modularity (0.4, more than twice the value of the mincut).

Best modularity with three clusters

It is interesting to note that the cluster with B-nodes reappears in the optimal division of the graph into three clusters. This is probably because the average size of the clusters approaches that of the B-node cluster. So the smallness of this cluster is no longer a disadvantage.