SPECTRAL CLUSTERING AND THE HIGH-DIMENSIONAL STOCHASTIC BLOCKMODEL
SPECTRAL CLUSTERING AND THE HIGH-DIMENSIONAL STOCHASTIC BLOCKMODEL
复制标题
DOI：
10.1214/11-aos887
复制
发表时间：
2011-08-01
影响因子：
4.5
通讯作者：
Yu, Bin
中科院分区：
文献类型：
--
作者：
Rohe, Karl;Chatterjee, Sourav;Yu, Bin
网络或图形可以轻松表示一组不同的数据源，这些数据源的特征是交互单元或参与者。代表人们相互交流的社交网络就是一个例子。高度互联的参与者组成的社区或集群构成了多个经验网络结构的基本特征。谱聚类是发现这些社区的流行且计算上可行的方法。随机块模型 [Social Networks 5 (1983) 109-137] 是一种具有明确定义的社区的社交网络模型；每个节点都是一个社区的成员。对于从随机块模型生成的网络，我们通过谱聚类来限制“错误聚类”的节点数量。本文的渐近结果是第一个允许模型中簇的数量随着节点数量而增长的聚类结果，因此被称为高维。为了研究随机块模型下的谱聚类，我们首先证明在更一般的潜在空间模型下，归一化图拉普拉斯的特征向量渐近收敛于归一化“群体”的特征向量 图拉普拉斯算子。除了对谱聚类的影响之外，这还提供了对图形可视化技术的深入了解。我们研究随机矩阵特征向量的方法是原创的。
Networks or graphs can easily represent a diverse set of data sources that are characterized by interacting units or actors. Social networks, representing people who communicate with each other, are one example. Communities or clusters of highly connected actors form an essential feature in the structure of several empirical networks. Spectral clustering is a popular and computationally feasible method to discover these communities.The stochastic blockmodel [Social Networks 5 (1983) 109-137] is a social network model with well-defined communities; each node is a member of one community. For a network generated from the Stochastic Blockmodel, we bound the number of nodes "misclustered" by spectral clustering. The asymptotic results in this paper are the first clustering results that allow the number of clusters in the model to grow with the number of nodes, hence the name high-dimensional.In order to study spectral clustering under the stochastic blockmodel, we first show that under the more general latent space model, the eigenvectors of the normalized graph Laplacian asymptotically converge to the eigenvectors of a "population" normalized graph Laplacian. Aside from the implication for spectral clustering, this provides insight into a graph visualization technique. Our method of studying the eigenvectors of random matrices is original.