Lecture
LCN2 seminar September 2025
- Date
- Friday 26 September 2025
- Time
- Address
- Gorlaeus
- Room
- BM. 2.26
75th LCN2 seminar
Speaker: Martijn Gösgens (CWI Amsterdam)
Title: Recovering Small Communities in the Planted Partition Model
Abstract: We analyze community recovery in the planted partition model (PPM, a.k.a. the Stochastic Block Model) in regimes where the number of communities is arbitrarily large. We examine the three standard recovery regimes: exact recovery, almost exact recovery, and weak recovery. When communities vary in size, traditional accuracy- or alignment-based metrics become unsuitable for assessing the correctness of a predicted partition. To address this, we redefine these recovery regimes using the correlation coefficient, a more versatile metric for comparing partitions. We then demonstrate that Diamond Percolation, a simple algorithm based on overlapping triangles, successfully recovers communities under mild assumptions on the edge probabilities, and with minimal restrictions on the community sizes. As a key application, we consider the case where community sizes follow a power-law distribution, a characteristic frequently found in real-world networks. To the best of our knowledge, we provide the first recovery results for such unbalanced partitions.
Snacks and drinks will be available after the seminar at the Fusiebar.