论文标题
在层次随机块模型上光谱聚类的一致性
Consistency of Spectral Clustering on Hierarchical Stochastic Block Models
论文作者
论文摘要
我们在通用随机块模型下研究现实世界网络中社区的层次结构，其中连接概率在二进制树中构成。在这样的模型下，标准递归双方分数算法将网络基于非标准图拉普拉斯式的Fiedler向量分为两个社区，并重复分裂，直到停止规则表示没有进一步的社区结构。我们证明了该方法在广泛的模型参数下的强大一致性，其中包括稀疏网络，其节点度小至$ o（\ log n）$。此外，与大多数现有工作不同，我们的理论涵盖了多尺度网络，在该网络中，连接概率可能因数量级而有所不同，这包括一类重要的模型，这些模型实际上是相关但在技术上具有挑战性的。最后，我们证明了算法在合成数据和实际示例上的性能。
We study the hierarchy of communities in real-world networks under a generic stochastic block model, in which the connection probabilities are structured in a binary tree. Under such model, a standard recursive bi-partitioning algorithm is dividing the network into two communities based on the Fiedler vector of the unnormalized graph Laplacian and repeating the split until a stopping rule indicates no further community structures. We prove the strong consistency of this method under a wide range of model parameters, which include sparse networks with node degrees as small as $O(\log n)$. In addition, unlike most of existing work, our theory covers multiscale networks where the connection probabilities may differ by orders of magnitude, which comprise an important class of models that are practically relevant but technically challenging to deal with. Finally we demonstrate the performance of our algorithm on synthetic data and real-world examples.
