We propose a generative model to detect globally optimal community structures in networks by utilizing random walks. Sophisticated parameter optimization algorithms are developed based on the Markov chain Monte Carlo methods to overcome limitations of the EM algorithm, which has been used in previous works but is sometimes trapped in local optima depending on initial conditions. We apply the algorithms to synthetic and real-world networks to examine their performance in terms of precision and robustness of detected communities. It is found that the Gibbs samplers outperform the previous approaches especially in detecting overlapping communities. The Markovian dynamics of random walkers is crucial to robustly detect the optimal community structures.