非负矩阵MapReduce梯度下降半监督社区发现算法

NONNEGATIVE MATRIX MAPREDUCE GRADIENT DESCENT SEMI-SUPERVISED COMMUNITY DISCOVERY ALGORITHM

为提高社区发现算法性能和计算效率,提出一种非负矩阵MapReduce梯度下降半监督社区发现算法。两个矩阵间存在的Frobenius平方范数差异以及Kullback-leibleer(KL)散度,构建社区发现的矩阵迹优化规则;利用梯度下降法对社区非负矩阵进行求解,并构建基于MapReduce的并行计算方式,同时给出算法的计算复杂度分析。该方法在社区发现过程中无需全程人工参与,是一种半监督社区发现方式。通过仿真实验显示,该算法在社区发现精度、计算效率、模块度、模块密度等指标上要优于选取的对比方法,验证了算法有效性。

In order to improve the performance and computational efficiency of community discovery algorithm,a non-negative matrix MapReduce gradient descent and semi-supervised community discovery algorithm was proposed.The Frobenius square norm difference between the two matrices and the Kullback-leibleer(KL)divergence were used to construct the matrix trace optimization rule for community discovery.The gradient descent method was used to solve the community non-negative matrix,and the parallel computing method based on MapReduce was constructed.At the same time,the computational complexity analysis of the algorithm was given.In addition,the method did not need full manual participation in the process of community discovery and was a semi-supervised community discovery method.The simulation results showed that the proposed algorithm was superior to the selected comparison method in terms of community discovery accuracy,computational efficiency,module degree and module density,which verified the effectiveness of the proposed algorithm.