Spectral clustering by considering stationary distribution vector and transition matrix

Abstract

One of the popular methods of data clustering is spectral clustering. The main step of this method is constructing a graph representation of the data set and its similarity matrix. The similarity matrices which are constructed based on some important points not all data points, are among the main approaches. In this paper, the stationary distribution for a random walk on a weighted graph $G$ is considered to find anchor points of the data set. Then we build the similarity matrix based on the anchor nodes and the weighted random walk transition matrix. After that, spectral clustering is applied on the gained similarity matrix. We propose the theoretical discussions and then we evaluate our method on benchmarks.