Abstract
The application of community detection (community discovery) has been widely used in various fields for several years. To improve the algorithm accuracy, we proposed a memetic algorithm based on an adaptive simulated annealing local search (MA-ASA). Segmented label propagation (STLP) is used for initialization and variation operations. A hierarchical idea is adopted to form an initial cluster center during initialization, and random competition is used to select the next generation of solutions. Instead of using fixed probabilities in each crossover and variation operation, we used quality differences to switch to adaptive probabilities in simulated annealing (SA) for local search to accelerate convergence. The algorithm was extensively tested and experimented with 11 artificial and 4 real networks. Compared with other 10 algorithms, the results showed that MA-ASA performs well and is highly competitive.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Latora, V., Nicosia, V., Russo, G.: Complex Networks: Principles, Methods and Applications, 1st edn. Cambridge University Press, UK (2017)
Wasserman, S., Faust, K.: Social Network Analysis, p. 825. Cambridge University Press (25 November 1994)
Li, Q., Zhong, J., Li, Q., Cao, Z., Wang, C.: Enhancing network embedding with implicit clustering. In: Li, G., Yang, J., Gama, J., Natwichai, J., Tong, Y. (eds.) Database Systems for Advanced Applications: 24th International Conference, DASFAA 2019, Chiang Mai, Thailand, April 22–25, 2019, Proceedings, Part I, pp. 452–467. Springer International Publishing, Cham (2019). https://doi.org/10.1007/978-3-030-18576-3_27
Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004)
Newman, M.E.J.: Fast algorithm for detecting community structure in networks. Phys. Rev. E 69(6), 066133 (2004)
Gong, M., Fu, B., Jiao, L., Du, H.: Memetic algorithm for community detection in networks. Phys. Rev. E 84, 056101 (2011)
Gong, M., Cai, Q., Li, Y., Ma, J.: An improved memetic algorithm for community detection in complex networks. In: 2012 IEEE Congress on Evolutionary Computation (CEC) (2012)
Sun, X., Sun, Y., Cheng, S., Bian, K., Liu, Z.: Population learning based memetic algorithm for community detection in complex networks. In: Tan, Y., Shi, Y., Zomaya, A., Yan, H., Cai, J. (eds.) DMBD 2021. CCIS, vol. 1454, pp. 275–288. Springer, Singapore (2021). https://doi.org/10.1007/978-981-16-7502-7_29
Bian, K., Sun, Y., Cheng, S., Liu, Z., Sun, X.: Adaptive methods of differential evolution multi-objective optimization algorithm based on decomposition. In: Zhang, H., Yang, Z., Zhang, Z., Wu, Z., Hao, T. (eds.) NCAA 2021. CCIS, vol. 1449, pp. 458–472. Springer, Singapore (2021). https://doi.org/10.1007/978-981-16-5188-5_33
Sun, Y., Bian, K., Liu, Z., Sun, X., Yao, R.: Adaptive strategies based on differential evolutionary algorithm for many-objective optimization. Discrete Dyn. Nat. Soc. 2021, 1–17 (2021)
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. U.S.A. 99(12), 7821–7826 (2002)
Zachary, W.W.: An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33(4), 452–473 (1977)
Lusseau, D., Schneider, K., Boisseau, O.J.: The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behav. Ecol. Sociobiol. 54(4), 396–405 (2003)
Gleiser, P., Danon, L.: Community structure in jazz. Adv. Complex Syst. 6(4), 565 (2003)
Gong, M., Cai, Q., Chen, X., Ma, L.: Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition. IEEE Trans. Evol. Comput. 18(1), 82–97 (2014)
Pizzuti, C.: A multiobjective genetic algorithm to find communities in complex networks. IEEE Trans. Evol. Comput. 16(3), 418–430 (2012)
Gong, M., Ma, L., Zhang, Q., Jiao, L.: Community detection in networks by using multiobjective evolutionary algorithm with decomposition. Phys. A 391(15), 4050–4060 (2012)
Shi, C., Yan, Z., Cai, Y., Wu, B.: Multi-objective community detection in complex networks. Appl. Soft Comput. 12(2), 850–859 (2012)
Pizzuti, C.: GA-Net: a genetic algorithm for community detection in social networks. Proc. Parallel Probl. Solving Nat. 5199, 1081–1090 (2008)
Liu, Z., Sun, Y., Cheng, S., Sun, X., Bian, K., Yao, R.: A node influence based memetic algorithm for community detection in complex networks. In: Pan, L., Cui, Z., Cai, J., Li, L. (eds.) Bio-inspired Computing: Theories and Applications, BIC-TA 2021. Communications in Computer and Information Science, vol. 1565. Springer, Singapore (2022). https://doi.org/10.1007/978-981-19-1256-6_16
Blondel, V.D., Guillaume, J.-L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theor. Exp. 2008(10), P10008 (2008)
Clauset, A., Newman, M.E.J., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70(6), 066111 (2004)
Acknowledgements
This work was supported by the National Natural Science Foundation of China (Grant No. 61703256, 61806119), Natural Science Basic Research Plan in Shaanxi Province of China (Program No. 2022JM-381, 2017JQ6070) and the Fundamental Research Funds for the Central Universities (Program No. GK201803020, GK201603014).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 IFIP International Federation for Information Processing
About this paper
Cite this paper
Yang, J. et al. (2022). A Memetic Algorithm Based on Adaptive Simulated Annealing for Community Detection. In: Shi, Z., Jin, Y., Zhang, X. (eds) Intelligence Science IV. ICIS 2022. IFIP Advances in Information and Communication Technology, vol 659. Springer, Cham. https://doi.org/10.1007/978-3-031-14903-0_3
Download citation
DOI: https://doi.org/10.1007/978-3-031-14903-0_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-14902-3
Online ISBN: 978-3-031-14903-0
eBook Packages: Computer ScienceComputer Science (R0)
