GLOD: The Local Greedy Expansion Method for Overlapping Community Detection in Dynamic Provenance Networks
Local overlapping community detection is a hot problem in the field of studying complex networks. It is the process of finding dense clusters based on local network information. This paper proposes a method called local greedy extended dynamic overlapping community detection (GLOD) to address the ch...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-07-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/15/3284 |
| _version_ | 1827731177706881024 |
|---|---|
| author | Ying Song Zhiwen Zheng Yunmei Shi Bo Wang |
| author_facet | Ying Song Zhiwen Zheng Yunmei Shi Bo Wang |
| author_sort | Ying Song |
| collection | DOAJ |
| description | Local overlapping community detection is a hot problem in the field of studying complex networks. It is the process of finding dense clusters based on local network information. This paper proposes a method called local greedy extended dynamic overlapping community detection (GLOD) to address the challenges of detecting high-quality overlapping communities in complex networks. The goal is to improve the accuracy of community detection by considering the dynamic nature of community boundaries and leveraging local network information. The GLOD method consists of several steps. First, a coupling seed is constructed by selecting nodes from blank communities (i.e., nodes not assigned to any community) and their similar neighboring nodes. This seed serves as the starting point for community detection. Next, the seed boundaries are extended by applying multiple community fitness functions. These fitness functions determine the likelihood of nodes belonging to a specific community based on various local network properties. By iteratively expanding the seed boundaries, communities with higher density and better internal structure are formed. Finally, the overlapping communities are merged using an improved version of the Jaccard coefficient, which is a measure of similarity between sets. This step ensures that overlapping nodes between communities are properly identified and accounted for in the final community structure. The proposed method is evaluated using real networks and three sets of LFR (Lancichinetti–Fortunato–Radicchi) networks, which are synthetic benchmark networks widely used in community detection research. The experimental results demonstrate that GLOD outperforms existing algorithms and achieves a 2.1% improvement in the F-score, a community quality evaluation metric, compared to the LOCD framework. It outperforms the best existing LOCD algorithm on the real provenance network. In summary, the GLOD method aims to overcome the limitations of existing community detection algorithms by incorporating local network information, considering overlapping communities, and dynamically adjusting community boundaries. The experimental results suggest that GLOD is effective in improving the quality of community detection in complex networks. |
| first_indexed | 2024-03-11T00:22:47Z |
| format | Article |
| id | doaj.art-bda642be92b6461b919a224f3383ea33 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-11T00:22:47Z |
| publishDate | 2023-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-bda642be92b6461b919a224f3383ea332023-11-18T23:14:35ZengMDPI AGMathematics2227-73902023-07-011115328410.3390/math11153284GLOD: The Local Greedy Expansion Method for Overlapping Community Detection in Dynamic Provenance NetworksYing Song0Zhiwen Zheng1Yunmei Shi2Bo Wang3Department of Computer, Beijing Information Science and Technology University, Beijing 100101, ChinaDepartment of Computer, Beijing Information Science and Technology University, Beijing 100101, ChinaDepartment of Computer, Beijing Information Science and Technology University, Beijing 100101, ChinaSoftware Engineering College, Zhengzhou University of Light Industry, Zhengzhou 450002, ChinaLocal overlapping community detection is a hot problem in the field of studying complex networks. It is the process of finding dense clusters based on local network information. This paper proposes a method called local greedy extended dynamic overlapping community detection (GLOD) to address the challenges of detecting high-quality overlapping communities in complex networks. The goal is to improve the accuracy of community detection by considering the dynamic nature of community boundaries and leveraging local network information. The GLOD method consists of several steps. First, a coupling seed is constructed by selecting nodes from blank communities (i.e., nodes not assigned to any community) and their similar neighboring nodes. This seed serves as the starting point for community detection. Next, the seed boundaries are extended by applying multiple community fitness functions. These fitness functions determine the likelihood of nodes belonging to a specific community based on various local network properties. By iteratively expanding the seed boundaries, communities with higher density and better internal structure are formed. Finally, the overlapping communities are merged using an improved version of the Jaccard coefficient, which is a measure of similarity between sets. This step ensures that overlapping nodes between communities are properly identified and accounted for in the final community structure. The proposed method is evaluated using real networks and three sets of LFR (Lancichinetti–Fortunato–Radicchi) networks, which are synthetic benchmark networks widely used in community detection research. The experimental results demonstrate that GLOD outperforms existing algorithms and achieves a 2.1% improvement in the F-score, a community quality evaluation metric, compared to the LOCD framework. It outperforms the best existing LOCD algorithm on the real provenance network. In summary, the GLOD method aims to overcome the limitations of existing community detection algorithms by incorporating local network information, considering overlapping communities, and dynamically adjusting community boundaries. The experimental results suggest that GLOD is effective in improving the quality of community detection in complex networks.https://www.mdpi.com/2227-7390/11/15/3284overlapping communitycommunity detectiondynamic provenance network |
| spellingShingle | Ying Song Zhiwen Zheng Yunmei Shi Bo Wang GLOD: The Local Greedy Expansion Method for Overlapping Community Detection in Dynamic Provenance Networks Mathematics overlapping community community detection dynamic provenance network |
| title | GLOD: The Local Greedy Expansion Method for Overlapping Community Detection in Dynamic Provenance Networks |
| title_full | GLOD: The Local Greedy Expansion Method for Overlapping Community Detection in Dynamic Provenance Networks |
| title_fullStr | GLOD: The Local Greedy Expansion Method for Overlapping Community Detection in Dynamic Provenance Networks |
| title_full_unstemmed | GLOD: The Local Greedy Expansion Method for Overlapping Community Detection in Dynamic Provenance Networks |
| title_short | GLOD: The Local Greedy Expansion Method for Overlapping Community Detection in Dynamic Provenance Networks |
| title_sort | glod the local greedy expansion method for overlapping community detection in dynamic provenance networks |
| topic | overlapping community community detection dynamic provenance network |
| url | https://www.mdpi.com/2227-7390/11/15/3284 |
| work_keys_str_mv | AT yingsong glodthelocalgreedyexpansionmethodforoverlappingcommunitydetectionindynamicprovenancenetworks AT zhiwenzheng glodthelocalgreedyexpansionmethodforoverlappingcommunitydetectionindynamicprovenancenetworks AT yunmeishi glodthelocalgreedyexpansionmethodforoverlappingcommunitydetectionindynamicprovenancenetworks AT bowang glodthelocalgreedyexpansionmethodforoverlappingcommunitydetectionindynamicprovenancenetworks |