HLEGF: An Effective Hypernetwork Community Detection Algorithm Based on Local Expansion and Global Fusion
Community structure is crucial for understanding network characteristics, and the local expansion method has performed well in detecting community structures. However, there are two problems with this method. Firstly, it can only add nodes or edges on the basis of existing clusters, and secondly, it...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-08-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/16/3497 |
| _version_ | 1797583987477053440 |
|---|---|
| author | Feng Wang Feng Hu Rumeng Chen Naixue Xiong |
| author_facet | Feng Wang Feng Hu Rumeng Chen Naixue Xiong |
| author_sort | Feng Wang |
| collection | DOAJ |
| description | Community structure is crucial for understanding network characteristics, and the local expansion method has performed well in detecting community structures. However, there are two problems with this method. Firstly, it can only add nodes or edges on the basis of existing clusters, and secondly, it can produce a large number of small communities. In this paper, we extend the local expansion method based on ordinary graph to hypergraph, and propose an effective hypernetwork community detection algorithm based on local expansion (LE) and global fusion (GF), which is referred to as HLEGF. The LE process obtains multiple small sub-hypergraphs by deleting and adding hyperedges, while the GF process optimizes the sub-hypergraphs generated by the local expansion process. To solve the first problem, the HLEGF algorithm introduces the concepts of community neighborhood and community boundary to delete some nodes and hyperedges in hypergraphs. To solve the second problem, the HLEGF algorithm establishes correlations between adjacent sub-hypergraphs through global fusion. We evaluated the performance of the HLEGF algorithm in the real hypernetwork and six synthetic random hypernetworks with different probabilities. Because the HLEGF algorithm introduces the concepts of community boundary and neighborhood, and the concept of a series of similarities, the algorithm has superiority. In the real hypernetwork, the HLEGF algorithm is consistent with the classical Spectral algorithm, while in the random hypernetwork, when the probability is not less than 0.95, the NMI value of the HLEGF algorithm is always greater than 0.92, and the RI value is always greater than 0.97. When the probability is 0.95, the HLEGF algorithm achieves a 2.3% improvement in the NMI value, compared to the Spectral algorithm. Finally, we applied the HLEGF algorithm to the drug–target hypernetwork to partition drugs with similar functions into communities. |
| first_indexed | 2024-03-10T23:45:59Z |
| format | Article |
| id | doaj.art-cf7b950eaf2c4d7f906a2c46e852d7c0 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T23:45:59Z |
| publishDate | 2023-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-cf7b950eaf2c4d7f906a2c46e852d7c02023-11-19T02:02:50ZengMDPI AGMathematics2227-73902023-08-011116349710.3390/math11163497HLEGF: An Effective Hypernetwork Community Detection Algorithm Based on Local Expansion and Global FusionFeng Wang0Feng Hu1Rumeng Chen2Naixue Xiong3School of Computer, Qinghai Normal University, Xining 810008, ChinaSchool of Computer, Qinghai Normal University, Xining 810008, ChinaSchool of Computer, Qinghai Normal University, Xining 810008, ChinaDepartment of Computer, Mathematical and Physical Sciences, Sul Ross State University, Alpine, TX 79830, USACommunity structure is crucial for understanding network characteristics, and the local expansion method has performed well in detecting community structures. However, there are two problems with this method. Firstly, it can only add nodes or edges on the basis of existing clusters, and secondly, it can produce a large number of small communities. In this paper, we extend the local expansion method based on ordinary graph to hypergraph, and propose an effective hypernetwork community detection algorithm based on local expansion (LE) and global fusion (GF), which is referred to as HLEGF. The LE process obtains multiple small sub-hypergraphs by deleting and adding hyperedges, while the GF process optimizes the sub-hypergraphs generated by the local expansion process. To solve the first problem, the HLEGF algorithm introduces the concepts of community neighborhood and community boundary to delete some nodes and hyperedges in hypergraphs. To solve the second problem, the HLEGF algorithm establishes correlations between adjacent sub-hypergraphs through global fusion. We evaluated the performance of the HLEGF algorithm in the real hypernetwork and six synthetic random hypernetworks with different probabilities. Because the HLEGF algorithm introduces the concepts of community boundary and neighborhood, and the concept of a series of similarities, the algorithm has superiority. In the real hypernetwork, the HLEGF algorithm is consistent with the classical Spectral algorithm, while in the random hypernetwork, when the probability is not less than 0.95, the NMI value of the HLEGF algorithm is always greater than 0.92, and the RI value is always greater than 0.97. When the probability is 0.95, the HLEGF algorithm achieves a 2.3% improvement in the NMI value, compared to the Spectral algorithm. Finally, we applied the HLEGF algorithm to the drug–target hypernetwork to partition drugs with similar functions into communities.https://www.mdpi.com/2227-7390/11/16/3497hypernetworkcommunity structurelocal expansionglobal fusion |
| spellingShingle | Feng Wang Feng Hu Rumeng Chen Naixue Xiong HLEGF: An Effective Hypernetwork Community Detection Algorithm Based on Local Expansion and Global Fusion Mathematics hypernetwork community structure local expansion global fusion |
| title | HLEGF: An Effective Hypernetwork Community Detection Algorithm Based on Local Expansion and Global Fusion |
| title_full | HLEGF: An Effective Hypernetwork Community Detection Algorithm Based on Local Expansion and Global Fusion |
| title_fullStr | HLEGF: An Effective Hypernetwork Community Detection Algorithm Based on Local Expansion and Global Fusion |
| title_full_unstemmed | HLEGF: An Effective Hypernetwork Community Detection Algorithm Based on Local Expansion and Global Fusion |
| title_short | HLEGF: An Effective Hypernetwork Community Detection Algorithm Based on Local Expansion and Global Fusion |
| title_sort | hlegf an effective hypernetwork community detection algorithm based on local expansion and global fusion |
| topic | hypernetwork community structure local expansion global fusion |
| url | https://www.mdpi.com/2227-7390/11/16/3497 |
| work_keys_str_mv | AT fengwang hlegfaneffectivehypernetworkcommunitydetectionalgorithmbasedonlocalexpansionandglobalfusion AT fenghu hlegfaneffectivehypernetworkcommunitydetectionalgorithmbasedonlocalexpansionandglobalfusion AT rumengchen hlegfaneffectivehypernetworkcommunitydetectionalgorithmbasedonlocalexpansionandglobalfusion AT naixuexiong hlegfaneffectivehypernetworkcommunitydetectionalgorithmbasedonlocalexpansionandglobalfusion |