Study identifies three causes of algorithm instability near community detection limit

Community detection algorithms often return different partitions on repeated runs, especially near the detectability threshold. In a new arXiv paper, researchers Faruk Alpay and Baris Basaran decompose this instability into three distinct mechanisms: hard readout artifacts from the final partition cutoff, relaxation critical slowing near the phase transition, and fixed-point dispersion caused by multiple stable solutions of belief propagation. They use the symmetric sparse stochastic block model and linearized belief propagation around the Kesten-Stigum boundary (SNR=1). Key metrics include variation of information (VI) and residual-gated fixed-point VI.

Their experiments reveal that the hard VI maximum occurs at SNR 1.05–1.10, not at the theoretical threshold. Moving the polarization cutoff from 0.001 to 0.1 shifts the peak across 1.047–1.128, with a linear fit SNR_50(τ)=1+0.0086+0.522τ (R²=0.996). Long-budget residual gating isolates readout: at SNR 1.05–1.10, gated subsets have zero VI, proving instability is from the rounding step, not algorithm dynamics. At higher SNR (1.15–1.30), nearly all runs pass the gate but retain VI 1.31–1.24 bits. A high-replication audit with N=100000 finds a small plateau SNR*–1 ≈ 0.024 (90% interval [0.0227, 0.0316]), disfavoring a zero-asymptote power law. On real networks (political blogs, six SNAP graphs), a label-free Bethe-Hessian modularity margin with Chung-Lu null gate confirms the decomposition remains valid under heterogenous conditions.