A New Multi-Agent Bat Approach for Detecting Community Structure in Social Networks

Document Type : Original Research (Full Papers)

Authors

Faculty of Computer and Information Technology Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran

Abstract

The complex networks are widely used to demonstrate effective systems in the fields of biology and sociology. One of the most significant kinds of complex networks is social networks. With the growing use of such networks in our daily habits, the discovery of the hidden social structures in these networks is extremely valuable because of the perception and exploitation of their secret knowledge. The community structure is a great topological property of social networks, and the process to detect this structure is a challenging problem. In this paper, a new approach is proposed to detect non-overlapping community structure. The approach is based on multi-agents and the bat algorithm. The objective is to optimize the amount of modularity, which is one of the primary criteria for determining the quality of the detected communities. The results of the experiments show the proposed approach performs better than existing methods in terms of modularity.

Keywords


[1] Latora, V.; Nicosia, V.; Russo, G., Complex networks: principles,methods and applications (2017). 
[2] Chen,  G.;  Wang,  X.;  Li,  X.,  Fundamentals  of  complex  networks: models, structures and dynamics, John Wiley & Sons (2014).  
[3] Reihanian,  A.;  Feizi-Derakhshi,  M.;  Aghdasi,  H.,  "Community detection  in  social networks  with  node  attributes based  on  multi-objective  biogeography  based  optimization",  Engineering Applications of Artificial Intelligence, vol. 62, pp. 51-67 (2017). 
[4] Silva, T. C.; Zhao, L., "Machine learning in complex networks", in Springer (2016). 
[5] Ghaderi,  S.;  Abdollahpouri,  A.;  Moradi,  P.,  "On  the  modularity improvement  for  community  detection  in  overlapping  social networks",  in  IEEE  -  2016  8th  International  Symposium  on Telecommunications (IST) (2016). 
[6] Estrada,  E.,  "Introduction  to  complex  networks:  structure  and dynamics", in Evolutionary Equations with Applications in Natural Sciences, no. Springer, pp. 93-131 (2015). 
[7] Huang, J.; Yang, B.; Jin, D.; Yang, Y., "Decentralized mining social network  communities  with  agents",  Mathematical  and  Computer Modelling - Elsevier, vol. 57, no. 11-12, pp. 2998-3008 (2013). 
[8] Girvan, M.; Newman, M. E., "Community structure in social and biological  networks",  Proceedings  of  the  national  academy  of sciences, vol. 99, no. 12, pp. 7821-7826 (2002). 
[9] Cazabet, R.; Amblard, F., "Simulate to Detect: A Multi-agent System for Community Detection", in IEEE, Lyon, France (2011). 
[10] Christian  Blum,  D.  M.,  Swarm  Intelligence:  Introduction  and Applications (Natural Computing Series), Springer (2008). 
[11] Bozorg oáiciga, H. A., "Development and application of the bat algorithm for optimizing the operation of reservoir systems", Journal of Water Resources Planning and Management (2014). 
[12]  Colin, T., "A comparison of BA, GA, PSO, BP, and LM for training feed  forward  neural  networks  in  e-learning context",  International Journal of Intelligent Systems and Applications, pp. 23-29 (2012). 
[13]  Lancichinetti, A.; Fortunato, S.; Radicchi, F., "Benchmark graphs for testing community detection algorithms", Physical review E, vol. 78, no. 4, 046110 (2008). 
[14]  Newman, M. E.; Girvan, M., "Finding and evaluating community structure in  networks",  Physical review  E, vol.  69,  no.  2,  026113 (2004). 
[15]  Pizzuti, C., "GA-Net: A genetic algorithm for community detection in social networks", in International Conference on Parallel Problem Solving from Nature (2008). 
[16]  Pizzuti,  C.,  "A  multi-objective  genetic  algorithm  for  community detection  in  networks",  in  Tools  with  Artificial  Intelligence  21st International Conference (2009). 
[17]  Li, Y.; Liu, J.; Liu, C., "A comparative analysis of evolutionary and memetic  algorithms  for  community  detection  from  signed  social networks", vol. 18, no. 2, pp. 329-348 (2014). 
[18]  Li,  Z.;  Liu,  J.,  "A  multi-agent  genetic  algorithm  for  community detection in complex networks", Physica A: Statistical Mechanics and its Applications, vol. 449, pp. 336-347 (2016). 
[19]  Atay, Y.; Koc, I.; Babaoglu, I.; Kodaz, H., "Community Detection from Biological and Social Networks: A Comparative Analysis of Metaheuristic Algorithms", Applied Soft Computing (2016). 
[20]  Cazabet, R.; Amblard, F., "Simulate to detect: a multi-agent system forc  ommunity  detection",  in  IEEE/WIC/ACM  International Conferences on Web Intelligence and Intelligent Agent Technology, Lyon, France (2011). 
[21]  Hassan,  E.  A.;  Hafez,  A.  I.;  Hassanien,  A.  E.;  Fahmy,  A.  A.,  "A Discrete Bat Algorithm for the Community Detection Problem", in International Conference on Hybrid Artificial Intelligence Systems. HAIS 2015. Lecture Notes in Computer Science, vol. 9121. Springer, Cham (2015). 
[22]  Yang, X. S. , "A new meta heuristic bat-inspired algorithm," Nature inspired cooperative strategies for optimization (NISCO 2010), vol. 284, pp. 65-74, 2010. 
[23]  Yang,  X.  S.,  "Meta-heuristic  optimization  with  applications: Demonstration via bat algorithm", in Proceedings of 5th Bioinspired Optimization  Methods  and  Their  Applications  (BIOMA2012), Bohinj, Slovenia (2012). 
[24]  Yang, X. S.; Gandomi, A. H., "Bat algorithm: A novel approach for global  engineering  optimization",  in  Engineering  Computations (2012). 
[25]  Koffka, K.; Ashok, S., "A comparison of BA, GA, PSO, BP, and LM for  training  feed  forward  neural  networks  in  e-learning  context", International Journal of Intelligent Systems and Applications, vol. 7, 
p. 23–29 (2012). 
[26]  Liu,  J.;  Jing,  H.;  Tang,  Y.Y.,  "Multi-agent  oriented  constraint satisfaction",  Artificial  Intelligence,  vol.  136,  no.  1,  pp.  101-144 (2002). 
[27]  Park, Y.; Song, M., "A genetic algorithm for clustering problems", in  Proceedings  of  the  Third  Annual  Conference  on  Genetic Programming, pp. 568–575 (1998). 
[28]  Wasi Ul Kabir, Md.; Sakib, N.; Mustafizur, S.; Shafiul, M., "A Novel Adaptive Bat Algorithm to Control Explorations and Exploitations for  Continuous  Optimization  Problems",  International  Journal  of Computer Applications (0975 – 8887), vol. 94, no. 13, pp. 15-20 (2014). 
[29]  Labatut, V., "Generalised measures for the evaluation of community detection methods", International Journal of Social Network Mining, vol. 2, no. 1, pp. 44-63 (2015). 
[30]  Danon,  L.;  Diaz-Guilera,  A.;  Duch,  J.;  Arenas,  A.,  "Comparing community  structure  identification",  Journal  of  Statistical Mechanics: Theory and Experiment, no. 9, pp. 219-228 (2005). 
Volume 12, Issue 1
June 2019
Pages 47-56
  • Receive Date: 14 July 2019
  • Revise Date: 11 August 2019
  • Accept Date: 06 October 2019
  • First Publish Date: 06 October 2019