2026-09-08T01:21:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26417 2026-09-05T19:42:54Z ddc:004 open_access

The Stochastic Block Model Has the Overlap Graph Property for Modularity Bhamidi, Shankar Gamarnik, David van der Hofstad, Remco Litvak, Nelly Prałat, Paweł Skerman, Fiona Tousinejad, Yasmin community detection average-case complexity overlap gap property modularity Louvain stochastic block model 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shankar Bhamidi and David Gamarnik and Remco van der Hofstad and Nelly Litvak and Paweł Prałat and Fiona Skerman and Yasmin Tousinejad 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.28 urn:nbn:de:0030-drops-264177 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.28 eng https://creativecommons.org/licenses/by/4.0/legalcode