SPECTRAL CLUSTERING AND THE HIGH-DIMENSIONAL STOCHASTIC BLOCKMODEL

SPECTRAL CLUSTERING AND THE HIGH-DIMENSIONAL STOCHASTIC BLOCKMODEL

2011, Vol. 39, No. 4, 1878–1915 | BY KARL ROHE, SOURAV CHATTERJEE AND BIN YU
The paper presents asymptotic results on the performance of spectral clustering in the high-dimensional stochastic blockmodel, where the number of clusters can grow with the number of nodes. It shows that under the stochastic blockmodel, spectral clustering can correctly identify communities, even when the number of blocks increases with the number of nodes. The key idea is that the eigenvectors of the normalized graph Laplacian converge to the eigenvectors of a "population" Laplacian, which is constructed from the true underlying structure of the network. This convergence is established under certain conditions on the expected degree of nodes and the separation of eigenvalues. The paper also provides bounds on the number of nodes that are "misclustered," showing that the number of such nodes converges to zero as the number of nodes grows. The results are applied to the stochastic blockmodel, where the matrix W is defined as ZBZ^T, with Z being a binary matrix indicating block memberships and B representing the probability of connections within and between blocks. The paper also discusses the implications of these results for graph visualization and the behavior of spectral clustering in different network models. Theoretical results are supported by simulations that demonstrate the effectiveness of spectral clustering in identifying communities in large networks.The paper presents asymptotic results on the performance of spectral clustering in the high-dimensional stochastic blockmodel, where the number of clusters can grow with the number of nodes. It shows that under the stochastic blockmodel, spectral clustering can correctly identify communities, even when the number of blocks increases with the number of nodes. The key idea is that the eigenvectors of the normalized graph Laplacian converge to the eigenvectors of a "population" Laplacian, which is constructed from the true underlying structure of the network. This convergence is established under certain conditions on the expected degree of nodes and the separation of eigenvalues. The paper also provides bounds on the number of nodes that are "misclustered," showing that the number of such nodes converges to zero as the number of nodes grows. The results are applied to the stochastic blockmodel, where the matrix W is defined as ZBZ^T, with Z being a binary matrix indicating block memberships and B representing the probability of connections within and between blocks. The paper also discusses the implications of these results for graph visualization and the behavior of spectral clustering in different network models. Theoretical results are supported by simulations that demonstrate the effectiveness of spectral clustering in identifying communities in large networks.
Reach us at info@study.space
[slides and audio] Spectral clustering and the high-dimensional stochastic blockmodel