Bayesian Modeling of Random Walker for Community Detection in Networks

Abstract

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.

arXiv comment13 pages, 4 figures

References in corpus (18)

• Community structure in social and biological networks
• Modularity and community structure in networks
• Community detection in graphs
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Community detection algorithms: a comparative analysis
• Hierarchical Organization in Complex Networks
• Stochastic blockmodels and community structure in networks
• Link communities reveal multiscale complexity in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Community detection in networks: A user guide
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• The map equation
• An information-theoretic framework for resolving community structure in complex networks
• Line Graphs, Link Partitions and Overlapping Communities
• An efficient and principled method for detecting communities in networks
• Modeling sequences and temporal networks with dynamic community structures
• Generalized Markov stability of network communities