Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animals
This provides faster clustering for network analysis applications like social role inference in animals, though it appears incremental as an extension of existing k-means approaches.
The authors tackled the problem of node clustering in Stochastic Block Model graphs by proposing a new family of model-free algorithms, which achieved significantly faster computation times with lower estimation error compared to state-of-the-art methods.
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.