Centrality verus modularity and mincut

  when dividing an organization

An example graph

This graph contains two clusters (brown and green) that are richly interconnected but the links carry only a low weight (1). The two links that connect the intended clusters, however, have a large weight (A1->A5 and A3->A7).
We will use the centrality measure to partition the graph. The centrality of a link measures the number of shortest paths that go through that link. To calculate this measure the shortest paths are computed between all node pairs. Then, for every link the the fraction of shortest path that go through that link is determined.
The result of this measure for the example graph is shown in the next figure.

(The "length" of a path between two nodes is the sum of the link weights on that path. The graph is considered undirected for computing shorstest paths and the centrality measure)

Centrality measure

A link label now indicates the fraction of shortest paths that go through this link. The link with the highest fraction of shortest paths is A3->A7 (20.3%) and then follows A1->A5 with 11.7%. This confirms our intuition on shortest paths when we look at the original graph. Both links have a central position between the two intended clusters. The centrality algorthm now reasons as follows:
A link with a high centrality is probably a link between two clusters (because many shortest path go through it). Links with the highest centrality are deleted until the graph falls apart and shows the required number of clusters. For two clusters the result is shown in the next figure.

Centrality clustering

The two heavy weighted links carry most of the shortest paths, in spite of their high weight (5). These links are deleted by the algorithm and the intended brown-green structure is found.
The following pictures show that neither the mincut nor the modularity is able to find this structure.

The best modularity

The modularity algorithm is not able to find the intended clusters. It tries to equally divide the heavy weighted links over the two clusters (and, at the same time, to establish a minimal cut through the remaining low weighted links)

The Gomory Hu tree

The mincut tree also does not show the intended clusters. The large weights on the inter-cluster links will never allow for a minimal cut through these links. The minimal cut in this tree just cuts off the single node A4 (or A8).

The third best minimal cut.

The largest cluster size in the mincut tree is almost the intended clustering. However, node A5 is, of course, not cut at the heavy weighted link, but at the two low weighted links.