# Robust Markov stability for community detection at a scale learned based on the structure

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 86 references that are in the map.
- First posted on arXiv 15 Apr 2025.

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

- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [graph2vec: Learning Distributed Representations of Graphs](https://mlsanity.com/paper/1707.05005/) (2017)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [GEMSEC: Graph Embedding with Self Clustering](https://mlsanity.com/paper/1802.03997/) (2018)
- [The ground truth about metadata and community detection in networks](https://mlsanity.com/paper/1608.05878/) (2016)
- [Structure and inference in annotated networks](https://mlsanity.com/paper/1507.04001/) (2015)
- [Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models](https://mlsanity.com/paper/1310.4378/) (2013)
- [Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks](https://mlsanity.com/paper/1502.04381/) (2015)
- [20 years of network community detection](https://mlsanity.com/paper/2208.00111/) (2022)
- [Artificial Benchmark for Community Detection (ABCD): Fast Random Graph Model with Community Structure](https://mlsanity.com/paper/2002.00843/) (2020)
- [Element-centric clustering comparison unifies overlaps and hierarchy](https://mlsanity.com/paper/1706.06136/) (2017)
- [A General Optimization Technique for High Quality Community Detection in Complex Networks](https://mlsanity.com/paper/1308.3508/) (2013)
- [Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity](https://mlsanity.com/paper/1403.5787/) (2014)
- [Community detection in networks: Structural communities versus ground truth](https://mlsanity.com/paper/1406.0146/) (2014)
- [Hierarchical Graph Clustering using Node Pair Sampling](https://mlsanity.com/paper/1806.01664/) (2018)
- [EdMot: An Edge Enhancement Approach for Motif-aware Community Detection](https://mlsanity.com/paper/1906.04560/) (2019)
- [The many facets of community detection in complex networks](https://mlsanity.com/paper/1611.07769/) (2016)
- [Multiscale dynamical embeddings of complex networks](https://mlsanity.com/paper/1804.03733/) (2018)
- [Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits](https://mlsanity.com/paper/1602.01016/) (2016)
- [Statistical inference of assortative community structures](https://mlsanity.com/paper/2006.14493/) (2020)
- [Normalized mutual information is a biased measure for classification and community detection](https://mlsanity.com/paper/2307.01282/) (2023)
- [Detecting communities using asymptotical Surprise](https://mlsanity.com/paper/1503.00445/) (2015)
- [Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity](https://mlsanity.com/paper/2209.04562/) (2022)
- [Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection](https://mlsanity.com/paper/1808.07690/) (2018)
- [Analyzing Modularity Maximization in Approximation, Heuristic, and Graph Neural Network Algorithms for Community Detection](https://mlsanity.com/paper/2310.10898/) (2023)
- [Significant Scales in Community Structure](https://mlsanity.com/paper/1306.3398/) (2013)
- [Multiscale mobility patterns and the restriction of human movement](https://mlsanity.com/paper/2201.06323/) (2022)
- [Optimality Of Community Structure In Complex Networks](https://mlsanity.com/paper/1712.05110/) (2017)
- [Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar](https://mlsanity.com/paper/2302.14698/) (2023)
- [Comparative analysis on the selection of number of clusters in community detection](https://mlsanity.com/paper/1606.07668/) (2016)

## Abstract (arXiv)

Community detection, the unsupervised task of clustering nodes of a graph, finds applications across various fields. The common approaches for community detection involve optimizing an objective function to partition the nodes into communities at a single scale of granularity. However, the single-scale approaches often fall short of producing partitions that are robust and at a suitable scale. The existing algorithm, PyGenStability, returns multiple robust partitions for a network by optimizing the multi-scale Markov stability function. However, in cases where the suitable scale is not known or assumed by the user, there is no principled method to select a single robust partition at a suitable scale from the multiple partitions that PyGenStability produces. Our proposed method combines the Markov stability framework with a pre-trained machine learning model for scale selection to obtain one robust partition at a scale that is learned based on the graph structure. This automatic scale selection involves using a gradient boosting model pre-trained on hand-crafted and embedding-based network features from a labeled dataset of 10k benchmark networks. This model was trained to predicts the scale value that maximizes the similarity of the output partition to the planted partition of the benchmark network. Combining our scale selection algorithm with the PyGenStability algorithm results in PyGenStabilityOne (PO): a hyperparameter-free multi-scale community detection algorithm that returns one robust partition at a suitable scale without the need for any assumptions, input, or tweaking from the user. We compare the performance of PO against 29 algorithms and show that it outperforms 25 other algorithms by statistically meaningful margins. Our results facilitate choosing between community detection algorithms, among which PO stands out as the accurate, robust, and hyperparameter-free method.