title: Detecting community structures in networks by label propagation with prediction of percolation transition.
abstract: Though label propagation algorithm (LPA) is one of the fastest algorithms for community detection in complex networks, the problem of trivial solutions frequently occurring in the algorithm affects its performance. We propose a label propagation algorithm with prediction of percolation transition (LPAp). After analyzing the reason for multiple solutions of LPA, by transforming the process of community detection into network construction process, a trivial solution in label propagation is considered as a giant component in the percolation transition. We add a prediction process of percolation transition in label propagation to delay the occurrence of trivial solutions, which makes small communities easier to be found. We also give an incomplete update condition which considers both neighbor purity and the contribution of small degree vertices to community detection to reduce the computation time of LPAp. Numerical tests are conducted. Experimental results on synthetic networks and real-world networks show that the LPAp is more accurate, more sensitive to small community, and has the ability to identify a single community structure. Moreover, LPAp with the incomplete update process can use less computation time than LPA, nearly without modularity loss.
authors.affiliation: College of Marine Engineering, Dalian Maritime University, Dalian 116026, China.
authors.forename: Aiping
authors.initials: A
authors.lastname: Zhang
authors.affiliation: College of Marine Engineering, Dalian Maritime University, Dalian 116026, China.
authors.forename: Guang
authors.identifier: 0000-0003-3645-1471
authors.initials: G
authors.lastname: Ren
authors.affiliation: College of Marine Engineering, Dalian Maritime University, Dalian 116026, China.
authors.forename: Yejin
authors.initials: Y
authors.lastname: Lin
authors.affiliation: College of Marine Engineering, Dalian Maritime University, Dalian 116026, China.
authors.forename: Baozhu
authors.initials: B
authors.lastname: Jia
authors.affiliation: College of Marine Engineering, Dalian Maritime University, Dalian 116026, China.
authors.forename: Hui
authors.initials: H
authors.lastname: Cao
authors.affiliation: College of Marine Engineering, Dalian Maritime University, Dalian 116026, China.
authors.forename: Jundong
authors.initials: J
authors.lastname: Zhang
authors.affiliation: Department of Architectural Engineering, Jilin Province Economic Management Cadre College, Changchun 130012, China.
authors.forename: Shubin
authors.initials: S
authors.lastname: Zhang
mesh_terms: D000465:Algorithms; D016571:Neural Networks, Computer
references.citation: Proc Natl Acad Sci U S A. 2002 Jun 11;99(12):7821-6
references.pmid: 12060727
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Dec;70(6 Pt 2):066111
references.pmid: 15697438
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2005 Aug;72(2 Pt 2):027104
references.pmid: 16196754
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Feb;69(2 Pt 2):026113
references.pmid: 14995526
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Jun;79(6 Pt 2):066107
references.pmid: 19658564
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2006 Jul;74(1 Pt 2):016110
references.pmid: 16907154
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Apr;77(4 Pt 2):046112
references.pmid: 18517695
references.citation: Nature. 2001 May 3;411(6833):41-2
references.pmid: 11333967
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Nov;70(5 Pt 2):056131
references.pmid: 15600716
references.citation: Phys Rev Lett. 2001 Jun 18;86(25):5835-8
references.pmid: 11415370
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2003 Dec;68(6 Pt 2):065103
references.pmid: 14754250
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Jun;69(6 Pt 2):066133
references.pmid: 15244693
references.citation: Science. 2009 Mar 13;323(5920):1453-5
references.pmid: 19286548
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2007 Sep;76(3 Pt 2):036106
references.pmid: 17930305
references.citation: ScientificWorldJournal. 2014 Feb 04;2014:549398
references.pmid: 24688404
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2006 Sep;74(3 Pt 2):036104
references.pmid: 17025705
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Aug;80(2 Pt 2):026129
references.pmid: 19792222
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Oct;78(4 Pt 2):046110
references.pmid: 18999496
references.citation: Proc Natl Acad Sci U S A. 2006 Jun 6;103(23):8577-82
references.pmid: 16723398
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2010 Apr;81(4 Pt 2):046106
references.pmid: 20481785
references.citation: Proc Natl Acad Sci U S A. 2007 Jan 2;104(1):36-41
references.pmid: 17190818
references.citation: Proc Biol Sci. 2003 Nov 7;270 Suppl 2:S186-8
references.pmid: 14667378
references.citation: ScientificWorldJournal. 2013 Dec 22;2013:464107
references.pmid: 24453857