Multi-agent memetic algorithm and its application to community structure detection in complex networks

Document Type : Original Article

Authors

• Somayeh Ranjkesh ¹
• Behrooz Masoumi ²
• Mohsen Hashemi ³

¹ Department of Electrical and Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran

² Faculty of Computer and Information Technology Engineerin

³ Faculty of Electrical and Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran,

10.22067/cke.2022.69792.1007

Abstract

A complex system is a system that has many components that are interdependent and appear as a whole and exhibit organized behavior. Community structure detection is an optimization problem in complex networks that involves searching for communities belonging to a network that shares nodes of a similar community with standard features. In this paper, we use a multi-agent memetic algorithm to detect the structure of the community in complex networks by optimizing the amount of modularity and calling it MAMA-Net. In the multi-agent memetic algorithm, agents are placed in a network-like environment to detect the community. Local search is used to find solution space. Having a local search in the memetic algorithm allows each member of the population to increase its evaluation function based on the suitability of its neighbors and achieve the desired result in minimum time. We compare the performance of MAMA-Net in detecting community structure with some standard algorithms. Both real-world and synthetic benchmark networks are used to evaluate the performance of the proposed method. The results show that MAMA-Net could detect communities more accurately than other comparable algorithms.
 

Keywords

• Complex systems
• Multi-agent systems
• Memetic algorithm
• Community detection

Main Subjects

• Machine learning

---

References

[1]   Guo, L., Nian, X., Pan, H., "Leader-following consensus of multi-agent system with diffusion", Asian J. Control, vol.16 (1), pp. 188–197, (2014).

[2]   Ye, Z., Hu, S., Yu, J., "Adaptive clustering algorithm for community detection in complex networks", Phys. Rev. vol. 78(4), (2008).

[3]   Fortunato, S., Castellano, C., "Community structure in graphs", Computational Complexity. Springer; pp. 490–512, (2012).

[4]   Girvan, M., Newman, M., "Community structure in social and biological networks", Proc. Natl. Acad. Sci. vol. 99(12), pp. 7821–7826, (2002).

[5]   Newman, M., Girvan, M., "Finding and evaluating community structure in networks", Phys. Rev. vol. 69 (2), pp. 026113, (2004). https://doi.org/10.1103/PhysRevE.69.026113.

[6]   Newman, M., "Modularity and community structure in networks", Proc. Natl. Acad. Sci, vol. 103(23), pp.8577–8582, (2006).

[7]   Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikoloski, Z., Wagner, D., "On modularity clustering", IEEE Trans. Knowl. Data Eng. Vol. 20 (2), pp. 172–188. https://doi.org/10.1109/TKDE.2007.190689, (2008).

[8]   Li, T., Lei, L., Bhattacharyya Sh., Berge, K., Sarkar, P., Bickel, P., Levina, E.,  "Hierarchical Community Detection by Recursive Partitioning", Journal of the American Statistical Association, Published online, (2020).  https://doi.org/10.1080/01621459.2020.1833888.

[9]   Ahuja, M., "Problem domains in complex networks", IOSR Journal of Computer Engineering (IOSR-JCE). vol. 18(5), pp. 65-68, (2016).

[10] Rahimi, S., Abdollahpouri, A., Moradi, P., "A multi-objective particle swarm optimization algorithm for community detection in complex networks", Swarm and Evolutionary Computation, pp. 297-309, (2018). https://doi.org/10.1016/j.swevo.2017.10.009.

[11] Pizzuti, C., "Ga-net: A genetic algorithm for community detection in social networks", Parallel Problem Solving from Nature–PPSN X, Springer; pp. 1081–1090.  https://doi.org/10.1007/978-3-540-87700-4_107, (2008).

[12] Liu, J., Zhong, W., Jiao, L., "A multi-agent evolutionary algorithm for combinatorial optimization problems", IEEE Trans. Syst. Man Cybern, vol. 40 (1), pp. 229–240.  https://doi.org/10.1109/TSMCB.2009.2025775, (2010).

[13] Liu, J., Zhong, W., Jiao, L., "A multi-agent evolutionary algorithm for constraint satisfaction problems", IEEE Trans. Syst. Man Cybern. vol. 36 (1), pp. 54–73, (2006). https://doi.org/10.1109/TSMCB.2005.852980.

[14] Naeni L., Berretta, R., Moscato, P., "MA-Net: A reliable memetic algorithm for community detection by modularity optimization", In Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems. Springer, pp. 311–323, (2015). https://doi.org/10.1007/978-3-319-13359-1_25.

