Database Reference
In-Depth Information
ation) 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 corresponding eigenvec-
tor 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
L
1
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 effect of summing the row, and this sum is clearly
d
+ (−1)
d
= 0. Thus, we can conclude
L
1
= 0
1
, which demonstrates that 0 is an eigenvalue and
1
its
corresponding eigenvector.
There is a simple way to find 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
x
T
L
x
, where
x
= [
x
1
, x
2
, . . . , x
n
] is a column vector with
n
components,
and the minimum is taken under the constraints:
(1) The length of
x
is 1; that is, .
(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 eigen-
vector associated with the smallest eigenvalue is
1
. Thus, if
x
is orthogonal to
1
, we must
have
In addition, for the Laplacian matrix, the expression
x
T
L
x
has a useful equivalent expres-
sion. Recall that
L
=
D
−
A
, where
D
and
A
are the degree and adjacency matrices of the
same graph. Thus,
x
T
L
x
=
x
T
D
x
−
x
T
A
x
. Let us evaluate the term with
D
and then the term
for
A
. Here
D
x
is the column vector [
d
1
x
1
, d
2
x
2
, . . . , d
n
x
n
], where
d
i
is the degree of the
i
th
node of the graph. Thus,
x
T
D
x
is
Now, turn to
x
T
A
x
. The
i
th component of the column vector
A
x
is the sum of
x
j
over all
j
such that there is an edge (
i, j
) in the graph. Thus, −
x
T
A
x
is the sum of −2
x
i
x
j
over all
pairs of nodes {
i, j
} such that there is an edge between them. Note that the factor 2 appears
because each set {
i, j
} corresponds to two terms, −
x
i
x
j
and −
x
j
x
i
.
We can group the terms of
x
T
L
x
in a way that distributes the terms to each pair {
i, j
}.
From −
x
T
A
x
, we already have the term −2
x
i
x
j
. From
x
T
D
x
, we distribute the term to the
d
i
