TL;DR该研究提出了基于稀疏线性系统和两阶段阈值和压缩感知算法的社区检测问题解决方案，在较小计算量内有效地在 Stochastic Block Model 模型的随机图数据以及真实数据集上实现图的划分。
Abstract
The community detection problem for graphs asks one to partition the n
vertices V of a graph G into k communities, or clusters, such that there are
many intracluster edges and few intercluster edges. Of course this is
equivalent to finding a permutation matrix P such that, if A denotes
在高斯图模型的框架下，我们引入一种新颖的分解方法，将基础图结构分解为稀疏部分和低秩对角块（非重叠社区），并提出一个三阶段估计过程以及快速高效的算法用于识别稀疏结构和社区。通过两种建模方式展示了这种分解的重要性，并在理论层面上建立了局部可辨识性的条件，并通过构造一种有效的范数将传统的不可表示性条件拓展为自适应形式，确保自适应 l1 惩罚估计器在第二阶段的模型选择的一致性。此外，我们还为第三阶段的 K 均值聚类过程提供了聚类误差界限。通过大量的数值实验，证明了所提方法在估计图结构方面的优越性。此外，我们还将该方法应用于股票回报数据，展示了其准确识别非重叠社区结构的能力。