Enhanced Markov clustering with reverse k-nearest neighbors, min–max expansion, and adaptive local pruning

Abstract

Markov clustering (MCL) is a widely used clustering algorithm for graph data partitioning. However, it suffers from three key limitations: the lack of theoretical investigation into the reliability of graph construction methods for MCL, difficulty in parameter expansion tuning, and the reliance on global pruning strategies that ignore local structural variations. To address these issues, we propose enhanced Markov clustering (EMC), which introduces three innovations: (1) A theoretically supported RkNN-based graph construction, which we demonstrate to be consistent with MCL’s inflow, thereby providing a principled basis for identifying natural cluster centers; (2) A minimal-but-maximal expansion strategy that adaptively determines the optimal expansion power, preventing over-merging and fragmentation; and (3) Local adaptive pruning, a column-wise pruning mechanism that removes weak inter-cluster edges more effectively than global pruning while preserving local structure. Experiments on benchmark datasets show that EMC generally outperforms existing MCL variants and is competitive with other effective clustering algorithms on tabular data while reducing hyperparameter tuning complexity.