Unraveling the Detectability of Stochastic Block Model With Overlapping Communities

The detectability and distinguishability analysis for stochastic block model (SBM) have been very important topics in community detection. Detectability refers to the ability for weak recovery of communities in a graph, and distinguishability refers to the ability to distinguish the generating model of a given network from SBM and Erdos-Renyi (E-R) model. Numerous prior arts have focused on networks with non-overlapping communities. It has been proved that the threshold for detectability and distinguishability is equal to the Kesten-Stigum (K-S) threshold for networks with two communities and below the K-S threshold for networks with more than three communities. In this work, we revisit the detectability and distinguishability problems of community detection considering the overlapping characteristics. Specifically, given a graph generated from symmetric stochastic block model (SSBM) with overlapping communities, we are interested in whether we can achieve weak recovery on it and whether it is possible to distinguish it from a graph generated from E-R model. We studied these two problems for both 2-community case and q-community case, then the corresponding information-theoretic thresholds for the detectability of communities are derived. These results imply that as the strength of overlap increases, the thresholds become higher, thus community detection becomes harder. Therefore, we can conclude that the overlapping characteristics will weaken the detectability and distinguiability of communities in the network.