362
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
the clusters to which their two nodes belong. The choices would be random,
because all distances represented by an edge are the same.
Example 10.3 : Consider again the graph of Fig. 10.1, repeated here as Fig.
10.3. First, let us agree on what the communities are. At the highest level,
it appears that there are two communities {A, B, C} and {D, E, F, G}. How-
ever, we could also view {D, E, F} and {D, F, G} as two subcommunities of
{D, E, F, G}; these two subcommunities overlap in two of their members, and
thus could never be identiﬁed by a pure clustering algorithm. Finally, we could
consider each pair of individuals that are connected by an edge as a community
of size 2, although such communities are uninteresting.
A
B
D
E
G
F
C
Figure 10.3: Repeat of Fig. 10.1
The problem with hierarchical clustering of a graph like that of Fig. 10.3 is
that at some point we are likely to chose to combine B and D, even though
they surely belong in diﬀerent clusters. The reason we are likely to combine B
and D is that D, and any cluster containing it, is as close to B and any cluster
containing it, as A and C are to B. There is even a 1/9 probability that the
ﬁrst thing we do is to combine B and D into one cluster.
There are things we can do to reduce the probability of error.
We can
run hierarchical clustering several times and pick the run that gives the most
coherent clusters. We can use a more sophisticated method for measuring the
distance between clusters of more than one node, as discussed in Section 7.2.3.
But no matter what we do, in a large graph with many communities there is a
signiﬁcant chance that in the initial phases we shall use some edges that connect
two nodes that do not belong together in any large community.
✷
Now, consider a point-assignment approach to clustering social networks.
Again, the fact that all edges are at the same distance will introduce a number
of random factors that will lead to some nodes being assigned to the wrong
cluster. An example should illustrate the point.
Example 10.4 : Suppose we try a k-means approach to clustering Fig. 10.3.
As we want two clusters, we pick k = 2. If we pick two starting nodes at random,
they might both be in the same cluster. If, as suggested in Section 7.3.2, we
start with one randomly chosen node and then pick another as far away as
