A scalable community detection algorithm for large graphs using stochastic block models

C. Peng, Z. Z. Zhang, K.-C. Wong, X. Zhang, and D. Keyes
International Joint Conference on Artificial Intelligence, IEEE, pp. 2090-2096, (2015)

A scalable community detection algorithm for large graphs using stochastic block models

Keywords

Stochastic block model

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.

Code

-

Sources

PDF

See all publications 2015