Modularity-Based Incremental Label Propagation Algorithm for Community Detection
Label Propagation Algorithm (LPA) is a fast community detection algorithm. However, since each node is randomly assigned a different label at first, there is serious randomness in the label updating process of LPA, resulting in great instability of detection results. This paper proposes a modularity...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-06-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/10/12/4060 |
| _version_ | 1797565508730486784 |
|---|---|
| author | Yunlong Ma Yukai Zhao Jingwei Wang Min Liu Weiming Shen Yumin Ma |
| author_facet | Yunlong Ma Yukai Zhao Jingwei Wang Min Liu Weiming Shen Yumin Ma |
| author_sort | Yunlong Ma |
| collection | DOAJ |
| description | Label Propagation Algorithm (LPA) is a fast community detection algorithm. However, since each node is randomly assigned a different label at first, there is serious randomness in the label updating process of LPA, resulting in great instability of detection results. This paper proposes a modularity-based incremental LPA (MILPA) to address this problem. Unlike LPA, MILPA first assigns all nodes the same label, and then repeatedly uses divide strategy to split locally dense connected nodes into a community and give them a new label. After that, MILPA uses modularity gain as the optimization function to fine-tune the label of nodes so as to obtain an optimal partition. The proposed MILPA has been compared with LPA and other known methods. Experimental results show that MILPA has the best and most stable performance in LFR benchmark networks and is comparable to the best algorithm in many real networks. |
| first_indexed | 2024-03-10T19:13:12Z |
| format | Article |
| id | doaj.art-954de483d448467ab7caca30080d6e02 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T19:13:12Z |
| publishDate | 2020-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-954de483d448467ab7caca30080d6e022023-11-20T03:36:15ZengMDPI AGApplied Sciences2076-34172020-06-011012406010.3390/app10124060Modularity-Based Incremental Label Propagation Algorithm for Community DetectionYunlong Ma0Yukai Zhao1Jingwei Wang2Min Liu3Weiming Shen4Yumin Ma5School of Electronic and Information Engineering, Tongji University, Shanghai 201804, ChinaSchool of Electronic and Information Engineering, Tongji University, Shanghai 201804, ChinaSchool of Electronic and Information Engineering, Tongji University, Shanghai 201804, ChinaSchool of Electronic and Information Engineering, Tongji University, Shanghai 201804, ChinaSchool of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, ChinaSchool of Electronic and Information Engineering, Tongji University, Shanghai 201804, ChinaLabel Propagation Algorithm (LPA) is a fast community detection algorithm. However, since each node is randomly assigned a different label at first, there is serious randomness in the label updating process of LPA, resulting in great instability of detection results. This paper proposes a modularity-based incremental LPA (MILPA) to address this problem. Unlike LPA, MILPA first assigns all nodes the same label, and then repeatedly uses divide strategy to split locally dense connected nodes into a community and give them a new label. After that, MILPA uses modularity gain as the optimization function to fine-tune the label of nodes so as to obtain an optimal partition. The proposed MILPA has been compared with LPA and other known methods. Experimental results show that MILPA has the best and most stable performance in LFR benchmark networks and is comparable to the best algorithm in many real networks.https://www.mdpi.com/2076-3417/10/12/4060label propagationcommunity detectionmodularity |
| spellingShingle | Yunlong Ma Yukai Zhao Jingwei Wang Min Liu Weiming Shen Yumin Ma Modularity-Based Incremental Label Propagation Algorithm for Community Detection Applied Sciences label propagation community detection modularity |
| title | Modularity-Based Incremental Label Propagation Algorithm for Community Detection |
| title_full | Modularity-Based Incremental Label Propagation Algorithm for Community Detection |
| title_fullStr | Modularity-Based Incremental Label Propagation Algorithm for Community Detection |
| title_full_unstemmed | Modularity-Based Incremental Label Propagation Algorithm for Community Detection |
| title_short | Modularity-Based Incremental Label Propagation Algorithm for Community Detection |
| title_sort | modularity based incremental label propagation algorithm for community detection |
| topic | label propagation community detection modularity |
| url | https://www.mdpi.com/2076-3417/10/12/4060 |
| work_keys_str_mv | AT yunlongma modularitybasedincrementallabelpropagationalgorithmforcommunitydetection AT yukaizhao modularitybasedincrementallabelpropagationalgorithmforcommunitydetection AT jingweiwang modularitybasedincrementallabelpropagationalgorithmforcommunitydetection AT minliu modularitybasedincrementallabelpropagationalgorithmforcommunitydetection AT weimingshen modularitybasedincrementallabelpropagationalgorithmforcommunitydetection AT yuminma modularitybasedincrementallabelpropagationalgorithmforcommunitydetection |