Institute of Mathematical Science, University of Malaya, Kuala Lumpur, Malaysia.
Sci Rep. 2017 Apr 4;7:45836. doi: 10.1038/srep45836.
Community structure is an important feature of a complex network, where detection of the community structure can shed some light on the properties of such a complex network. Amongst the proposed community detection methods, the label propagation algorithm (LPA) emerges as an effective detection method due to its time efficiency. Despite this advantage in computational time, the performance of LPA is affected by randomness in the algorithm. A modified LPA, called CLPA-GNR, was proposed recently and it succeeded in handling the randomness issues in the LPA. However, it did not remove the tendency for trivial detection in networks with a weak community structure. In this paper, an improved CLPA-GNR is therefore proposed. In the new algorithm, the unassigned and assigned nodes are updated synchronously while the assigned nodes are updated asynchronously. A similarity score, based on the Sørensen-Dice index, is implemented to detect the initial communities and for breaking ties during the propagation process. Constraints are utilised during the label propagation and community merging processes. The performance of the proposed algorithm is evaluated on various benchmark and real-world networks. We find that it is able to avoid trivial detection while showing substantial improvement in the quality of detection.
社区结构是复杂网络的一个重要特征，检测社区结构可以揭示复杂网络的一些性质。在提出的社区检测方法中，标签传播算法（LPA）由于其时间效率而成为一种有效的检测方法。尽管在计算时间上具有优势，但 LPA 的性能受到算法随机性的影响。最近提出了一种改进的 LPA，称为 CLPA-GNR，它成功地解决了 LPA 中的随机性问题。然而，它并没有消除在社区结构较弱的网络中进行琐碎检测的趋势。因此，本文提出了一种改进的 CLPA-GNR。在新算法中，未分配和已分配的节点同步更新，而已分配的节点异步更新。基于 Sørensen-Dice 指数的相似度得分用于在传播过程中检测初始社区和打破平局。在标签传播和社区合并过程中利用了约束。在各种基准和真实网络上评估了所提出算法的性能。我们发现，它能够避免琐碎的检测，同时在检测质量方面有了实质性的提高。
