作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2020, Vol. 46 ›› Issue (6): 73-80. doi: 10.19678/j.issn.1000-3428.0054480

• 人工智能与模式识别 • 上一篇    下一篇

基于双曲空间嵌入的极小值社区划分算法

谢菁, 羿舒文, 张毅   

  1. 武汉大学 电子信息学院, 武汉 430072
  • 收稿日期:2019-04-03 修回日期:2019-06-27 发布日期:2019-07-12
  • 作者简介:谢菁(1995-),女,硕士研究生,主研方向为人工智能、复杂网络、大数据技术;羿舒文,博士研究生;张毅,硕士研究生。
  • 基金资助:
    国家自然科学基金(61702387)。

Community Division Algorithm by Minimum Based on Hyperbolic Space Embedding

XIE Jing, YI Shuwen, ZHANG Yi   

  1. Electronic Information School, Wuhan University, Wuhan 430072, China
  • Received:2019-04-03 Revised:2019-06-27 Published:2019-07-12

摘要: 真实复杂网络节点度分布服从幂律分布,而双曲空间能够完整表现这一特性。为此,提出一种基于双曲空间嵌入与极小值聚类的社区划分算法MHE。将建模后的复杂网络嵌入庞加莱圆盘模型,保留复杂网络的全局拓扑信息。根据庞加莱圆盘中的角度统计节点分布关系,得到θ曲线,并以最优模块度选择曲线极小值作为最优社区的划分依据。使用中国移动用户的真实访问数据对算法进行有效性评估,结果表明,与Louvain、SLPA和正则化谱聚类算法相比,该算法无需选择聚类中心并且计算复杂度较小,在真实复杂网络中能够获得较好的社区划分效果。

关键词: 双曲空间, 复杂网络, 嵌入, 极小值聚类, 社区划分

Abstract: The distribution of real complex network nodes obeys power laws,and the hyperbolic geometry can fully represent such characteristics.On this basis,this paper proposes a community division algorithm based on hyperbolic space embedding and minumun clustering.It embeds the modeled complex network into the Poincaré disk model while keeping the global topology information of the complex network.The distribution relationship of nodes is calculated based on the angles on the Poincaré disk to obtain the curve θ.Then the minimum of this curve is selected according to the optimal modularity as the division basis of the optimal community.This paper uses the real access data of China Mobile users to evaluate the effectiveness of the proposed algorithm,and the result shows that,compared with Louvain,SLPA and regularized spectral clustering algorithms,this algorithm does not need to choose a clustering center and its computational complexity is reduced,which has excellent community division performance in real complex networks.

Key words: hyperbolic space, complex network, embedding, minimum clustering, community division

中图分类号: