# SamBaS: Sampling-Based Stochastic Block Partitioning

arXiv: https://arxiv.org/abs/2108.06651 · HTML: https://mlsanity.com/paper/2108.06651/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 60 references that are in the map.
- First posted on arXiv 15 Aug 2021.

## Builds on (most cited first, 6 of 6)

- [Hierarchical Block Structures and High-resolution Model Selection in Large Networks](https://mlsanity.com/paper/1310.4377/) (2013)
- [Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models](https://mlsanity.com/paper/1310.4378/) (2013)
- [Nonparametric Bayesian inference of the microcanonical stochastic block model](https://mlsanity.com/paper/1610.02703/) (2016)
- [Parallel Heuristics for Scalable Community Detection](https://mlsanity.com/paper/1410.1237/) (2014)
- [Streaming Graph Challenge: Stochastic Block Partition](https://mlsanity.com/paper/1708.07883/) (2017)
- [Compressing networks with super nodes](https://mlsanity.com/paper/1706.04110/) (2017)

## Abstract (arXiv)

Community detection is a well-studied problem with applications in domains ranging from networking to bioinformatics. Due to the rapid growth in the volume of real-world data, there is growing interest in accelerating contemporary community detection algorithms. However, the more accurate and statistically robust methods tend to be hard to parallelize. One such method is stochastic block partitioning (SBP) - a community detection algorithm that works well on graphs with complex and heterogeneous community structure. In this paper, we present a sampling-based SBP (SamBaS) for accelerating SBP on sparse graphs. We characterize how various graph parameters affect the speedup and result quality of community detection with SamBaS and quantify the trade-offs therein. To evaluate SamBas on real-world web graphs without known ground-truth communities, we introduce partition quality score (PQS), an evaluation metric that outperforms modularity in terms of correlation with F1 score. Overall, SamBaS achieves speedups of up to 10X while maintaining result quality (and even improving result quality by over 150% on certain graphs, relative to F1 score).