Detecting Community Structures in Networks by Label Propagation with Prediction of Percolation Transition
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 (L...
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/148686 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832565130598023168 |
|---|---|
| author | Aiping Zhang Guang Ren Yejin Lin Baozhu Jia Hui Cao Jundong Zhang Shubin Zhang |
| author_facet | Aiping Zhang Guang Ren Yejin Lin Baozhu Jia Hui Cao Jundong Zhang Shubin Zhang |
| author_sort | Aiping Zhang |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-d5239d7c8e4b4f869d6861e77dd091d9 |
| institution | Kabale University |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-d5239d7c8e4b4f869d6861e77dd091d92025-02-03T01:09:27ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/148686148686Detecting Community Structures in Networks by Label Propagation with Prediction of Percolation TransitionAiping Zhang0Guang Ren1Yejin Lin2Baozhu Jia3Hui Cao4Jundong Zhang5Shubin Zhang6College of Marine Engineering, Dalian Maritime University, Dalian 116026, ChinaCollege of Marine Engineering, Dalian Maritime University, Dalian 116026, ChinaCollege of Marine Engineering, Dalian Maritime University, Dalian 116026, ChinaCollege of Marine Engineering, Dalian Maritime University, Dalian 116026, ChinaCollege of Marine Engineering, Dalian Maritime University, Dalian 116026, ChinaCollege of Marine Engineering, Dalian Maritime University, Dalian 116026, ChinaDepartment of Architectural Engineering, Jilin Province Economic Management Cadre College, Changchun 130012, ChinaThough 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.http://dx.doi.org/10.1155/2014/148686 |
| spellingShingle | Aiping Zhang Guang Ren Yejin Lin Baozhu Jia Hui Cao Jundong Zhang Shubin Zhang Detecting Community Structures in Networks by Label Propagation with Prediction of Percolation Transition The Scientific World Journal |
| title | Detecting Community Structures in Networks by Label Propagation with Prediction of Percolation Transition |
| title_full | Detecting Community Structures in Networks by Label Propagation with Prediction of Percolation Transition |
| title_fullStr | Detecting Community Structures in Networks by Label Propagation with Prediction of Percolation Transition |
| title_full_unstemmed | Detecting Community Structures in Networks by Label Propagation with Prediction of Percolation Transition |
| title_short | Detecting Community Structures in Networks by Label Propagation with Prediction of Percolation Transition |
| title_sort | detecting community structures in networks by label propagation with prediction of percolation transition |
| url | http://dx.doi.org/10.1155/2014/148686 |
| work_keys_str_mv | AT aipingzhang detectingcommunitystructuresinnetworksbylabelpropagationwithpredictionofpercolationtransition AT guangren detectingcommunitystructuresinnetworksbylabelpropagationwithpredictionofpercolationtransition AT yejinlin detectingcommunitystructuresinnetworksbylabelpropagationwithpredictionofpercolationtransition AT baozhujia detectingcommunitystructuresinnetworksbylabelpropagationwithpredictionofpercolationtransition AT huicao detectingcommunitystructuresinnetworksbylabelpropagationwithpredictionofpercolationtransition AT jundongzhang detectingcommunitystructuresinnetworksbylabelpropagationwithpredictionofpercolationtransition AT shubinzhang detectingcommunitystructuresinnetworksbylabelpropagationwithpredictionofpercolationtransition |