Abstract
Community structure is a significant property when analyzing the features and functions of complex systems. Heuristic algorithm-based community detection treats finding the community structure as an optimization problem, which has received great attentions in a variety of fields these years. Several community detection methods have been proposed. To make an approach of detecting the community structure in a more efficient way, a node influence based memetic algorithm (NIMA), considering node influence, is proposed in this paper. The NIMA consists of three main parts. First of all, a transition probability matrix-based initialization is employed to accelerate the convergence speed and provide an initial population with great diversity. Secondly, a network-specific crossover and a node degree-based mutation are designed to enlarge the search space and keep effective information. Last, a multi-level greedy search is deployed to find the potential optimal solutions quickly and effectively. Extensive experiments on 28 synthetic and 6 real-world networks demonstrate that compared with 11 existing algorithms, the proposed NIMA has effective performance on detecting communities in complex networks.
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 ed. Cambridge University Press, Cambridge (2017). https://doi.org/10.1017/9781316216002
Watts, D.J.: A twenty-first century science. Nature 445(7127), 489 (2007)
Lazer, D., et al.: Life in the network: the coming age of computational social science. Science 323(5915), 721–723 (2009)
Suweis, S., Simini, F., Banavar, J.R., Maritan, A.: Emergence of structural and dynamical properties of ecological mutualistic networks. Nature 500(7463), 449–452 (2013)
Chakraborty, T., Ghosh, S., Park, N.: Ensemble-based overlapping community detection using disjoint community structures. Knowl.-Based. Syst 163, 241–251 (2019). https://doi.org/10.1016/j.knosys.2018.08.033
Yang, L., Cao, X., He, D., Wang, C., Zhang, W.: Modularity based community detection with deep learning. In: Proceedings of International Joint Conference on Artificial Intelligence, pp. 2252–2258 (2016). https://doi.org/10.5555/3060832.3060936
You, X., Ma, Y., Liu, Z.: A three-stage algorithm on community detection in social networks. Knowl.-Based Syst. 187, 104822 (2020). https://doi.org/10.1016/j.knosys.2019.06.030
Zhang, J., Ding, X., Yang, J.: Revealing the role of node similarity and community merging in community detection. Knowl.-Based Syst. 165, 407–419 (2019). https://doi.org/10.1016/j.knosys.2018.12.009
Lu, M., Zhang, Z., Qu, Z., Kang, Y.: LPANNI: overlapping community detection using label propagation in large-scale complex networks. IEEE Trans. Knowl. Data Eng. 31(9), 1736–1749 (2019). https://doi.org/10.1109/TKDE.2018.2866424
Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3–5), 75–174 (2010)
Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004). https://link.aps.org/doi/10.1103/PhysRevE.69.026113
Newman, M.E.J.: Fast algorithm for detecting community structure in networks. Phys. Rev. E 69(6), 066133 (2004). https://doi.org/10.1103/PhysRevE.69.066133
Newman, M.E.J.: Modularity and community structure in networks. Proc. Natl. Acad. Sci. U.S.A. 103(23), 8577–8582 (2006)
Newman, M.E.J.: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74(3), 036104 (2006). https://link.aps.org/doi/10.1103/PhysRevE.74.036104
Lancichinetti, A., Fortunato, S.: Limits of modularity maximization in community detection. Phys. Rev. E 84, 066122 (2011)
Zhan, Z., Shi, L., Tan, K., Zhang, J.: A survey on evolutionary computation for complex continuous optimization. Artificial Intell. Rev. 55, 59–110 (2021). https://doi.org/10.1007/s10462-021-10042-y
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
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). https://doi.org/10.1109/TEVC.2013.2260862
Li, C., Chen, H., Li, T., et al.: A stable community detection approach for complex network based on density peak clustering and label propagation. Appl Intell. 52, 1188–1208 (2021). https://doi.org/10.1007/s10489-021-02287-5
Ma, L., Gong, M., Liu, J., Cai, Q., Jiao, L.: Multi-level learning based memetic algorithm for community detection. Appl. Soft Comput. 19, 121–133 (2014). https://doi.org/10.1016/j.asoc.2014.02.003
Chen, D., Liu, C., Huang, X., Wang, D., Yan, J.: A probability transition matrix-based recommendation algorithm for bipartite networks. In: Liu, Y., Wang, L., Zhao, L., Yu, Z. (eds.) ICNC-FSKD 2019. AISC, vol. 1074, pp. 921–929. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-32456-8_99
Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theory and Experiment (10), P10008 (2008)
Coello, C., Pulido, G., Lechuga, M.: Handling multiple objectives with particle swarm optimization. IEEE Trans. Evol. Comput. 8(3), 256–279 (2004)
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)
Gong, M., Fu, B., Jiao, L., Du, H.: Memetic algorithm for community detection in networks. Phys. Rev. E 84(5), 056101 (2011)
Pizzuti, C.: GA-Net: A genetic algorithm for community detection in social networks. Proc. Parallel Problem Solving Nat. 5199, 1081–1090 (2008)
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)
Clauset, A., Newman, M.E.J., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70(6), 066111 (2004)
Rosvall, M., Bergstrom, C.T.: Maps of random walks on complex networks reveal community structure. Proc. Natl. Acad. Sci. USA 105(4), 1118–1123 (2008)
Fortunato, S., Lancichinetti, A.: Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. E 80(1), 016118 (2009)
Zachary, W.W.: An information-flow model for conflict and fission in small groups. J. Anthropol. Res. 33(4), 452–473 (1997)
Lusseau, D., Schneider, K., Boisseau, O.J., Haase, P., Slooten, E., Dawson, S.M.: 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)
Guimerà, R., Danon, L., Díaz-Guilera, A.: Self-similar community structure in a network of human interactions. Phys. Rev. E 68(6), 065103 (2003)
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440–442 (1998)
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. 2017JQ6070), the Fundamental Research Funds for the Central Universities (Program No. GK201803020) and the Graduate Innovation Team Project of Shaanxi Normal University (Grant No. TD2020014Z).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Liu, Z., Sun, Y., Cheng, S., Sun, X., Bian, K., Yao, R. (2022). 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. https://doi.org/10.1007/978-981-19-1256-6_16
Download citation
DOI: https://doi.org/10.1007/978-981-19-1256-6_16
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-19-1255-9
Online ISBN: 978-981-19-1256-6
eBook Packages: Computer ScienceComputer Science (R0)