The most commonly used method to tackle the graph partitioning problem in practice is the multilevel metaheuristic. In this paper we introduce size‐constrained label propagation (SCLaP) and show how it can be used to instantiate both the coarsening phase and the refinement phase of multilevel graph partitioning. We mainly target networks with highly irregular and hierarchically clustered structure (but other network types can be partitioned as well). Additionally, we augment the basic algorithm with several extensions to further improve its speed and/or solution quality. Depending on the configuration of the resulting partitioner using SCLaP, we are able to compute high‐quality partitions outperforming all competitors, or instead, to compute similarly good partitions as the best competitor in terms of quality, hMetis, while being an order of magnitude faster. Our fastest configuration partitions the largest real‐world graph in our study (it has 3.3 billion edges) with sequential code in about ten minutes while cutting less than half of the edges than the fastest competitor, kMetis.
