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.