The stochastic block model has the overlap graph property for modularity
2026-05-11 • Computational Complexity
Computational ComplexityData Structures and Algorithms
AI summaryⓘ
The authors study a popular way to find communities in networks called modularity-based algorithms, applied to a specific network model called the Stochastic Block Model (SBM). They show that the modularity score has a complex landscape known as the overlap gap property (OGP), which means certain local algorithms get stuck and can't efficiently find the true communities. This also suggests slow behavior for some related methods like Markov Chains. Additionally, the authors extend previous work to show that nearly optimal partitions by modularity are very close to the true community division in the SBM.
Stochastic Block ModelModularityOverlap Gap PropertyLocal AlgorithmsCommunity DetectionMarkov ChainPlanted PartitionClusteringAlgorithmic LimitsGraph Theory
Authors
Shankar Bhamidi, David Gamarnik, Remco van der Hofstad, Nelly Litvak, Pawel Pralat, Fiona Skerman, Yasmin Tousinejad
Abstract
The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to coincide with conjectured algorithmic limits in problems with statistical computational gap. We consider the Stochastic Block Model (SBM), where the graph has a planted partition with $k$ equal-size blocks which form the `communities', and where, for parameters $p>q$, vertices within the same community connect with probability $p$, while vertices in different communities connect with probability $q$, independently across pairs of vertices. Modularity--based clustering algorithms have become ubiquitous in applications. This article studies theoretical limits of local algorithms based on the modularity score on the SBM. We establish that modularity exhibits OGP on the SBM. This rules out a class of local algorithms based on modularity for recovery in the SBM, and shows slow mixing time for a related Markov Chain. Theoretically this is one of the few instances where OGP has been established for a `planted' model, as most such analyses to date consider the `null' model. As part of our analysis, we extend a result by Bickel and Chen 2009, who established that with high probability, the modularity optimal partition of SBM is $o(n)$ local moves away from the planted partition, where $n$ is the graph size. We show that, with high probability, any partition with modularity score sufficiently near the optimal value is close to the planted partition.