380
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
component and only node 5 in the other. That partition would have a cut of size
two, as did the choice based on the threshold of zero, but the two components
have radically diﬀerent sizes, so we would tend to prefer our original choice.
However, there are other cases where the threshold zero gives unequally sized
components, as would be the case if we used the third eigenvector in Fig. 10.18.
We may also want a partition into more than two components. One approach
is to use the method described above to split the graph into two, and then use
it repeatedly on the components to split them as far as desired.
A second
approach is to use several of the eigenvectors, not just the second, to partition
the graph. If we use m eigenvectors, and set a threshold for each, we can get a
partition into 2m groups, each group consisting of the nodes that are above or
below threshold for each of the eigenvectors, in a particular pattern.
It is worth noting that each eigenvector except the ﬁrst is the vector x that
minimizes xTLx, subject to the constraint that it is orthogonal to all previous
eigenvectors. This constraint generalizes the constraints we described for the
second eigenvector in a natural way. As a result, while each eigenvector tries
to produce a minimum-sized cut, the fact that successive eigenvectors have to
satisfy more and more constraints generally causes the cuts they describe to be
progressively worse.
Example 10.20 : Let us reconsider the graph of Fig. 10.16, for which the
eigenvectors of its Laplacian matrix were tabulated in Fig. 10.18. The third
eigenvector, with a threshold of 0, puts nodes 1 and 4 in one group and the
other four nodes in the other. That is not a bad partition, but its cut size is
four, compared with the cut of size two that we get from the second eigenvector.
If we use both the second and third eigenvectors, we put nodes 2 and 3 in
one group, because their components are positive in both eigenvectors. Nodes
5 and 6 are in another group, because their components are negative in the
second eigenvector and positive in the third. Node 1 is in a group by itself
because it is positive in the second eigenvector and negative in the third, while
node 4 is also in a group by itself because its component is negative in both
eigenvectors. This partition of a six-node graph into four groups is too ﬁne a
partition to be meaningful. But at least the groups of size two each have an
edge between the nodes, so it is as good as we could ever get for a partition
into groups of these sizes.
✷
10.4.6
Exercises for Section 10.4
Exercise 10.4.1: For the graph of Fig. 10.9, construct:
(a) The adjacency matrix.
(b) The degree matrix.
(c) The Laplacian matrix.
