基于矩阵计算的并行谱聚类方法

来源：计算机科学与探索杂志2015年第10期北京时间：

作者：张鲁飞，郝子宇，陈左宁

单位：数学工程与先进计算国家重点实验室，江苏 无锡 214125

摘要：针对大规模社交网络的聚类研究由来已久，谱聚类方法的可扩展性也一直是研究难点。近年来，基于代数图论发展出来的谱聚类方法，利用了特征值对应的谱结构，降低了计算复杂度且保证了聚类质量，是新的研究热点。但是在图的规模比较大和聚类个数比较多的情况下，中间运算结果会突破单机内存限制，必须将谱聚类方法并行化。为解决上述问题，提出了基于矩阵计算的并行谱聚类方法。首先利用矩阵计算领域中形成的大量的高效算法以及成熟的软件解决了特征值分解问题，将大规模的图进行降维，有效地支持原型系统的快速开发。其次使用稀疏矩阵的分片压缩存储，并用MPI（message passing interface）模型实现了矩阵-向量乘等基本算子，提高了系统的可扩展性及可靠性。最后通过实验表明提出的并行谱聚类方法可有效地解决聚类问题所面临的并发度高和平台复杂的挑战，进而支持挖掘蕴藏在海量数据资源中的有价值信息。

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