Community Detection Based on Genetic Algorithm Using Local Structural Similarity
Community detection is an important research direction in complex network analysis that aims to detect the community structure in networks via clustering operation, which has an important application value and practical significance in mining potential network information. Genetic algorithm (GA) is...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8826549/ |
| _version_ | 1818947656017248256 |
|---|---|
| author | Xuchao Guo Jie Su Han Zhou Chengqi Liu Jing Cao Lin Li |
| author_facet | Xuchao Guo Jie Su Han Zhou Chengqi Liu Jing Cao Lin Li |
| author_sort | Xuchao Guo |
| collection | DOAJ |
| description | Community detection is an important research direction in complex network analysis that aims to detect the community structure in networks via clustering operation, which has an important application value and practical significance in mining potential network information. Genetic algorithm (GA) is commonly used in community detection to solve NP-hard problems caused by modularity optimization effectively. However, in terms of GA, the problems of global search performance and slow convergence still remain due to the low accuracy of initial population generation and the randomness of the mutation operator. Thus, a novel local structural similarity-based GA (LSSGA) is proposed in this study to address such problems. It mainly contains two innovations: First, a new generation strategy for initial population based on local structural similarity and roulette wheel selection is designed to improve the quality of initial individuals, at the same time, maintain the diversity of the initial population. Secondly, an effective mutation operator based on label propagation and local structural similarity is proposed, which can quickly achieve targeted and effective mutation. The performance of LSSGA has been verified in many detailed aspects such as the convergence of initialization strategy, the effectiveness of overcome falling into local optimum, and rationality of objective function. Experimental results of both synthetic and real-world networks demonstrate the effective performance of the proposed method via systematic comparison with other existing advanced algorithms. |
| first_indexed | 2024-12-20T08:34:22Z |
| format | Article |
| id | doaj.art-9dfc2a0aa55b4ab6b5fd3514fa1622c2 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-20T08:34:22Z |
| publishDate | 2019-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-9dfc2a0aa55b4ab6b5fd3514fa1622c22022-12-21T19:46:36ZengIEEEIEEE Access2169-35362019-01-01713458313460010.1109/ACCESS.2019.29398648826549Community Detection Based on Genetic Algorithm Using Local Structural SimilarityXuchao Guo0https://orcid.org/0000-0002-6457-0534Jie Su1https://orcid.org/0000-0003-0275-0334Han Zhou2Chengqi Liu3Jing Cao4Lin Li5https://orcid.org/0000-0002-3443-3344College of Information and Electrical Engineering, China Agricultural University, Beijing, ChinaCollege of Information and Electrical Engineering, China Agricultural University, Beijing, ChinaCollege of Information and Electrical Engineering, China Agricultural University, Beijing, ChinaCollege of Information and Electrical Engineering, China Agricultural University, Beijing, ChinaCollege of Information and Electrical Engineering, China Agricultural University, Beijing, ChinaCollege of Information and Electrical Engineering, China Agricultural University, Beijing, ChinaCommunity detection is an important research direction in complex network analysis that aims to detect the community structure in networks via clustering operation, which has an important application value and practical significance in mining potential network information. Genetic algorithm (GA) is commonly used in community detection to solve NP-hard problems caused by modularity optimization effectively. However, in terms of GA, the problems of global search performance and slow convergence still remain due to the low accuracy of initial population generation and the randomness of the mutation operator. Thus, a novel local structural similarity-based GA (LSSGA) is proposed in this study to address such problems. It mainly contains two innovations: First, a new generation strategy for initial population based on local structural similarity and roulette wheel selection is designed to improve the quality of initial individuals, at the same time, maintain the diversity of the initial population. Secondly, an effective mutation operator based on label propagation and local structural similarity is proposed, which can quickly achieve targeted and effective mutation. The performance of LSSGA has been verified in many detailed aspects such as the convergence of initialization strategy, the effectiveness of overcome falling into local optimum, and rationality of objective function. Experimental results of both synthetic and real-world networks demonstrate the effective performance of the proposed method via systematic comparison with other existing advanced algorithms.https://ieeexplore.ieee.org/document/8826549/Complex networkcommunity detectiongenetic algorithmlocal structural similarityroulette wheel selection |
| spellingShingle | Xuchao Guo Jie Su Han Zhou Chengqi Liu Jing Cao Lin Li Community Detection Based on Genetic Algorithm Using Local Structural Similarity IEEE Access Complex network community detection genetic algorithm local structural similarity roulette wheel selection |
| title | Community Detection Based on Genetic Algorithm Using Local Structural Similarity |
| title_full | Community Detection Based on Genetic Algorithm Using Local Structural Similarity |
| title_fullStr | Community Detection Based on Genetic Algorithm Using Local Structural Similarity |
| title_full_unstemmed | Community Detection Based on Genetic Algorithm Using Local Structural Similarity |
| title_short | Community Detection Based on Genetic Algorithm Using Local Structural Similarity |
| title_sort | community detection based on genetic algorithm using local structural similarity |
| topic | Complex network community detection genetic algorithm local structural similarity roulette wheel selection |
| url | https://ieeexplore.ieee.org/document/8826549/ |
| work_keys_str_mv | AT xuchaoguo communitydetectionbasedongeneticalgorithmusinglocalstructuralsimilarity AT jiesu communitydetectionbasedongeneticalgorithmusinglocalstructuralsimilarity AT hanzhou communitydetectionbasedongeneticalgorithmusinglocalstructuralsimilarity AT chengqiliu communitydetectionbasedongeneticalgorithmusinglocalstructuralsimilarity AT jingcao communitydetectionbasedongeneticalgorithmusinglocalstructuralsimilarity AT linli communitydetectionbasedongeneticalgorithmusinglocalstructuralsimilarity |