一种并行社区发现方法和装置

摘要

本发明公开了一种并行社区发现方法和装置，涉及数据挖掘领域。本发明公开的方法包括：读入原始社交网络数据，将其转换成邻接矩阵的形式并存储在HDFS文件系统上；在配置有Hadoop环境的计算集群上计算存储在HDFS上的图的邻接矩阵的度矩阵D和Laplacian矩阵；对Laplacian矩阵进行特征值和特征向量的并行Lanczos数值求解，得到矩阵前K个最大特征值对应的特征向量，并构造出特征向量矩阵进行归一化，得到规范化的特征向量矩阵并提取特征，将每行看作一个点，采用聚类方法将其聚类成K类；根据点的对应关系，将原来的社区中的个体等价地划为K类，完成社区的分类。本发明还公开了一种社区发现装置。本申请技术方案对于大规模数据具有良好的适应性。

主权项

一种社区发现方法，其特征在于，该方法包括：读入原始社交网络数据，将其转换成邻接矩阵的形式并存储在HDFS文件系统上；在配置有Hadoop环境的计算集群上计算存储在HDFS上的图的邻接矩阵的度矩阵D和Laplacian矩阵L_sym＝I‑D^‑1/2SD^‑1/2；对所述Laplacian矩阵采用Haoop框架进行特征值和特征向量的并行Lanczos数值求解，得到矩阵前K个最大特征值I＝λ₁≥λ₂≥…≥λ_K，其对应的特征向量表示成V¹，V²，…，V^K；将所述特征向量V¹，V²，…，V^K排成一行，构造出特征向量矩阵并对其进行归一化，得到规范化的特征向量矩阵$Y=U_{\mathrm{ij}}/{\left({\Sigma }_i{U}_{\mathrm{ij}}^2\right)}^{1/2};$对规范化的特征向量矩阵Y进行特征提取，将每行看作一个点，代表原来的抽象个体的欧式空间映射，采用简单基于距离的聚类方法将其聚类成K类；根据点的对应关系，将原来的社区中的个体等价地划为K类，完成社区的分类。