Detectability of minority communities in networks
2026-04-20 • Social and Information Networks
Social and Information Networks
AI summaryⓘ
The authors study how to find small hidden groups, called minority communities, in network data. They use a theoretical model to show there are three levels of success: sometimes you just see big groups with small ones mixed in, sometimes you can spot the small groups but not their details, and sometimes you can fully identify each small group. They find exact conditions for these levels based on mathematical properties of the network. Also, they show that a common method called spectral clustering struggles more with finding these small groups compared to a more advanced method called belief propagation.
community structureminority communitiesStochastic Block Modelphase transitionsKesten-Stigum thresholdeigenvaluesignal matrixspectral clusteringBethe Hessianbelief propagation
Authors
Jiaze Li, Leto Peel
Abstract
Community structure is prevalent in real-world networks, with empirical studies revealing heterogeneous distributions where a few dominant majority communities coexist with many smaller groups. These small-scale groups, which we term minority communities, are critical for understanding network organization but pose significant challenges for detection. Here, we investigate the detectability of minority communities from a theoretical perspective using the Stochastic Block Model. We identify three distinct phases of community detection: the detectable phase, where overall community structure is recoverable but minority communities are merged into majority groups; the distinguishable phase, where minority communities form a coherent group separate from the majority but remain unresolved internally; and the resolvable phase, where each minority community is fully distinguishable. These phases correspond to phase transitions at the Kesten-Stigum threshold and two additional thresholds determined by the eigenvalue structure of the signal matrix, which we derive explicitly. Furthermore, we demonstrate that spectral clustering with the Bethe Hessian exhibits significantly weaker detection performance for minority communities compared to belief propagation, revealing a specific limitation of spectral methods in identifying fine-grained community structure despite their capability to detect macroscopic structures down to the theoretical limit.