Matrix Concentration for Random Signed Graphs and Community Recovery in the Signed Stochastic Block Model
This work addresses community detection in signed networks, which is incremental by extending concentration results to signed graphs and applying them to a specific model with theoretical guarantees.
The paper tackles the problem of community detection in signed graphs by establishing concentration inequalities for adjacency and Laplacian matrices in random signed graph models, and applies these to the signed stochastic block model, showing that the spectral gap concentrates near 2s and the first eigenvector provides a weakly consistent estimator for community recovery.
We consider graphs where edges and their signs are added independently at random from among all pairs of nodes. We establish strong concentration inequalities for adjacency and Laplacian matrices obtained from this family of random graph models. Then, we apply our results to study graphs sampled from the signed stochastic block model. Namely, we take a two-community setting where edges within the communities have positive signs and edges between the communities have negative signs and apply a random sign perturbation with probability $0< s <1/2$. In this setting, our findings include: first, the spectral gap of the corresponding signed Laplacian matrix concentrates near $2s$ with high probability; and second, the sign of the first eigenvector of the Laplacian matrix defines a weakly consistent estimator for the balanced community detection problem, or equivalently, the $\pm 1$ synchronization problem. We supplement our theoretical contributions with experimental data obtained from the models under consideration.