[15] Li, Z., Liu, J., "A multi-agent genetic algorithm for community detection in complex networks", Physica A., vol. 449, pp. 336–347, (2016). https://doi.org/10.1016/j.physa.2015.12.126.

[16] Shang, R., Bai, J., Jiao, L., Jin, C., "Community detection based on modularity and an improved genetic algorithm", Phys. Stat. Mech. Appl, vol. 39 (2), pp. 1215–1231, (2013).  https://doi.org/10.1016/j.physa.2012.11.003.

[17] Gach, O., Hao, J., "A Memetic Algorithm for Community Detection in Complex Networks", Lecture Notes in Computer Science, pp. 327-336, (2012). https://doi.org/10.1007/978-3-642-32964-7_33.

[18] Mirsaleh, M, Meybodi, M., "A Michigan memetic algorithm for solving the community detection problem in a complex network", Neurocomputing, vol. 21(4), pp. 535–545, (2016).

  https://doi.org/10.1016/j.neucom.2016.06.030

[19] Shi, C., Wang, Y., Wu, B., Zhong, C., "A new genetic algorithm for community detection", in International Conference on Complex Sciences, vol. 1298–1309, (2009).

[20] Pizzuti, C., "A multi-objective genetic algorithm to find communities in complex networks", IEEE Trans. Evol. Comput. vol. 16(3), pp. 418–430, (2012).

[21] Gong, M., Ma, L., Zhang, Q., Jiao, L., "Community detection in networks using a multi-objective evolutionary algorithm with decomposition", Physica A, vol. 391(15), pp. 4050–4060, (2012).

[22] Gong, M., Chen, X., Ma, L., Zhang, Q., Jiao, L., "Identification of multi-resolution network structures with a multi-objective immune algorithm", Appl. Soft Comput. vol, 13(4), pp. 1705–1717, (2013).

[23] Ji Ping, Zhang Shanxin, Zhou ZhiPing. "A decomposition-based ant colony optimization algorithm for the multi-objective community detection", Journal of Ambient Intelligence and Humanized Computing, vol. 11, pp. 173–188, (2020). https://doi.org/10.1007/s12652-019-01241-1.

[24] Luo, X., Liu, Z., Shang, M., Lou, J., Zhou, M., "Highly accurate community detection via pointwise mutual information incorporated symmetric nonnegative matrix factorization", IEEE Transactions on Network Science and Engineering, vol. 8 (1), pp. 463–476, (2021).

[25] Lu, H., Sang, X., Zhao, Q., and Lu, J., "Community detection algorithm based on nonnegative matrix factorization and improved density peak clustering", IEEE Access, vol. 8, pp. 5749–5759, (2020).

[26] Fiscarelli, A., Brust, M., Danny, G., Bouvry, P., "A vertex-similarity clustering algorithm for community detection", Journal of Information and Telecommunication, vol. 4(1), (2020). https://doi.org/10.1080/24751839.2019.1686683.

[27] Agrawal, S., Patel, A., "Clustering Algorithm for Community Detection in Complex Network: A Comprehensive Review", Computer Science, (2020).  https://doi.org/10.2174/2213275912666190710183635

[28] Chi, Y., Song, X., Zhou, D., Hino, K., and Tseng, B., "ACM Trans", Knowl. Discov. Data 3, vol. 17(1), (2009).

[29] Tang, F., Wang, Ch., Su, J., Wang, Y., "Semidefinite programming based community detection for node-attributed and multiplex networks", Communications in Statistics - Simulation and Computation, Published online. (2020). https://doi.org/10.1080/03610918.2020.1847291.

[30] Zarandi, F., Rafsanjani, M., "Community detection in complex networks using structural similarity", Physica A: Statistical Mechanics and its Applications, vol. 503, pp. 882-891, (2018).

https://doi.org/10.1016/j.physa.2018.02.212.

[31] Ye Zhiwen, Zhang Hui, Feng Libo, and Shan Zhangming. CDCN: A New NMF-Based Community Detection Method with Community Structures and Node Attributes. Wireless Communications and Mobile Computing, (2021). https://doi.org/10.1155/2021/5517204.

[32] Tang, F., Ding, W., "Community detection with structural and attribute similarities", School of Mathematics Sciences, Huaibei Normal University, Huaibei, Chinahttp://orcid.org/0000-0001-8582-2078 Journal of Statistical Computation and Simulation, vol. 89(4), (2019).  https://doi.org/10.1080/00949655.2019.1568435.

