Database Reference
In-Depth Information
pairs that include node
i
. As a result, we can associate with each pair {
i, j
} that has an edge
between nodes
i
and
j
the terms This expression is equivalent to (
x
i
−
x
j
)
2
. Therefore,
we have proved that
x
T
L
x
equals the sum over all graph edges (
i, j
) of (
x
i
−
x
j
)
2
.
Recall that the second-smallest eigenvalue is the minimum of this expression under the
constraint that Intuitively, we minimize it by making
x
i
and
x
j
close whenever there is
an edge between nodes
i
and
j
in the graph. We might imagine that we could choose
for all
i
and thus make this sum 0. However, recall that we are constrained to choose
x
to
be orthogonal to
1
, which means the sum of the
x
i
is 0. We are also forced to make be
1, so all components cannot be 0. As a consequence,
x
must have some positive and some
negative components.
We can obtain a partition of the graph by taking one set to be the nodes
i
whose corres-
ponding vector component
x
i
is positive and the other set to be those whose components are
negative. This choice does not guarantee a partition into sets of equal size, but the sizes are
likely to be close. We believe that the cut between the two sets will have a small number
of edges because (
x
i
−
x
j
)
2
is likely to be smaller if both
x
i
and
x
j
have the same sign than
if they have different signs. Thus, minimizing
x
T
L
x
under the required constraints will tend
to give
x
i
and
x
j
the same sign if there is an edge (
i, j
).
EXAMPLE
10.19 Let us apply the above technique to the graph of
Fig. 10.16
.
The Laplacian
matrix for this graph is shown in
Fig. 10.17
. By standard methods or math packages we can
find all the eigenvalues and eigenvectors of this matrix. We shall simply tabulate them in
Fig. 10.18
, from lowest eigenvalue to highest. Note that we have not scaled the eigenvec-
tors to have length 1, but could do so easily if we wished.
Figure 10.16
Graph for illustrating partitioning by spectral analysis
Figure 10.17
The Laplacian matrix for
Fig. 10.16
Figure 10.18
Eigenvalues and eigenvectors for the matrix of
Fig. 10.17
