We present a study of the web based user navigation patterns mining and propose a novel approach for clustering of user navigation patterns. The approach is based on the graph partitioning for modeling user navigation patterns. In order to mining user navigation patterns, we establish an undirected graph based on connectivity between each pair of the web pages. Moreover, we propose novel formula for assigning weights to edges of the graph. The experimental results represent that the approach can improve the
quality of clustering for user navigation pattern in web usage mining systems. These results can be use for predicting user’s next request in the huge web sites.