Overlapping Community Detection Based on Membership Degree Propagation
A community in a complex network refers to a group of nodes that are densely connected internally but with only sparse connections to the outside. Overlapping community structures are ubiquitous in real-world networks, where each node belongs to at least one community. Therefore, overlapping communi...
| প্রধান লেখক: | , , , , |
|---|---|
| বিন্যাস: | প্রবন্ধ |
| ভাষা: | English |
| প্রকাশিত: |
MDPI AG
2020-12-01
|
| মালা: | Entropy |
| বিষয়গুলি: | |
| অনলাইন ব্যবহার করুন: | https://www.mdpi.com/1099-4300/23/1/15 |
| _version_ | 1827699322366459904 |
|---|---|
| author | Rui Gao Shoufeng Li Xiaohu Shi Yanchun Liang Dong Xu |
| author_facet | Rui Gao Shoufeng Li Xiaohu Shi Yanchun Liang Dong Xu |
| author_sort | Rui Gao |
| collection | DOAJ |
| description | A community in a complex network refers to a group of nodes that are densely connected internally but with only sparse connections to the outside. Overlapping community structures are ubiquitous in real-world networks, where each node belongs to at least one community. Therefore, overlapping community detection is an important topic in complex network research. This paper proposes an overlapping community detection algorithm based on membership degree propagation that is driven by both global and local information of the node community. In the method, we introduce a concept of membership degree, which not only stores the label information, but also the degrees of the node belonging to the labels. Then the conventional label propagation process could be extended to membership degree propagation, with the results mapped directly to the overlapping community division. Therefore, it obtains the partition result and overlapping node identification simultaneously and greatly reduces the computational time. The proposed algorithm was applied to a synthetic Lancichinetti–Fortunato–Radicchi (LFR) dataset and nine real-world datasets and compared with other up-to-date algorithms. The experimental results show that our proposed algorithm is effective and outperforms the comparison methods on most datasets. Our proposed method significantly improved the accuracy and speed of the overlapping node prediction. It can also substantially alleviate the computational complexity of community structure detection in general. |
| first_indexed | 2024-03-10T13:48:14Z |
| format | Article |
| id | doaj.art-35e745bc67b747cbb0199201281d1405 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-10T13:48:14Z |
| publishDate | 2020-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-35e745bc67b747cbb0199201281d14052023-11-21T02:26:07ZengMDPI AGEntropy1099-43002020-12-012311510.3390/e23010015Overlapping Community Detection Based on Membership Degree PropagationRui Gao0Shoufeng Li1Xiaohu Shi2Yanchun Liang3Dong Xu4Key Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education, College of Computer Science and Technology, Jilin University, 2699 Qianjin Street, Changchun 130012, ChinaKey Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education, College of Computer Science and Technology, Jilin University, 2699 Qianjin Street, Changchun 130012, ChinaKey Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education, College of Computer Science and Technology, Jilin University, 2699 Qianjin Street, Changchun 130012, ChinaKey Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education, College of Computer Science and Technology, Jilin University, 2699 Qianjin Street, Changchun 130012, ChinaKey Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education, College of Computer Science and Technology, Jilin University, 2699 Qianjin Street, Changchun 130012, ChinaA community in a complex network refers to a group of nodes that are densely connected internally but with only sparse connections to the outside. Overlapping community structures are ubiquitous in real-world networks, where each node belongs to at least one community. Therefore, overlapping community detection is an important topic in complex network research. This paper proposes an overlapping community detection algorithm based on membership degree propagation that is driven by both global and local information of the node community. In the method, we introduce a concept of membership degree, which not only stores the label information, but also the degrees of the node belonging to the labels. Then the conventional label propagation process could be extended to membership degree propagation, with the results mapped directly to the overlapping community division. Therefore, it obtains the partition result and overlapping node identification simultaneously and greatly reduces the computational time. The proposed algorithm was applied to a synthetic Lancichinetti–Fortunato–Radicchi (LFR) dataset and nine real-world datasets and compared with other up-to-date algorithms. The experimental results show that our proposed algorithm is effective and outperforms the comparison methods on most datasets. Our proposed method significantly improved the accuracy and speed of the overlapping node prediction. It can also substantially alleviate the computational complexity of community structure detection in general.https://www.mdpi.com/1099-4300/23/1/15complex networksocial networkoverlapping community detectionlabel propagationmembership degreeclustering |
| spellingShingle | Rui Gao Shoufeng Li Xiaohu Shi Yanchun Liang Dong Xu Overlapping Community Detection Based on Membership Degree Propagation Entropy complex network social network overlapping community detection label propagation membership degree clustering |
| title | Overlapping Community Detection Based on Membership Degree Propagation |
| title_full | Overlapping Community Detection Based on Membership Degree Propagation |
| title_fullStr | Overlapping Community Detection Based on Membership Degree Propagation |
| title_full_unstemmed | Overlapping Community Detection Based on Membership Degree Propagation |
| title_short | Overlapping Community Detection Based on Membership Degree Propagation |
| title_sort | overlapping community detection based on membership degree propagation |
| topic | complex network social network overlapping community detection label propagation membership degree clustering |
| url | https://www.mdpi.com/1099-4300/23/1/15 |
| work_keys_str_mv | AT ruigao overlappingcommunitydetectionbasedonmembershipdegreepropagation AT shoufengli overlappingcommunitydetectionbasedonmembershipdegreepropagation AT xiaohushi overlappingcommunitydetectionbasedonmembershipdegreepropagation AT yanchunliang overlappingcommunitydetectionbasedonmembershipdegreepropagation AT dongxu overlappingcommunitydetectionbasedonmembershipdegreepropagation |