10.4. PARTITIONING OF GRAPHS
379
2
3
6
5
4
1
Figure 10.16: Graph for illustrating partitioning by spectral analysis


3
-1
-1
-1
0
0
-1
2
-1
0
0
0
-1
-1
3
0
0
-1
-1
0
0
3
-1
-1
0
0
0
-1
2
-1
0
0
-1
-1
-1
3


Figure 10.17: The Laplacian matrix for Fig. 10.16
The second eigenvector has three positive and three negative components.
It makes the unsurprising suggestion that one group should be {1, 2, 3}, the
nodes with positive components, and the other group should be {4, 5, 6}.
✷
Eigenvalue
0
1
3
3
4
5
Eigenvector
1
1
−5
−1
−1
−1
1
2
4
−2
1
0
1
1
1
3
−1
1
1
−1
−5
−1
1
1
1
−2
4
−2
−1
0
1
−1
1
3
1
−1
Figure 10.18: Eigenvalues and eigenvectors for the matrix of Fig. 10.17
10.4.5
Alternative Partitioning Methods
The method of Section 10.4.4 gives us a good partition of the graph into two
pieces that have a small cut between them. There are several ways we can use
the same eigenvectors to suggest other good choices of partition. First, we are
not constrained to put all the nodes with positive components in the eigenvector
into one group and those with negative components in the other. We could set
the threshold at some point other than zero.
For instance, suppose we modiﬁed Example 10.19 so that the threshold was
not zero, but −1.5. Then the two nodes 4 and 6, with components −1 in the
second eigenvector of Fig. 10.18, would join 1, 2, and 3, leaving ﬁve nodes in one
