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