关键词: 矩阵计算, 谱聚类, 特征值分解, 社交网络

Abstract: Finding community structure of large-scale graph is always an important problem and difficult to researchers. Spectral clustering algorithm based on algebraic graph theory is an emerging algorithm which uses spectrum structure to reduce computation complexity and ensure the clustering quality. But it can hardly scale because the eigenvalue decomposition of the Laplacian matrix is memory-consumptive and difficult to explore its parallelism. To overcome the problems, this paper proposes a parallel spectral clustering algorithm based on matrix computation. Firstly, this paper uses state-of-art matrix computation tools to solve the problem of eigenvalue decomposition, and reduces the dimension of large-scale graph to support the rapid development of prototype system. Secondly, this paper develops some basic operators such as matrix-vector multiplication with the blocked compression and storage of sparse matrix and MPI (message passing interface) programming model, and improves the scalability and reliability of the system. Finally, the experimental results show that the proposed parallel spectral clustering algorithm can effectively solve the problems of concurrency and complexity, then mine the valuable information in huge amounts of data resources.

Key words: matrix computation, spectral clustering, eigenvalue decomposition, social network