基于节点关联度的标签传递社团发现算法

COMMUNITY DISCOVERY ALGORITHM USING LABEL PROPAGATION BASED ON NODES CORRELATION

现有快速社团发现算法存在划分质量不高和标签传递划分结果不稳定问题。针对这些问题,提出一种基于节点关联度的标签传递社团发现算法(ELPA)。以邻居节点间的关联度为约束更新网络节点的标签,实现对社团初始划分;以模块度增量最大化对社团进行合并,使得每次合并后的社团模块度最大。为验证ELPA的有效性,基于计算机生成网络和真实网络环境与经典算法FN、LPA进行对比实验。结果表明,ELPA算法不仅弥补了LPA算法结果不稳定的缺陷,而且提高了社团划分精度和有效性。

Existing fast community discovery algorithm has the problems of low division quality and unstable label propagation division result. To solve the problem, this paper proposes a community discovery algorithm using label propagation （ ELPA）, which is based on nodes correlation. The algorithm uses the correlation between neighbouring nodes as the constraint to update the labels of network nodes so as to achieve initial division of community; it merges the communities by maximising the increment of module-degree, after each combination it makes the module degree of community be the largest. To verify the effectiveness of ELPA, based on the computer-generated network and real network environment we carry out the comparative experiment of ELPA with classic algorithms of FN, LPA. Results show that ELPA not only makes up the defect of the LPA in unstable results, but also improves the precision and effectiveness of community division.