A Multi-objective Multi-agent Optimization Algorithm for the Community Detection Problem
محورهای موضوعی : Complex NetworksAmir Hossein Hosseinian 1 , Vahid Baradaran 2
1 - Islamic Azad University, Tehran North Branch
2 - Islamic Azad, Tehran Shomal University
کلید واژه: Community detection problem , Complex networks , Multi-agent systems,
چکیده مقاله :
This paper addresses the community detection problem as one of the significant problems in the field of social network analysis. The goal of the community detection problem is to find sub-graphs of a network where they have high density of within-group connections, while they have a lower density of between-group connections. Due to high practical usage of community detection in scientific fields, many researchers developed different algorithms to meet various scientific requirements. However, single-objective optimization algorithms may fail to detect high quality communities of complex networks. In this paper, a novel multi-objective Multi-agent Optimization Algorithm, named the MAOA is proposed to detect communities of complex networks. The MAOA aims to optimize modularity and community score as objective functions, simultaneously. In the proposed algorithm, each feasible solution is considered as an agent and the MAOA organizes agents in multiple groups. The MAOA uses new search operators based on social, autonomous and self-learning behaviors of agents. Moreover, the MAOA uses the weighted sum method (WSM) in finding the global best agent and leader agent of each group. The Pareto solutions obtained by the MAOA is evaluated in terms of several performance measures. The results of the proposed method are compared with the outputs of three meta-heuristics. Experiments results based on five real-world networks show that the MAOA is more efficient in finding better communities than other methods.
This paper addresses the community detection problem as one of the significant problems in the field of social network analysis. The goal of the community detection problem is to find sub-graphs of a network where they have high density of within-group connections, while they have a lower density of between-group connections. Due to high practical usage of community detection in scientific fields, many researchers developed different algorithms to meet various scientific requirements. However, single-objective optimization algorithms may fail to detect high quality communities of complex networks. In this paper, a novel multi-objective Multi-agent Optimization Algorithm, named the MAOA is proposed to detect communities of complex networks. The MAOA aims to optimize modularity and community score as objective functions, simultaneously. In the proposed algorithm, each feasible solution is considered as an agent and the MAOA organizes agents in multiple groups. The MAOA uses new search operators based on social, autonomous and self-learning behaviors of agents. Moreover, the MAOA uses the weighted sum method (WSM) in finding the global best agent and leader agent of each group. The Pareto solutions obtained by the MAOA is evaluated in terms of several performance measures. The results of the proposed method are compared with the outputs of three meta-heuristics. Experiments results based on five real-world networks show that the MAOA is more efficient in finding better communities than other methods.
[1] K.R. Zalik, and B. Zalik, “Multi-objective evolutionary algorithm using problem-specific genetic operators for community detection in networks”, Neural Computing and Applications, Vol. 1, 2017, pp. 1-14.
[2] S. Fortunato, “Community detection in graphs”, Physics Reports, Vol. 486, No. 3, 2010, pp. 1-100.
[3] Z. Zhao, S. Feng, Q. Wang, J.Z. Huang, G.J. Williams, and J. Fan, “Topic oriented community detection through social objects and link analysis in social networks”, Knowledge-Based Systems, Vol. 26, 2012, pp. 164-173.
[4] S. Rahimi, A. Abdollahpouri, and P. Moradi, “A multi-objective particle swarm optimization algorithm for community detection in complex networks”, Swarm and Evolutionary Computation, Vol. 39, 2018, pp. 297-309.
[5] C. Pizzuti, “GA-Net: A genetic algorithm for community detection in social networks”, In Proc. Parallel Problem Solving from Nature–PPSN X, Springer, 2008, pp. 1081-1090.
[6] M. Gong, B. Fu, L. Jiao, and H. Du, “Memetic algorithm for community detection in networks”, Physical Review E, Vol. 84, 2011, pp. 1-9.
[7] C. Pizzuti, “A multi-objective genetic algorithm to find communities in complex networks”, IEEE Transactions on Evolutionary Computation, Vol. 16, 2012, pp. 418-430.
[8] C. Shi, Z. Yan, Y. Cai, and B. Wu, “Multi-objective community detection in complex networks”, Applied Soft Computing, Vol. 12, 2012, pp. 850-859.
[9] M. Gong, L. Ma, Q. Zhang, and L. Jiao, “Community detection in networks by using multi-objective evolutionary algorithm with decomposition”, Physica A: Statistical Mechanics and its Applications, Vol. 391, 2012, pp. 4050-4060.
[10] J. Li, and Y. Song, “Community detection in complex networks using extended compact genetic algorithm”, Soft computing, Vol. 17, 2013, pp. 925-937.
[11] B. Amiri, L. Hossain, J.W. Crawford, and R.T. Wigand, “Community detection in complex networks: Multi–objective enhanced firefly algorithm”, Knowledge-Based Systems, Vol. 46, 2013, pp. 1-11.
[12] Q. Cai, M. Gong, B. Shen, L. Ma, and L. Jiao, “Discrete particle swarm optimization for identifying community structures in signed social networks”, Neural Networks, Vol. 58, 2014, pp. 4-13.
[13] M. Gong, Q. Cai, X. Chen, and L. Ma, “Complex network clustering by multi-objective discrete particle swarm optimization based on decomposition”, IEEE Transactions on Evolutionary Computation, Vol. 18, 2014, pp. 82-97.
[14] Q. Cai, M. Gong, L. Ma, S. Ruan, F. Yuan, and L. Jiao, “Greedy discrete particle swarm optimization for large-scale social network clustering”, Information Sciences, Vol. 316, 2015, pp. 503-516.
[15] Y. Zhou, J. Wang, N. Luo, and Z. Zhang, “Multi-objective local search for community detection in networks”, Soft Computing, Vol. 20, 2015, pp. 3273–3282.
[16] R. Shang, S. Luo, W. Zhang, R. Stolkin, and L. Jiao, “A multi-objective evolutionary algorithm to find community structures based on affinity propagation”, Physica A: Statistical Mechanics and its Applications, Vol. 453, 2016, pp. 203-227.
[17] H.S. Cheraghchi, and A. Zakerolhosseini, “COGNISON: A Novel Dynamic Community Detection Algorithm in Social Network”, Journal of Information Systems and Telecommunication, Vol. 4, No. 2, 2016, pp. 78-84.
[18] S. Bilal, and M. Abdelouahab, “Evolutionary algorithm and modularity for detecting communities in networks”, Physica A: Statistical Mechanics and its Applications, Vol. 473, 2017, pp. 89-96.
[19] L. Li, L. Jiao, J. Zhao, R. Shang, and M. Gong, “Quantum-behaved discrete multi-objective particle swarm optimization for complex network clustering”, Pattern Recognition, Vol. 63, 2017, pp. 1-14.
[20] J. Handl, and J. Knowles, “An evolutionary approach to multi-objective clustering”, IEEE transactions on Evolutionary Computation, Vol. 11, 2007, pp. 56-76.
[21] N.R. Jennings, K. Sycara, and M. Wooldridge, “A roadmap of agent research and development”, Autonomous Agents and Multi-Agent Systems, Vol. 1, No. 1, 1998, pp. 7–38.
[22] J. Li, H. Jing, and Y.Y. Tang, “Multi-agent oriented constraint satisfaction”, Artificial Intelligence, Vol. 136, No. 1, 2002, pp. 101-144.
[23] X.L. Zheng, and L. Wang, “A multi-agent optimization algorithm for resource constrained project scheduling problem”, Expert Systems with Application, Vol. 42, 2015; pp. 6039-6049
. [24] W.C. Zhong, J. Liu, M.Z. Xue, and L.C. Jiao, “A multi-agent genetic algorithm for global numerical optimization”, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 34, No. 2, 2004, pp. 229-244.
[25] K. Deb, A. Pratap, S. Agrawal, and T. Meyarivan, “A Fast and Elitist Multi-objective Genetic Algorithm: NSGA-II”, IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, 2000, pp. 182-197.
[26] R.T. Marler, and J.S. Arora, “The weighted sum method for multi-objective optimization: new insights”, Structural and Multidisciplinary Optimization, Vol. 41, No. 6, 2010, pp. 853-862.
[27] C. A. Coello Coello, and M. S. Lechuga, "MOPSO: a proposal for multiple objective particle swarm optimization", In Proc. Congress on Evolutionary Computation (CEC'02), Honolulu, HI, USA, Vol. 2, 2002, pp. 1051-1056.
[28] W. Sheng, Y. Liu, X. Meng, and T. Zhang, “An Improved Strength Pareto Evolutionary Algorithm 2 with application to the optimization of distributed generations”, Computers & Mathematics with Applications, Vol. 64, No. 5, 2012, pp. 944-955.
[29] W. W. Zachary, "An information flow model for conflict and fission in small groups", Journal of anthropological research, Vol. 33, No.4, 1977, pp. 452-473.
[30] D.E. Knuth, “The Stanford Graph Base: A Platform for Combinatorial Computing”, Addison-Wesley, Reading, MA (1993).
[31] H. R. Bernard, P. D. Killworth, and L. Sailer, "Informant accuracy in social network data IV: A comparison of clique-level structure in behavioral and cognitive network data", Social Networks, Vol. 2, 1980, pp. 191-218.
[32] S. R. Sundaresan, I. R. Fischhoff, J. Dushoff, and D. I. Rubenstein, "Network metrics reveal differences in social organization between two fission–fusion species, Grevy’s zebra and onager", Oecologia, Vol. 151, 2007, pp. 140-149.
[33] E. Zitzler and L. Thiele, "Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach", IEEE Transactions on Evolutionary Computation, Vol. 3, No. 4, 1999, pp. 257-271.
[34] V. Hajipour, E. Mehdizadeh, and R. Tavakkoli-Moghaddam, “A novel Pareto-based multi-objective vibration damping optimization algorithm to solve multi-objective optimization problems”, Scientia Iranica, Vol. 21, No. 6, 2014, pp. 2368–2378.
[35] B. Golpalsamy, B. Mondal, and S. Ghosh, “Taguchi method and ANOVA: An approach for process parameters optimization of hard machining while machining hardened steel”, Journal of Scientific & Industrial Research, Vol. 68, 2009, pp. 686-695.
[36] S.H.A. Rahmati, V. Hajipour, and S.T.A. Niaki, “A soft-computing Pareto-based meta-heuristic algorithm for a multi-objective multi-server facility location problem”, Applied Soft Computing, Vol. 13, 2013, pp. 1728-1740.
[37] J. Gao, R. Chen, W. Deng, “An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem”, International Journal of Production Research, Vol. 51, No. 3, 2013, pp. 641-651.
