稳定的标签传播社团划分算法研究

快速稳定地发现复杂网络中的社团是近年来社团划分研究的热点。标签传播算法(LPA)具有接近线性的时间复杂度,能快速发现复杂网络中的社团结构,但是该算法在标签传播过程中存在不确定性和随机性,降低了划分结果的准确性和稳定性。为了解决这一问题,设计了一种稳定的标签传播社团划分算法(S-LPA)。该算法利用改进的K-Shell算法来计算节点全局影响力,并结合能反映节点局部影响力的度值以及邻居节点信息,计算节点综合影响力;在标签传播过程中,根据标签影响力更新标签;当网络中所有节点的标签不再变化或者迭代次数达到最大值时,拥有相同标签的节点划分到同一社团中。在真实网络和人工合成网络上的实验结果表明,S-LPA算法不仅具有线性时间复杂度,而且提高了社团划分的质量和稳定性。

Research on Stable Label Propagation Community Division Algorithm

The rapid and stable discovery of community in complex networks is a hot topic in the study of community division in recent years.Label propagation algorithm(LPA)has a nearly linear time complexity and can quickly discover the community structure in complex networks,but it has uncertainty and randomness in the process of label propagation,which reduces the accuracy and stability of the partition results.To solve this problem,we design a stable label propagation community division algorithm(S-LPA).The improved K-shell algorithm is used to calculate the global influence of nodes,and the comprehensive influence of nodes is calculated by combining the global influence and the degree value that can reflect the local influence of nodes with the information of neighbor nodes.Then the labels are updated according to the label influence in the process of label propagation.When the labels of all nodes in the network no longer change or the number of iterations reaches the maximum,the nodes with the same label are assigned into the same community.The experimental results on real networks and synthetic networks show that the S-LPA algorithm not only has linear time complexity,but also significantly improves the quality and stability of community division.