论文标题
稀疏和光滑：改进的保证在动态随机块模型中的光谱聚类
Sparse and Smooth: improved guarantees for Spectral Clustering in the Dynamic Stochastic Block Model
论文作者
论文摘要
在本文中，我们分析了动态随机块模型（DSBM）中光谱聚类（SC）算法的经典变体。现有结果表明，在相对稀疏的情况下，预期程度随节点数量而对数增长，在静态情况下保证可以扩展到动态情况，并且当DSBM在时间上足够光滑时，也可以提高误差界限，即，两个时间步长之间的社区不会改变太大。我们通过在DSBM的稀疏度和平滑度之间建立新的联系来改善这些结果：DSBM越规律，它越稀疏，同时仍然可以保证稳定的恢复。特别是，平滑度的温和条件可以使稀疏的外壳以有界程度处理。我们还将这些保证金扩展到了归一化的拉普拉斯式，作为我们分析的副产品，我们获得了具有独立Bernoulli条目的归一化矩阵的最佳光谱浓度。
In this paper, we analyse classical variants of the Spectral Clustering (SC) algorithm in the Dynamic Stochastic Block Model (DSBM). Existing results show that, in the relatively sparse case where the expected degree grows logarithmically with the number of nodes, guarantees in the static case can be extended to the dynamic case and yield improved error bounds when the DSBM is sufficiently smooth in time, that is, the communities do not change too much between two time steps. We improve over these results by drawing a new link between the sparsity and the smoothness of the DSBM: the more regular the DSBM is, the more sparse it can be, while still guaranteeing consistent recovery. In particular, a mild condition on the smoothness allows to treat the sparse case with bounded degree. We also extend these guarantees to the normalized Laplacian, and as a by-product of our analysis, we obtain to our knowledge the best spectral concentration bound available for the normalized Laplacian of matrices with independent Bernoulli entries.
