|
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. |
|