Fanzhen Liu
ABSTRACT
Evolutionary algorithm belongs to the behaviorism which is one of major approaches to artificial intelligence. Community detection is one of the important applications of the evolutionary algorithm. Detecting the community structure, an essential property for complex networks, can help us understand the inherent functions of real systems. It has been proved that genetic algorithm (GA) is feasible for community detection, and yet existing GA-based community detection algorithms still need improving in terms of their robustness and accuracy. A Physarum-based network model (PNM) with an intelligence of recognizing inter-community edges based on a kind of multi-headed slime mold, has been proposed in the phase of GA's initialization for optimization. In this paper, integrated with PNM after three operators of GA during the process of community detection, a novel genetic algorithm, called P-GACD, is proposed to improve the efficiency of GA for community detection. In addition, some experiments are implemented in five real-world networks to evaluate the performance of P-GACD. The results reveal that P-GACD shows an advantage in terms of the robustness and accuracy, contrasted with the existing algorithms.
- Lada A Adamic and Natalie Glance. 2005. The Political Blogosphere and the 2004 US Election: Divided They Blog. In Proceedings of the 3rd International Workshop on Link Discovery. ACM, 36--43. Google Scholar
Digital Library
- Qing Cai, Maoguo Gong, Lijia Ma, Shasha Ruan, Fuyan Yuan, and Licheng Jiao. 2015. Greedy Discrete Particle Swarm Optimization for Large-scale Social Network Clustering. Information Sciences 316 (September 2015), 503--516. Google ScholarDigital Library
- Qing Cai, Lijia Ma, Maoguo Gong, and Dayong Tian. 2014. A Survey on Network Community Detection Based on Evolutionary Computation. International Journal of Bio-Inspired Computation 8, 2 (January 2014), 84--98. Google ScholarDigital Library
- Aaron Clauset, Mark EJ Newman, and Cristopher Moore. 2004. Finding Community Structure in Very Large Networks. Physical Review E 70, 6 (December 2004), 066111.Google ScholarCross Ref
- Santo Fortunato. 2010. Community Detection in Graphs. Physics Reports 486, 3--5 (February 2010), 75--174.Google ScholarCross Ref
- Rodrigo Francisquini, Valrio Rosset, and Mari C. V. Nascimento. 2017. GA-LP: A Genetic Algorithm Based on Label Propagation to Detect Communities in Directed Networks. Expert Systems with Applications 74 (May 2017), 127--138. Google ScholarDigital Library
- Michelle Girvan and Mark EJ Newman. 2002. Community Structure in Social and Biological Networks. Proceedings of the National Academy of Sciences 99, 12 (June 2002), 7821--7826.Google ScholarCross Ref
- Donald Ervin Knuth. 1993. The Stanford GraphBase: A Platform for Combinatorial Computing. Addison-Wesley Reading, Austin, Texas. Google Scholar
- Dongsheng Li, Qin Lv, Xing Xie, Li Shang, Huanhuan Xia, Tun Lu, and Ning Gu. 2012. Interest-based Real-time Content Recommendation in Online Social Communities. Knowledge-Based Systems 28 (April 2012), 1--12. Google ScholarDigital Library
- Xianghua Li, Chao Gao, and Ruyang Pu. 2014. A Community Clustering Algorithm Based on Genetic Algorithm with Novel Coding Scheme. In 2014 10th International Conference on Natural Computation (ICNC). IEEE, 486--491.Google ScholarCross Ref
- Mingxin Liang, Chao Gao, and Zili Zhang. 2017. A New Genetic Algorithm Based on Modified Physarum Network Model for Bandwidth-delay Constrained Least-cost Multicast Routing. Natural Computing 16, 1 (March 2017), 85--98. Google ScholarDigital Library
- Yuxin Liu, Chao Gao, Zili Zhang, Yuxiao Lu, Shi Chen, Mingxin Liang, and Li Tao. 2017. Solving NP-hard Problems with Physarum-based Ant Colony System. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 14, 1 (January 2017), 108--120. Google ScholarDigital Library
- Yitong Lu, Mingxin Liang, Chao Gao, Yuxin Liu, and Xianghua Li. 2016. A Bio-inspired Genetic Algorithm for Community Mining. In 2016 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD). IEEE, 673--679.Google ScholarCross Ref
- Toshiyuki Nakagaki, Hiroyasu Yamada, and Masahiko Hara. 2004. Smart Network Solutions in an Amoeboid Organism. Biophysical Chemistry 107, 1 (January2004), 1--5.Google ScholarCross Ref
- Mark EJ Newman. 2006. Finding Community Structure in Networks Using the Eigenvectors of Matrices. Physical Review E 74, 3 (September 2006), 036104.Google ScholarCross Ref
- Mark EJ Newman. 2006. Modularity and Community Structure in Networks. Proceedings of the National Academy of Sciences 103, 23 (June 2006), 8577--8582.Google ScholarCross Ref
- Mark EJ Newman and Michelle Girvan. 2004. Finding and Evaluating Community Structure in Networks. Physical Review E 69, 2 (February 2004), 026113.Google ScholarCross Ref
- Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. 2007. Near Linear Time Algorithm to Detect Community Structures in Large-scale Networks. Physical Review E 76, 3 (September 2007), 036106. 76.036106Google ScholarCross Ref
- Martin Rosvall and Carl T Bergstrom. 2008. Maps of Random Walks on Complex Networks Reveal Community Structure. Proceedings of the National Academy of Sciences 105, 4 (January 2008), 1118--1123.Google ScholarCross Ref
- Mursel Tasgin, Amac Herdagdelen, and Haluk Bingol. 2007. Community Detection in Complex Networks Using Genetic Algorithms. (November 2007). https://arxiv.org/abs/0711.0491Google Scholar
- Atsushi Tero, Ryo Kobayashi, and Toshiyuki Nakagaki. 2007. A Mathematical Model for Adaptive Transport Network in Path Finding by True Slime Mold. Journal of Theoretical Biology 244, 4 (February 2007), 553--564.Google ScholarCross Ref
- Atsushi Tero, Seiji Takagi, Tetsu Saigusa, Kentaro Ito, Dan P Bebber, Mark D Fricker, Kenji Yumiki, Ryo Kobayashi, and Toshiyuki Nakagaki. 2010. Rules for Biologically Inspired Adaptive Network Design. Science 327, 5964 (January 2010), 439--442.Google ScholarCross Ref
- Jina Wang. 2009. Ant Colony Algorithms Based Community Clustering Research. Master's thesis. Sun Yat-sen University.Google Scholar
- Lilian Weng, Filippo Menczer, and Yong-Yeol Ahn. 2013. Virality Prediction and Community Structure in Social Networks. Scientific Reports 3 (November 2013), 2522.Google Scholar
- Wayne W Zachary. 1977. An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research 33, 4 (Winter 1977), 452--473.Google ScholarCross Ref
- Xiaoge Zhang and Sankaran Mahadevan. 2017. A Bio-inspired Approach to Traffic Network Equilibrium Assignment Problem. IEEE Transactions on Cybernetics PP, 99 (April 2017), 1--12.Google Scholar
Index Terms
- A hybrid evolutionary algorithm for community detection
Recommendations
Multi-objective evolutionary algorithm using problem-specific genetic operators for community detection in networks
Automatic network clustering is an important method for mining the meaningful communities of complex networks. Uncovered communities help to understand the potential system structure and functionality. Many algorithms that use multiple optimization ...
Hybrid Taguchi-genetic algorithm for global numerical optimization
In this paper, a hybrid Taguchi-genetic algorithm (HTGA) is proposed to solve global numerical optimization problems with continuous variables. The HTGA combines the traditional genetic algorithm (TGA), which has a powerful global exploration capability,...
Community Structure Detection Using Firefly Algorithm
This article describes how parallel to the continuous growth of the Internet, which allows people to share and collaborate more, social networks have become more attractive as a research topic in many different disciplines. Community structures are ...
Comments