10.4. PARTITIONING OF GRAPHS
377


2
-1
-1
0
0
0
0
-1
3
-1
-1
0
0
0
-1
-1
2
0
0
0
0
0
-1
0
4
-1
-1
-1
0
0
0
-1
2
-1
0
0
0
0
-1
-1
3
-1
0
0
0
-1
0
-1
2


Figure 10.15: The Laplacian matrix for Fig. 10.12
10.4.4
Eigenvalues of the Laplacian Matrix
We can get a good idea of the best way to partition a graph from the eigenvalues
and eigenvectors of its Laplacian matrix.
In Section 5.1.2 we observed how the
principal eigenvector (eigenvector associated with the largest eigenvalue) of the
transition matrix of the Web told us something useful about the importance of
Web pages. In fact, in simple cases (no taxation) the principal eigenvector is the
PageRank vector. When dealing with the Laplacian matrix, however, it turns
out that the smallest eigenvalues and their eigenvectors reveal the information
we desire.
The smallest eigenvalue for every Laplacian matrix is 0, and its correspond-
ing eigenvector is [1, 1, . . ., 1]. To see why, let L be the Laplacian matrix for a
graph of n nodes, and let 1 be the column vector of all 1’s with length n. We
claim L1 is a column vector of all 0’s. To see why, consider row i of L. Its
diagonal element has the degree d of node i. Row i also will have d occurrences
of −1, and all other elements of row i are 0. Multiplying row i by column vector
1 has the eﬀect of summing the row, and this sum is clearly d + (−1)d = 0.
Thus, we can conclude L1 = 01, which demonstrates that 0 is an eigenvalue
and 1 its corresponding eigenvector.
There is a simple way to ﬁnd the second-smallest eigenvalue for any matrix,
such as the Laplacian matrix, that is symmetric (the entry in row i and column
j equals the entry in row j and column i).
While we shall not prove this
fact, the second-smallest eigenvalue of L is the minimum of xTLx, where x =
[x1, x2, . . . , xn] is a column vector with n components, and the minimum is
taken under the constraints:
1. The length of x is 1; that is Pn
i=1 x2
i = 1.
2. x is orthogonal to the eigenvector associated with the smallest eigenvalue.
Moreover, the value of x that achieves this minimum is the second eigenvector.
When L is a Laplacian matrix for an n-node graph, we know something
more. The eigenvector associated with the smallest eigenvalue is 1. Thus, if x
