计算机工程 ›› 2017, Vol. 43 ›› Issue (12): 296-302.doi: 10.3969/j.issn.1000-3428.2017.12.053

• 开发研究与工程应用 • 上一篇    下一篇

基于KL散度矩阵迹的潜映射半监督社区发现

余琨 a,伍孝金 b   

  1. (荆楚理工学院 a.计算机工程学院; b.教育技术中心,湖北 荆门 448000)
  • 收稿日期:2016-11-09 出版日期:2017-12-15 发布日期:2017-12-15
  • 作者简介:余琨(1978—),男,讲师、硕士,主研方向为计算机网络工程;伍孝金,教授。
  • 基金项目:

    湖北省科技计划项目(2015CFB209)。

Potential Mapping Semi Supervised Community Discovery Based on KL Divergence Matrix Trace

YU Kun  a,WU Xiaojin  b   

  1. (a.Institute of Computer Engineering; b.Educational Technology Center,Jingchu University of Technology,Jingmen,Hubei 448000,China)
  • Received:2016-11-09 Online:2017-12-15 Published:2017-12-15

摘要:

为提高社区发现算法的计算效率和发现性能,提出一种基于潜空间映射的半监督社区发现梯度下降算法。基于潜空间表示形式构建基于潜空间映射的半监督社区发现框架,并使用KL散度对潜空间顶点相似度进行评价,获得三元组表示形式,基于矩阵迹和Frobenius范数,构建半监督社区发现梯度下降算法的优化规则,以实现目标函数局部极小值点的快速获取,提高算法在大规模社区发现中的实用价值,给出算法计算复杂度理论分析。实验结果表明,与局部社区结构发现算法、格文-纽曼算法、标签传播算法等算法相比,该算法具有更好的社区发现性能。

关键词: 潜空间, 特征映射, 半监督, 社区发现, 梯度下降

Abstract:

In order to improve the computational efficiency and performance of the community discovery algorithm,a semi supervised community discovery gradient descent algorithm based on latent space mapping is proposed.Firstly,a semi supervised community discovery framework based on latent space mapping is constructed based on the latent space representation,then the similarity of the latent space is evaluated by use of the square distance or KL divergence;Secondly,the semi supervised gradient descent optimization rules community discovery algorithm based on the norm of matrices and Frobenius is constructed to achieve the objective function of the local minimum quick access points,which improves the algorithm in large scale community found in practical value.Finally,the theoretical analysis of the computational complexity of the proposed algorithm is presented.Experimental results show that compared with the finding local community structure in networks method,Girvan-Newman networks,Label propagation and other 6 algorithms,the performance of the proposed algorithm is found to have a better performance of community discovery,and the effectiveness of the algorithm is verified.

Key words: potential space, feature mapping, semi supervised, community discovery, gradient descent

中图分类号: