Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models

Tiago P. Peixoto*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract (may include machine translation)

We present an efficient algorithm for the inference of stochastic block models in large networks. The algorithm can be used as an optimized Markov chain Monte Carlo (MCMC) method, with a fast mixing time and a much reduced susceptibility to getting trapped in metastable states, or as a greedy agglomerative heuristic, with an almost linear O(Nln2N) complexity, where N is the number of nodes in the network, independent of the number of blocks being inferred. We show that the heuristic is capable of delivering results which are indistinguishable from the more exact and numerically expensive MCMC method in many artificial and empirical networks, despite being much faster. The method is entirely unbiased towards any specific mixing pattern, and in particular it does not favor assortative community structures.

Original languageEnglish
Article number012804
JournalPhysical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics
Volume89
Issue number1
DOIs
StatePublished - 13 Jan 2014
Externally publishedYes

Fingerprint

Dive into the research topics of 'Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models'. Together they form a unique fingerprint.

Cite this