3.4. Spectral approaches to clustering
27
Random walk normalized Laplacian clustering
In random-walk normalized Laplacian clustering [58], the k smallest eigenvalues and
the corresponding eigenvectors of L rw are first computed, and then the eigenvectors
are used to cluster the graph in the same way as the unnormalized Laplacian clustering. It should be noted that the (generalized) eigenvectors are not orthogonal to
each other. (Eigenvectors may not be real in some computational environments. For
example, eigenvectors in MATLAB are always orthogonal. If the real part cannot
be orthogonal, it adds an imaginary part to make the eigenvectors orthogonal. We
only need the real part, which is the same as the generalized eigenvectors of the
generalized eigenproblem L f = λ D f . Alternatively, we can compute the k smallest eigenvectors of L sym first, and then convert them to the eigenvectors for L rw by
multiplying by D −1/2 .)
Symmetric normalized Laplacian clustering
In symmetric normalized Laplacian clustering [71], the k smallest eigenvectors are
first computed, each row considered as coordinates of the corresponding node, and
then the coordinate value of each node is renormalized to norm 1. This corresponds
to projecting the nodes onto the surface of a unit hypersphere with the origin as the
center. The nodes can then be clustered based on the new positions.
3.4.2 Which Laplacian clustering should be used?
When the network is connected, and the degrees of all nodes are approximately the
same, the eigenvectors of the three Laplacian matrices are similar, and the eigenvalues of the unnormalized Laplacian matrix are just the degree times the eigenvalues
of the normalized Laplacian matrices. The clustering result will be similar regardless
of which technique is used.
However, if the degrees of nodes in a network are quite different, the three
different techniques will produce different clusterings. As before, there is some evidence that using a normalized Laplacian will lead to better results than using the
unnormalized Laplacian.
One of the arguments is based on the graph cut point of view. As mentioned
earlier, unnormalized Laplacian clustering is an approximation of RatioCut, and normalized Laplacian clustering is an approximation of NCut. The differences between
RatioCut and NCut are the denominators — one uses the number of nodes in a cluster, and the other uses the volume of edges in a cluster. Both cuts minimize the edges
between groups and also maximize the edges within groups. From the definition of
RatioCut and NCut, we can infer that the definitions of within-group RatioCut and
NCut are:
W RatioCut(A 1 , ..., A k ) :=
k
∑
i=1
W (A i , A i )
|A i |
=
k
∑
i=1
vol(A i )
|A i |
−
W (A i , A i )
|A i |
27
Random walk normalized Laplacian clustering
In random-walk normalized Laplacian clustering [58], the k smallest eigenvalues and
the corresponding eigenvectors of L rw are first computed, and then the eigenvectors
are used to cluster the graph in the same way as the unnormalized Laplacian clustering. It should be noted that the (generalized) eigenvectors are not orthogonal to
each other. (Eigenvectors may not be real in some computational environments. For
example, eigenvectors in MATLAB are always orthogonal. If the real part cannot
be orthogonal, it adds an imaginary part to make the eigenvectors orthogonal. We
only need the real part, which is the same as the generalized eigenvectors of the
generalized eigenproblem L f = λ D f . Alternatively, we can compute the k smallest eigenvectors of L sym first, and then convert them to the eigenvectors for L rw by
multiplying by D −1/2 .)
Symmetric normalized Laplacian clustering
In symmetric normalized Laplacian clustering [71], the k smallest eigenvectors are
first computed, each row considered as coordinates of the corresponding node, and
then the coordinate value of each node is renormalized to norm 1. This corresponds
to projecting the nodes onto the surface of a unit hypersphere with the origin as the
center. The nodes can then be clustered based on the new positions.
3.4.2 Which Laplacian clustering should be used?
When the network is connected, and the degrees of all nodes are approximately the
same, the eigenvectors of the three Laplacian matrices are similar, and the eigenvalues of the unnormalized Laplacian matrix are just the degree times the eigenvalues
of the normalized Laplacian matrices. The clustering result will be similar regardless
of which technique is used.
However, if the degrees of nodes in a network are quite different, the three
different techniques will produce different clusterings. As before, there is some evidence that using a normalized Laplacian will lead to better results than using the
unnormalized Laplacian.
One of the arguments is based on the graph cut point of view. As mentioned
earlier, unnormalized Laplacian clustering is an approximation of RatioCut, and normalized Laplacian clustering is an approximation of NCut. The differences between
RatioCut and NCut are the denominators — one uses the number of nodes in a cluster, and the other uses the volume of edges in a cluster. Both cuts minimize the edges
between groups and also maximize the edges within groups. From the definition of
RatioCut and NCut, we can infer that the definitions of within-group RatioCut and
NCut are:
W RatioCut(A 1 , ..., A k ) :=
k
∑
i=1
W (A i , A i )
|A i |
=
k
∑
i=1
vol(A i )
|A i |
−
W (A i , A i )
|A i |