26
Chapter 3. Background
to be eliminated, and the degree of nodes needs to be considered. The non-trivial
eigenvectors associated with the smallest eigenvalues of the random-walk normalized Laplacian matrix, L rw is a good approximate solution, since the random-walk
matrix and random-walk normalized Laplacian matrix L rw have the same eigenvectors with corresponding eigenvalues λ and 1 − λ , respectively.
Meila and Shi [58] proved that NCut and transition probabilities of the random
walk are formally equal. In other words, finding the minimum value of NCut is
actually looking for a partition where a random walk seldom transitions from one
group to another.
Commute distance approach
In a graph, the commute distance between two nodes is the expected distance of a
random walk from one node to another and back again. Because of the randomness, this commute distance takes into account all possible paths between the two
nodes. Even the presence of a long path between two nodes may reduce the commute distance between them. Based on electrical network theory, Klein and Randi´ c
[45] proved that the general commute distance c i j between node i and j could be
computed with the help of the graph Laplacian
c i j = vol(V )
n
∑
k=1
1
λ k
( f
(k)
i − f
(k)
j )
2
where λ k and f (k) are the k-th eigenvalue and eigenvector of L. The equation tells
us that the commute distance between two nodes is the sum of the differences in
all eigenvectors divided by the corresponding eigenvalues. Therefore, the smaller
eigenvalues (except 0) and the corresponding eigenvectors play the most important
roles in the commute distance. This commute distance can also be viewed as the average first-passage time based on a Markov-chain model of random walk [35]. Even
though the commute distance seems to be helpful to explain the spectral embedding,
there is only a rather loose relation between spectral embedding and the commute
distance [101].
3.4.1 Undirected spectral clustering algorithms
Here three clustering algorithms for undirected graphs are introduced based on these
different approaches. All the algorithms begin with an adjacency matrix, W , and a
number, k, of clusters into which the graph is to be partitioned.
Unnormalized Laplacian clustering
After the Laplacian matrix L is constructed, the k smallest eigenvalues and the corresponding eigenvectors of L are computed. The ith entries of the k eigenvectors
are viewed as the position coordinates of the node i. Thus, we can directly cluster
the nodes by comparing their positions based on Euclidean distance. The clustering
algorithm can be K-means or any other geometric method.
Chapter 3. Background
to be eliminated, and the degree of nodes needs to be considered. The non-trivial
eigenvectors associated with the smallest eigenvalues of the random-walk normalized Laplacian matrix, L rw is a good approximate solution, since the random-walk
matrix and random-walk normalized Laplacian matrix L rw have the same eigenvectors with corresponding eigenvalues λ and 1 − λ , respectively.
Meila and Shi [58] proved that NCut and transition probabilities of the random
walk are formally equal. In other words, finding the minimum value of NCut is
actually looking for a partition where a random walk seldom transitions from one
group to another.
Commute distance approach
In a graph, the commute distance between two nodes is the expected distance of a
random walk from one node to another and back again. Because of the randomness, this commute distance takes into account all possible paths between the two
nodes. Even the presence of a long path between two nodes may reduce the commute distance between them. Based on electrical network theory, Klein and Randi´ c
[45] proved that the general commute distance c i j between node i and j could be
computed with the help of the graph Laplacian
c i j = vol(V )
n
∑
k=1
1
λ k
( f
(k)
i − f
(k)
j )
2
where λ k and f (k) are the k-th eigenvalue and eigenvector of L. The equation tells
us that the commute distance between two nodes is the sum of the differences in
all eigenvectors divided by the corresponding eigenvalues. Therefore, the smaller
eigenvalues (except 0) and the corresponding eigenvectors play the most important
roles in the commute distance. This commute distance can also be viewed as the average first-passage time based on a Markov-chain model of random walk [35]. Even
though the commute distance seems to be helpful to explain the spectral embedding,
there is only a rather loose relation between spectral embedding and the commute
distance [101].
3.4.1 Undirected spectral clustering algorithms
Here three clustering algorithms for undirected graphs are introduced based on these
different approaches. All the algorithms begin with an adjacency matrix, W , and a
number, k, of clusters into which the graph is to be partitioned.
Unnormalized Laplacian clustering
After the Laplacian matrix L is constructed, the k smallest eigenvalues and the corresponding eigenvectors of L are computed. The ith entries of the k eigenvectors
are viewed as the position coordinates of the node i. Thus, we can directly cluster
the nodes by comparing their positions based on Euclidean distance. The clustering
algorithm can be K-means or any other geometric method.