[33] Chen, Q., Qiao, T. L., Hu, F., Li, Y., "Community detection in complex network based on the APT method", Pattern Recognition, (2020).  https://doi.org/10.1016/j.patrec.2020.07.021.

[34] Alvari, H., Lakkaraju, K., Sukthankar, G., and Whetzel, J., "Predicting guild membership in massively multiplayer online games", In Proceedings of the International Conference on Social Computing, Behavioral-Cultural Modeling, and Prediction, Washington, pp. 215–222, (2014).

[35] Beigi, G., Alvari, H., Jalili, M., and Sukthankar, G., "Leveraging community detection for accurate trust prediction", In ASE International Conference on Social Computing, Palo Alto, CA, May, (2014).

[36] Alvari Hamidreza, Hajibagheri Alireza, Sukthankar Gita.   Community detection in dynamic social networks: A game-theoretic approach. In IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, (2014).

[37] Xie, J., and Szymanski, B., "Labelrank: A stabilized label propagation algorithm for network community detection", In-Network Science Workshop (NSW), IEEE, pp. 138-143, (2013).

[38] Zhang, X., Ren, J., Song, Ch., and Zhang, Q., "Label propagation algorithm for community detection based on node importance and label influence", Physics Letters A, vol. 381(33), pp. 2691-2698, (2017).  https://doi.org/10.1016/j.physleta.2017.06.018.

[39] Zhong, W., Liu, J., Xue, M., Jiao, L., "A multi-agent genetic algorithm for global numerical optimization", IEEE Trans, vol. 34 (2), pp. 1128–1141, (2004).  https://doi.org/10.1109/TSMCB.2003.821456.

[40] Maesani, A., Lacca, G., Floreano, D., "Memetic Viability Evolution for Constrained Optimization", IEEE Transactions on Evolutionary Computation. vol. 1(20), pp. 125-144, (2016).

[41] Park, Y., Song, M., "A genetic algorithm for clustering problems", In Proceedings of the Third Annual Conference on Genetic Programming, (1998).

[42] Leung, Y., Wang, Y., "An orthogonal genetic algorithm with quantization for global numerical optimization", IEEE Trans. Evol. Comput. pp. 41–53, (2001).

[43] Li, Zh., Liu, J., "A multi-agent genetic algorithm for community detection in complex networks", Physica A, vol. 449, pp. 336–347, (2016).

  https://doi.org/10.1016/j.physa.2015.12.126.

[44] Liu, X., Murata, T., "Advanced modularity specialized label propagation algorithm for detecting communities in networks", Physica A. Statistical Mechanics and its Applications, vol. 398(7), (2010).

  https://doi.org/10.1016/j.physa.2009.12.019.

[45] Rotta, R., Noack, A., "Multilevel local search algorithms for modularity clustering", J. Exp. Algorithmic, vol. 6(2), pp. 1594-1605, (2011). https://doi.org/10.1145/1963190.1970376.

[46] Liu, J., Liu, T., "Detecting community structure in complex networks using simulated annealing with -means algorithms", Physica A: Statistical Mechanics and its Applications, vol. 389(11), pp. 2300-2309, (2010).   https://doi.org/10.1016/j.physa.2010.01.042.

[47] Danon, L., Diaz-Guilera, A., Duch, J., Arenas, A., "Comparing community structure identification", J. Stat. Mech. Theory Exp. (2005). https://doi.org/10.1088/1742-5468/2005/09/P09008.

[48] Zachary, W., "An information flow model for conflict and fission in small groups", J. Anthropol. Res. (1977). https://doi.org/10.1086/jar.33.4.3629752.

[49] Ma, L., "Multi-level learning-based memetic algorithm for community detection", Applied Soft Computing,   vol. 19(0), pp. 121-133, (2014).

  https://doi.org/10.1016/j.asoc.2014.02.003 

[50] Krebs, V., "A network of books about US politics", (2008). http://www.orgnet.com/.

[51] Lancichinetti, A., Fortunato, S., Radicchi, F., "Benchmark graphs for testing community detection algorithms", Phys. Rev. E, (2008).

[52] Khomami, M., Rezvanian, A., Meybodi, M., "A New Cellular Learning Automata-based Algorithm for Community Detection in Complex Social Networks", Journal of Computational Science, vol. 24, pp. 413-426, (2018).

https://doi.org/10.1016/j.jocs.2017.10.009.