Abstract: In this paper, we propose a new graph clustering algorithm, based on both structural and attribute characteristics, and use neighborhood random walk distances to measure vertex closeness, and make a clustering based on the transitional probability matrix.The experimental results show the effectiveness of the clustering algorithm that based on attribute augmented graph.The clustering algorithm has fully considered the attribute characteristics of every vertex based on the topological structure of graph.The result of clustering will better suit the practical application.