A New Approach to Community Detection in Complex Networks by Using Memetic Algorithms

A New Approach to Community Detection in Complex Networks by Using Memetic Algorithms

Ali Ghorbanian Mehdi Neyestani 

Department of Industrial Engineering, Esfarayen University of technology, Iran, North Khorasan 96619-98195

Department of Electrical Engineering, Esfarayen University of technology, North Khorasan 96619-98195

Corresponding Author Email: 
ali.ghorbanian83@gmail.com, m.Neyestani@esfarayen.ac.ir
Page: 
384-406
|
DOI: 
https://doi.org/10.18280/ama_a.540301
Received: 
26 December 2017
|
Accepted: 
4 January 2018
|
Published: 
30 September 2017
| Citation

OPEN ACCESS

Abstract: 

Nowadays, networks are widely used to show the structure and type of relationship in various fields of science including social sciences, engineering, and social network. Investigating the structure of these networks has always been of interest to many people. To this end, the present study tries to identify these networks as interconnected communities, while each community might have unique properties. In this regard various methods and algorithms with different evaluation criteria are used, with the evolutionary algorithm having the highest share. The present research attempts to introduce a relatively efficient method for community detection through introduction of a new evaluation criterion based on the modularity density and giving weight to the relationships between nodes in the unweighted networks. For this purpose, at first we propose a new modularity based on difference of weight of nodes in a same community with other community also for this we propose a method for calculation weight between nodes in a same community named α_ij and between nodes in different community named β_ij. And employing this new modularity as the evaluation criteria by using Memetic Algorithm(MA). The proposed algorithms are evaluated in very complex artificial and real networks and the results were analyzed and were compared to other algorithms. For accuracy of the algorithm the number of communities is identified also Adjusted Rand Index (ARI) and Normalized Mutual Information (NMI) criteria are used to evaluate the algorithm. The obtained results indicated that MA based on new density is effective and efficient at detecting the community structure in complex real and artificial networks.

Keywords: 

Complex networks, Modularity density, Memetic algorithm, Unweighted networks

1. Introductions
2. Modularity Density
3. Genetic and Memetic Algorithm
4. Adjusting Parameter’s Algorithms
5. Examining the Results
6. Results
7. Conclusion
  References

1. S. Fortunato, Community detection in graphs, 2010, Physics Reports, vol. 486, no. 3–5, pp. 75–174.

2. M. Girvan, M. Newman, Community structure in social and biological networks, 2002, Proceedings of the National Academy of Sciences of the United States of America, vol. 99, no. 12, pp. 7821–7826.

3. S. H. Strogatz, Exploring complex networks, 2001, Nature, vol. 410, no. 6825, pp. 268–76. 

4. Ben Sheldon, Community Detection Algorithms: A comparative evaluation on artificial and real-world networks, 2010.

5. M. Newman, Detecting community structure in networks, The European Physical Journal B – Condensed Matter, vol. 83, no. 2, pp. 823–883.

6. M. Newman, Finding community structure in networks using the eigenvectors of matrices, Physical Review E, no. 2, pp. 3–5.

7. Q. Yan, L. Wu, L. Zheng, Social Network Based Microblog User Behavior Analysis, 2013, Physica A: Statistical Mechanics and Its Applications, vol. 392, no. 7, pp. 1712-1723.

8. X. Zhang, J. Zhu, Skeleton of weighted social network, 2013, Physica A: Statistical Mechanics and its Applications, vol. 392, no. 6, pp.1547-1556

9. A. Beach, M. Gartrell, R. Han, August. Solutions to security and privacy issues in mobile social networking, 2009, Computational Science and Engineering, CSE'09, International Conference on, Vol. 4, pp. 1036-1042.

10. M. Salama, M. Panda, Y. Elbarawy, A. Hassanien and A. Abraham, Computational Social Networks: Security and Privacy, 2012, Springer Verlag, vol. 2, pp. 3-21.

11. A. Abraham, A. E. Hassanien, (Eds.). Computational Social Networks: Tools, 2012, Perspectives and Applications. Springer Science & Business Media.

12. M. C. Caschera, F. Ferri, P. Grifoni, SIM: A dynamic multidimensional visualization method for social networks, 2008, PsychNology Journal, vol. 6, no. 3, pp. 291-320.

13. U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, D. Wagner, On modularity clustering, 2008, IEEE Trans. Knowl. Data Eng. vol. 20, no. 2, pp. 172–188.

14. J. Eustace, X. Wang, Y. Cui, Community detection using local neighborhood in complex networks, 2015, Physica A: Statistical Mechanics and its Applications, vol. 436, pp. 665-677.

15. J. Xiang, Hu, T., Y. Zhang, K. Hu, J. M. Li, X. K. Xu, Chen, S. Local modularity for community detection in complex networks, 2016, Physica A: Statistical Mechanics and its Applications, vol. 443, 451-459.

16. B. Saoud, A. Moussaoui, Community detection in networks based on minimum spanning tree and modularity, 2016, Physica A: Statistical Mechanics and its Applications, vol. 460, 230-234.

