A novel algorithm for overlapping community detection based on label propagation in complex networks

被引：0
作者：
Deng K. [1 ,2 ]
Li W.-P. [1 ]
Chen L. [1 ]
Liu X.-Y. [1 ]
机构：
[1] College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing
[2] School of Computing, Media and the Arts, Teesside University, Middlesbrough
来源：
Kongzhi yu Juece/Control and Decision | 2020年 / 35卷 / 11期
关键词：
Community detection; Community structures; Complex networks; Label propagation; Overlapping nodes;
D O I：
10.13195/j.kzyjc.2019.0176
中图分类号：
学科分类号：
摘要：
Existing label propagation based overlapping community detection algorithms are limited, in terms of lacking accuracy, exhibiting high randomness, etc., when applied to complex networks.To overcome these limitations, this paper proposes a novel algorithm for overlapping community detection based on label propagation (NOCDLP).In the algorithm, we first search for a number of complete subgraphs centered on nodes with higher degrees in a network and initiate the label propagation starting from these subgraphs.Then, a function to specify the bonds between nodes and communities is generated, by analyzing the strength of connections between nodes and communities, and the internal closeness of a particular community after a certain node is adopted.By introducing this function, the accuracy of community detection is increased significantly.Subsequently, in the process of label propagation, NOCDLP sets control marks to alleviate the high randomness in community detection.Finally, the algorithm cleans up overlapping nodes to improve the accuracy of the overlapping community structures generated.This algorithm is tested in both artificial and real-world networks. The experimental results show that the proposed algorithm is practical and more efficient in comparison with multiple classical algorithms. © 2020, Editorial Office of Control and Decision. All right reserved.
引用
收藏
页码：2733 / 2742
页数：9
相关论文
共 20 条
  • [1] Newman M E J., Fast algorithm for detecting community structure in networks, Physical Review E, 69, 6, (2004)
  • [2] Raghavan U N, Albert R, Kumara S., Near linear time algorithm to detect community structures in large-scale networks, Physical Review E, 76, 3, (2007)
  • [3] Palla G, Derenyi I, Farkas I, Et al., Uncovering the overlapping community structure of complex networks in nature and society, Nature, 435, 7043, pp. 814-818, (2005)
  • [4] Shen H W, Cheng X Q, Guo J F., Quantifying and identifying the overlapping community structure in networks, Journal of Statistical Mechanics Theory and Experiment, 53, 7, (2009)
  • [5] Lancichinetti A, Fortunato S, Kertesz J., Detecting the overlapping and hierarchical community structure in complex networks, New Journal of Physics, 11, 3, (2009)
  • [6] Ahn Y Y, Bagrow J P, Lehmann S., Link communities reveal multiscale complexity in networks, Nature, 466, 7307, pp. 761-764, (2010)
  • [7] Liu W, Suzumura T, Ji H., Finding overlapping communities in multilayer networks, Plos One, 13, 4, (2018)
  • [8] Mondragon R J, Iacovacci J, Bianconi G., Multilink communities of multiplex networks, Plos One, 13, 3, (2018)
  • [9] Gregory S., Finding overlapping communities in networks by label propagation, New Journal of Physics, 12, 10, (2010)
  • [10] Xie J R, Szymanski B K, Liu X., Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process, Proceedings of IEEE ICDM Workshop on DMCCI, pp. 344-349, (2011)
12