Community detection methods for directed graphs

Community detection has been developed extensively with many different algorithms. One of the most powerful algorithms on undirected graphs is Walktrap, whose idea is to define the distance between vertices by using random walk and to evaluate the clusters by modularity function based on the degree of vertices. Although there are many directions to develop this method for directed graphs, none of those are effective. In this paper, we are interested in studying the Walktrap algorithm \cite{latapy}, the spectral method \cite{main}, and then extending them for directed graphs. We propose a new approach, in which the distance between vertices is defined by hitting time, and the modularity is computed based on the stationary distribution of a random walk. These definitions are very effective because of the development of algorithms about the hitting time and the stationary distribution so it is possible to compute them in good complexity. In particular, our proposed method can apply to directed graphs and the well-known results on undirected graphs are special cases. Besides, we also use the spectral method for these problems. And finally, we have also implemented our algorithms to demonstrate the plausibility and effectiveness of these methods.