# Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animals

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 44 references that are in the map.
- First posted on arXiv 19 Sep 2025.

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

- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Frequentist Consistency of Variational Bayes](https://mlsanity.com/paper/1705.03439/) (2017)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [A Review of Stochastic Block Models and Extensions for Graph Clustering](https://mlsanity.com/paper/1903.00114/) (2019)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Statistical clustering of temporal networks through a dynamic stochastic block model](https://mlsanity.com/paper/1506.07464/) (2015)
- [Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models](https://mlsanity.com/paper/1310.4378/) (2013)
- [Theoretical and Computational Guarantees of Mean Field Variational Inference for Community Detection](https://mlsanity.com/paper/1710.11268/) (2017)
- [Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/1510.05956/) (2015)
- [Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery](https://mlsanity.com/paper/1501.05021/) (2015)
- [Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms](https://mlsanity.com/paper/1412.7335/) (2014)
- [Modeling heterogeneity in random graphs through latent space models: a selective review](https://mlsanity.com/paper/1402.4296/) (2014)
- [Multilayer stochastic block models reveal the multilayer structure of complex networks](https://mlsanity.com/paper/1411.1098/) (2014)
- [Variational Inference for Stochastic Block Models from Sampled Data](https://mlsanity.com/paper/1707.04141/) (2017)
- [Community Detection in the Stochastic Block Model by Mixed Integer Programming](https://mlsanity.com/paper/2101.12336/) (2021)
- [Learning common structures in a collection of networks. An application to food webs](https://mlsanity.com/paper/2206.00560/) (2022)
- [Exponential error rates of SDP for block models: Beyond Grothendieck's inequality](https://mlsanity.com/paper/1705.08391/) (2017)
- [Subsampling Spectral Clustering for Large-Scale Social Networks](https://mlsanity.com/paper/2110.13613/) (2021)
- [A Stochastic Block Model Approach for the Analysis of Multilevel Networks: an Application to the Sociology of Organizations](https://mlsanity.com/paper/1910.10512/) (2019)

## Abstract (arXiv)

We propose a novel family of model-free algorithms for node clustering and parameter inference in graphs generated from the Stochastic Block Model (SBM), a fundamental framework in community detection. Drawing inspiration from the Lloyd algorithm for the k-means problem, our approach extends to SBMs with general edge weight distributions. We establish the consistency of our estimator under a natural identifiability condition. Through extensive numerical experiments, we benchmark our methods against state-of-the-art techniques, demonstrating significantly faster computation times with the lower order of estimation error. Finally, we validate the practical relevance of our algorithms by applying them to empirical network data from behavioral ecology.