研究带符号随机图的矩阵集中性，用于社区检测
Matrix Concentration for Random Signed Graphs and Community Recovery in the Signed Stochastic Block Model
- 构建带符号随机图的邻接与拉普拉斯矩阵集中不等式
- 谱间隙集中在2s附近，首特征向量符号可实现弱一致社区划分
- 适用于符号网络中的社区发现与同步问题
我们研究边及其符号独立随机生成的图模型，建立了该类随机图模型下邻接矩阵和拉普拉斯矩阵的强集中不等式。随后将结果应用于符号随机块模型（signed stochastic block model）：在双社区设置中，社区内边为正号，跨社区边为负号，并以概率 $0 < s < 1/2$ 加入随机符号扰动。主要结论包括：第一，对应符号拉普拉斯矩阵的谱间隙以高概率集中在 $2s$ 附近；第二，拉普拉斯矩阵首特征向量的符号可作为平衡社区检测问题或等价的 $\pm 1$ 同步问题的弱一致估计器。实验数据验证了理论分析的有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。