The stochastic block model has the overlap graph property for modularity

Shankar Bhamidi; David Gamarnik; Remco van der Hofstad; Nelly Litvak; Pawel Pralat; Fiona Skerman; Yasmin Tousinejad

The stochastic block model has the overlap graph property for modularity

Shankar Bhamidi, David Gamarnik, Remco van der Hofstad, Nelly Litvak, Pawel Pralat, Fiona Skerman, Yasmin Tousinejad

arXivarxiv/2605.10911May 11, 2026math.PRscore 0

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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.10911
curl -X POST /api/v1/records/arxiv/2605.10911/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.10911/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'