Database Reference
In-Depth Information
Figure 10.6
Final step of the Girvan-Newman Algorithm - completing the credit calculation
The credit on each of the edges in
Fig. 10.6
is the contribution to the betweenness of
that edge due to shortest paths from
E
. For example, this contribution for the edge (
E, D
) is
4.5.
□
To complete the betweenness calculation, we have to repeat this calculation for every
node as the root and sum the contributions. Finally, we must divide by 2 to get the true
betweenness, since every shortest path will be discovered twice, once for each of its end-
points.
10.2.5
Using Betweenness to Find Communities
The betweenness scores for the edges of a graph behave something like a distance measure
on the nodes of the graph. It is not exactly a distance measure, because it is not defined for
pairs of nodes that are unconnected by an edge, and might not satisfy the triangle inequal-
ity even when defined. However, we can cluster by taking the edges in order of increasing
betweenness and add them to the graph one at a time. At each step, the connected compon-
ents of the graph form some clusters. The higher the betweenness we allow, the more edges
we get, and the larger the clusters become.
More commonly, this idea is expressed as a process of edge removal. Start with the
graph and all its edges; then remove edges with the highest betweenness, until the graph
has broken into a suitable number of connected components.
the betweenness for each edge in
Fig. 10.7
. The calculation of the betweenness will be left
to the reader. The only tricky part of the count is to observe that between
E
and
G
there are
two shortest paths, one going through
D
and the other through
F
. Thus, each of the edges
(
D, E
), (
E, F
), (
D, G
), and (
G, F
) are credited with half a shortest path.
