基于速度优化和社区偏向的标签传播算法

A Label Propagation Algorithm Based on Speed Optimization and Community Preference

【目的】减少标签传播算法的无效更新、解决算法准确率低的问题。【方法】引入节点信息列表以指导更新过程,避免不必要的更新,从而加快执行速度;采取基于节点对社区偏向程度的更新规则,提高社区划分的准确率。【结果】实验结果表明,相比标签传播算法和两种较好的改进算法,本文提出的基于速度优化和社区偏向的标签传播算法在较大规模网络上的迭代次数减少了几十倍,在真实网络数据集的模块度相对较高,在LFR基准网络数据集的归一化互信息值和F-measure值分别有明显提高。【局限】更新顺序具有随机性,需进一步研究。【结论】本文算法在提高执行速度的基础上,提高了社区发现的准确率。

[Objective] This paper aims to reduce the unnecessary updates and improve the accuracy of Label Propagation Algorithm. [Methods] First, we used the node information list to direct the update process and increase the execution speed. Then, we proposed new updating rules based on the node preference to improve the accuracy of community detection. [Results] Compared with the classic label propagation algorithm and two improved algorithms, the proposed one significantly reduced the number of iterations on large-scale social networks, as well as improved the value of Normalized Mutual Information and F-measure of LFR benchmark network. [Limitations] The new algorithm＇s updating sequence is random, which needs to be investigated in further studies. [Conclusions] The SOCP_LPA improves the accuracy of community detection and the processing speed.