Seminar: Recovering Small Communities in the Planted Partition Model

Speaker: Martijn Gösgens, CWI, Amsterdam, the Netherlands

Title: Recovering Small Communities in the Planted Partition Model

Abstract: We analyze community recovery in the planted partition model (PPM) 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, an algorithm based on common-neighbors, successfully recovers communities under mild assumptions on edge probabilities, with minimal restrictions on the number and sizes of communities. 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.