融合节点分析与边分析的复杂网络社区识别算法

Community detection algorithm of hybrid node analysis and edge analysis in complex networks

针对边社区识别与节点型社区识别两类算法在识别社区过程中均存在相应缺陷,影响复杂网络社区识别质量的问题,提出融合节点分析与边分析的复杂网络社区识别(CDHNE)算法。该算法首先运用边在网络中较为稳定的特点,在算法执行初期通过边社区识别构建较为准确的社区结构;然后利用节点较为灵活的特点,在边社区形成后,对边社区的边缘进行精确识别,更准确地识别出复杂网络中的社区结构。在计算机生成网络实验中,当网络的社区结构逐渐变得模糊、重叠节点数量与重叠节点归属社区数量不断增加时,CDHNE算法的社区识别精度较传统算法平均提高10%,在重叠节点识别精度上较传统算法平均提高15%;在真实网络实验中,算法识别的社区结构紧密度较好,特别是面对拥有十几万个节点的大规模网络时,CDHNE算法高质量地完成了识别任务,EQ值达到0.412 1。实验结果表明,CDHNE算法在运行稳定性和处理大规模网络方面具有优势。

The community detection of hybrid node analysis and edge analysis in complex networks(CDHNE),a novel community detection algorithm,was proposed aiming at the problem that both edge community detection and node-based community detection algorithms had corresponding shortcomings in the process of detecting communities,which affected the quality of complex network community detection.The relatively stable characteristics of the edge in the networks were firstly used by the algorithm to construct a more accurate community structure through edge community detection at the early stage of algorithm execution.Then,after the formation of the edge communities,the flexible characteristics of the node were used to accurately detect the boundary of edge communities,so as to more accurately detect the community structure in the complex networks.In the computer-generated network experiments,when the community structure of the network gradually became fuzzy,the number of overlapping nodes and the number of communities to which the overlapping nodes belonged kept increasing.Compared to traditional algorithms,the accuracy of community detection and overlapping nodes detection were improved by an average of 10%and 15%,respectively,by the CDHNE algorithm.In the real network experiments,the tightness of the community structure detected by the CDHNE algorithm was better.Especially when facing large-scale networks with more than 100000 nodes,the detection task was completed by the CDHNE algorithm with high quality,and the EQ value reached 0.4121.The experimental results show that the CDHNE algorithm has advantages in operational stability and handling large-scale networks.