社会网络中基于标签传播的社区发现新算法

摘要

发现高质量的社区是社会网络中的研究热点.基于标签传播的社区发现算法对社会网络中顶点的标签进行传播来发现潜在的社区.该算法为每个顶点分配一个标签,并随传播过程更新标签,顶点的标签应该和它邻居中具有最多相同标签的顶点保持一致.该算法的传播过程具有很多不确定性和随机性,并对社会网络的结构很敏感,导致最终结果包含很多小而碎的社区,且结果很不稳定,因此提出一种新的基于标签传播的LIB(Label-Influence-Based)社区发现算法.该算法首先选取一个小的顶点集作为种子集并赋予每个种子唯一的标签,再以种子集作为起点进行传播.在传播过程中,该算法综合考虑各种因素:顶点邻居中相同标签所占比例、顶点度数和边的权重等,并计算每个顶点的标签影响值来更新顶点的标签.我们在具有不同特性的数据集上进行了实验,实验结果表明LIB算法在复杂度相近的情况下明显提高了所发现社区的质量,并有很好的稳定性.