---
title: "A Scalable Community Detection Algorithm for Large Graphs Using Stochastic Block Models"
authors:
  - "Chengbin Peng"
  - "Zhihua Zhang"
  - "Ka-Chun Wong"
  - "Xiangliang Zhang"
  - "David E. Keyes"
doi: ""
url: "https://ijcai.org/proceedings/2015/296"
pdf: "https://ijcai.org/proceedings/2015/0296.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "2090-2095"
track: "Main Track"
keywords:
---

# A Scalable Community Detection Algorithm for Large Graphs Using Stochastic Block Models

Chengbin Peng, Zhihua Zhang, Ka-Chun Wong, Xiangliang Zhang, David E. Keyes

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 2090-2095.

## 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.