Detecting Community Structures in Networks by Label Propagation with Prediction of Percolation Transition
Joint Authors
Zhang, Aiping
Ren, Guang
Lin, Yejin
Jia, Baozhu
Cao, Hui
Zhang, Jundong
Zhang, Shubin
Source
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-14, 14 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-07-07
Country of Publication
Egypt
No. of Pages
14
Main Subjects
Medicine
Information Technology and Computer Science
Abstract EN
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.
American Psychological Association (APA)
Zhang, Aiping& Ren, Guang& Lin, Yejin& Jia, Baozhu& Cao, Hui& Zhang, Jundong…[et al.]. 2014. Detecting Community Structures in Networks by Label Propagation with Prediction of Percolation Transition. The Scientific World Journal،Vol. 2014, no. 2014, pp.1-14.
https://search.emarefa.net/detail/BIM-1048480
Modern Language Association (MLA)
Zhang, Aiping…[et al.]. Detecting Community Structures in Networks by Label Propagation with Prediction of Percolation Transition. The Scientific World Journal No. 2014 (2014), pp.1-14.
https://search.emarefa.net/detail/BIM-1048480
American Medical Association (AMA)
Zhang, Aiping& Ren, Guang& Lin, Yejin& Jia, Baozhu& Cao, Hui& Zhang, Jundong…[et al.]. Detecting Community Structures in Networks by Label Propagation with Prediction of Percolation Transition. The Scientific World Journal. 2014. Vol. 2014, no. 2014, pp.1-14.
https://search.emarefa.net/detail/BIM-1048480
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1048480