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

Community Division Algorithm by Minimum Based on Hyperbolic Space Embedding

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

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.