17. Y. M. ElBarawy, R. F. Mohamed, N. I. Ghali, Improving social network community detection using DBSCAN algorithm, 2014, Computer Applications & Research (WSCAR), 2014 World Symposium on, pp. 1-6.

18. N. Aston, W. Hu, Community detection in dynamic social networks, 2014, Communications and Network.

19. Y. Li, G. Liu, S. Y. Lao, A genetic algorithm for community detection in complex networks, 2013, Journal of Central South University, vol. 20, no. 5, pp. 1269-1276.

20. Z. Li, J. Liu, A multi-agent genetic algorithm for community detection in complex networks, 2016, Physica A: Statistical Mechanics and its Applications, vol. 449, 336-347.

21. L.M. Naeni, R. Berretta, P. Moscato, MA-Net: A reliable memetic algorithm for community detection by modularity optimization, 2015, Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems, vol. 1, Springer, pp. 311–323

22. T.N. Bui, B.R. Moon, Genetic algorithm and graph partitioning, 1996, IEEE Trans. Comput. vol. 45, no. 7, pp. 841–855.

23. M. Tasgin, A. Herdagdelen, H. Bingol, Community detection in complex networks using genetic algorithms. ArXiv preprint arXiv:0711.0491

24. C. Pizzuti, Ga-net: A genetic algorithm for community detection in social networks, 2008, Parallel Problem Solving from Nature–PPSN X, Springer, pp. 1081–1090.

25. R. Shang, J. Bai, L. Jiao, C. Jin, Community detection based on modularity and an improved genetic algorithm, 2013, Physica A: Statistical Mechanics and its Applications, vol. 392, no. 5, pp. 1215-1231. 

26. Y. Zhao, W. Jiang, S. Li, Y. Ma, G. Su, X. Lin, A cellular learning automata based algorithm for detecting community structure in complex networks, 2015, Neurocomputing, vol. 151, pp. 1216-1226. 

27. M. R. Mirsaleh, M. R.  Meybodi, A Michigan memetic algorithm for solving the community detection problem in complex network. Neurocomputing, 2016, vol. 214, 535-545. 

28. S. Fortunato, M. Barthelemy, Resolution limit in community detection, 2007, Proceedings of the National, pp. 1–8.

29. Z. Li, S. Zhang, R.-S. Wang, X.-S. Zhang, L. Chen, Quantitative function for community detection, 2008, Physical Review E, vol. 77, no. 3, p. 036109.

30. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Reading, 1989, MA: Addison-Wesley.

31. R. Dawkins, The Selfish Gene, 1976, Oxford, U.K.: Oxford Univ. Press.

32. P. Merz, B. Freisleben, Fitness landscape analysis and memetic algorithms for the quadratic assignment problem, 2000, IEEE Trans. Evol. Comput., vol. 4, no. 4, pp. 337–352.

33. P. Moscato, On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms, Memetic Algorithms' Home Page, http://www.densis.fee.unicamp.br/~moscato/memetic_home.html.

34. F. Herrera, N. Krasnogor and Daniel Molina, Real-Coded Memetic Algorithms with Crossover Hill-Climbing, 2004, Evolutionary Computation, vol. 12, no. 3, pp. 273-302.

35.  A. Caponio, G. L. Cascella, F. Neri, N. Salvatore, M. Sumner, A fast adaptive memetic algorithm for off-line and on-line control design of PMSM drives, IEEE Trans. on Systems, Feb. 2007, Man and Cybernetics – Part B, Special Issue on Memetic Algorithms, vol. 37, no. 1, pp. 28-41.

36. Y.-J. Park and M.-S. Song, A genetic algorithm for clustering problem, 1998, ACGP98, pp. 568–575.

37. C. Shi, Z. Yan, Y. Cai, B. Wu, Multi-objective community detection in complex networks, 2012, Applied Soft Computing Journal, vol. 12, no. 2, pp. 850–859.

38. L. Hubert, P. Arabie, Comparing partitions. Journal of classification, 1985, vol. 2, no. 1, pp. 193-218.

39. A. Clauset, M. E. Newman, C. Moore, Finding community structure in very large networks, 2004, Physical review E, vol. 70, no. 6, pp. 066111.

40. M. Gong, B. Fu, L. Jiao, H. Du, Memetic algorithm for community detection in networks, 2011, Physical Review E, vol. 84, no. 5, pp. 056101.

41. Pizzuti, C. GA-Net: A Genetic Algorithm for Community Detection in Social Networks, 2008, PPSN, pp. 1081-1090.

42. C. Shi, Z. Yan, Y. Cai, B. Wu, Multi-objective community detection in complex networks, 2012, Applied Soft Computing, vol. 12, no. 2, pp. 850-859.

43. C. Pizzuti, A multiobjective genetic algorithm to find communities in complex networks, 2012, IEEE Transactions on Evolutionary Computation, vol. 16, no. 3, pp. 418-430.

44. M. Gong, L. Ma, Q. Zhang, L. Jiao, Community detection in networks by using multiobjective evolutionary algorithm with decomposition, 2012, Physica A: Statistical Mechanics and its Applications, vol. 391, no. 15, pp. 4050-4060.