10.2. CLUSTERING OF SOCIAL-NETWORK GRAPHS
363
possible, we don’t do much better; we could thereby pick any pair of nodes not
connected by an edge, e.g., E and G in Fig. 10.3.
However, suppose we do get two suitable starting nodes, such as B and F.
We shall then assign A and C to the cluster of B and assign E and G to the
cluster of F. But D is as close to B as it is to F, so it could go either way, even
though it is “obvious” that D belongs with F.
If the decision about where to place D is deferred until we have assigned
some other nodes to the clusters, then we shall probably make the right decision.
For instance, if we assign a node to the cluster with the shortest average distance
to all the nodes of the cluster, then D should be assigned to the cluster of F, as
long as we do not try to place D before any other nodes are assigned. However,
in large graphs, we shall surely make mistakes on some of the ﬁrst nodes we
place.
✷
10.2.3
Betweenness
Since there are problems with standard clustering methods, several specialized
clustering techniques have been developed to ﬁnd communities in social net-
works. In this section we shall consider one of the simplest, based on ﬁnding
the edges that are least likely to be inside a community.
Deﬁne the betweenness of an edge (a, b) to be the number of pairs of nodes
x and y such that the edge (a, b) lies on the shortest path between x and y.
To be more precise, since there can be several shortest paths between x and y,
edge (a, b) is credited with the fraction of those shortest paths that include the
edge (a, b). As in golf, a high score is bad. It suggests that the edge (a, b) runs
between two diﬀerent communities; that is, a and b do not belong to the same
community.
Example 10.5 : In Fig. 10.3 the edge (B, D) has the highest betweenness, as
should surprise no one. In fact, this edge is on every shortest path between
any of A, B, and C to any of D, E, F, and G. Its betweenness is therefore
3 × 4 = 12. In contrast, the edge (D, F) is on only four shortest paths: those
from A, B, C, and D to F.
✷
10.2.4
The Girvan-Newman Algorithm
In order to exploit the betweenness of edges, we need to calculate the number of
shortest paths going through each edge. We shall describe a method called the
Girvan-Newman (GN) Algorithm, which visits each node X once and computes
the number of shortest paths from X to each of the other nodes that go through
each of the edges. The algorithm begins by performing a breadth-ﬁrst search
(BFS) of the graph, starting at the node X. Note that the level of each node in
the BFS presentation is the length of the shortest path from X to that node.
Thus, the edges that go between nodes at the same level can never be part of
a shortest path from X.
