10.2. CLUSTERING OF SOCIAL-NETWORK GRAPHS
367
it is not deﬁned for pairs of nodes that are unconnected by an edge, and might
not satisfy the triangle inequality even when deﬁned. 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 components 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 between-
ness, until the graph has broken into a suitable number of connected compo-
nents.
Example 10.9 : Let us start with our running example, the graph of Fig. 10.1.
We see it with 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.
A
B
D
E
G
F
C
5
12
4
1
5
4.5
1.5
1.5
4.5
Figure 10.7: Betweenness scores for the graph of Fig. 10.1
Clearly, edge (B, D) has the highest betweenness, so it is removed ﬁrst.
That leaves us with exactly the communities we observed make the most sense,
namely: {A, B, C} and {D, E, F, G}.
However, we can continue to remove
edges. Next to leave are (A, B) and (B, C) with a score of 5, followed by (D, E)
and (D, G) with a score of 4.5. Then, (D, F), whose score is 4, would leave the
graph. We see in Fig. 10.8 the graph that remains.
The “communities” of Fig. 10.8 look strange. One implication is that A and
C are more closely knit to each other than to B. That is, in some sense B is a
“traitor” to the community {A, B, C} because he has a friend D outside that
community. Likewise, D can be seen as a “traitor” to the group {D, E, F, G},
which is why in Fig. 10.8, only E, F, and G remain connected.
✷
10.2.6
Exercises for Section 10.2
Exercise 10.2.1: Figure 10.9 is an example of a social-network graph. Use
the Girvan-Newman approach to ﬁnd the number of shortest paths from each
