Affiliations: [a] King Abdullah University of Science and Technology, Thuwal, Saudi Arabia | [b] Ningbo Institute of Industrial Technology, Ningbo, Zhejiang, China | [c] Shanghai Jiao Tong University, Shanghai, China | [d] City University of Hong Kong, Hong Kong, China
Correspondence:
[*]
Corresponding author: Xiangliang Zhang, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Post Box: 2925, Kingdom of Saudi Arabia. Tel.: +966 12 808 0313; E-mail: xiangliang.zhang@kaust.edu.sa.
Abstract: Community detection in graphs is widely used in social and biological networks, and the stochastic block model is a powerful probabilistic tool for describing graphs with community structures. However, in the era of “big data”, traditional inference algorithms for such a model are increasingly limited due to their high time complexity and poor scalability. In this paper, we propose a multi-stage maximum likelihood approach to recover the latent parameters of the stochastic block model, in time linear with respect to the number of edges. We also propose a parallel algorithm based on message passing. Our algorithm can overlap communication and computation, providing speedup without compromising accuracy as the number of processors grows. For example, to process a real-world graph with about 1.3 million nodes and 10 million edges, our algorithm requires about 6 seconds on 64 cores of a contemporary commodity Linux cluster. Experiments demonstrate that the algorithm can produce high quality results on both benchmark and real-world graphs. An example of finding more meaningful communities is illustrated consequently in comparison with a popular modularity maximization algorithm.
Keywords: Stochastic block model, parallel computing, community detection
