A Random Walk Based Clustering Algorithm

In this paper, a modified model of random walk is proposed, and then a clustering algorithm is developed based on this model. In the algorithm, at first a weighted and undirected graph G(V,E,d) is constructed among data points in a dataset according to the model, where each data point corresponds to a vertex in the graph, and is regarded as an agent who can move randomly in space. Next, the transition probabilities of data points are computed, and then each data point chooses a neighbor randomly in its neighborhood as a transition direction and takes a step to it. As all data points walk in space at random repeatedly, the data points that belong to the same class are located at a same position, whereas those that belong to different classes are away from one another. Consequently, the experimental results demonstrate that data points in datasets are clustered reasonably and efficiently. Moreover, the comparison with other algorithms also provides an indication of the effectiveness of the algorithm.