Skip to main content

Advertisement

SpringerLink
Log in

Genetic algorithm-based community detection in large-scale social networks

  • Original Article
  • Published:
Neural Computing and Applications Aims and scope Submit manuscript

Abstract

Communities in social networks are the essential feature which may be considered as a potential parameter in modeling the behavior of the social entities. Detection of communities has attracted a lot of attention in research in social network analysis. It is one of the major challenging problems as it involves high complexity in processing complex web structure. In fact, this problem can be considered as a NP-complete problem in large-scale networks, as this problem is somewhat reducible to the clique problem in graph theory. A number of meta-heuristic algorithms have been proposed to explore the hidden communities. Most of these algorithms have considered the modularity of the network as their objective function. But, the aspect of optimizing the value of modularity is associated with a problem known as resolution limit, where the size of the detected communities depends on the number of edges existing in the network. In this paper, a genetic algorithm-based community detection has been proposed where an efficient single objective function based on similarity matrix has been devised. The similarity index between each pair of nodes has been calculated in a distributed manner over multiple computing nodes. Similarity index proposed in this paper is based on the topological structure of the network. The effectiveness of the proposed approach is examined by comparing the performance with other state-of-the-art community detection algorithms applied over some real-world network datasets.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. Nussbaum R, Esfahanian AH, Tan PN (2013) Clustering social networks using distance-preserving subgraphs. In: The influence of technology on social network analysis and mining. Springer, Vienna, pp 331–349. https://doi.org/10.1007/978-3-7091-1346-2_14

  2. Fortunato S (2010) Community detection in graphs. Phys Rep 486(3–5):75–174. https://doi.org/10.1016/j.physrep.2009.11.002

    Article  MathSciNet  Google Scholar 

  3. Newman ME (2004) Analysis of weighted networks. Phys Rev E 70(5):056131. https://doi.org/10.1103/PhysRevE.70.056131

    Article  Google Scholar 

  4. Newman ME (2013) Spectral methods for community detection and graph partitioning. Phys Rev E 88(4):042822. https://doi.org/10.1103/PhysRevE.88.042822

    Article  Google Scholar 

  5. Girvan M, Newman ME (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826. https://doi.org/10.1073/pnas.122653799

    Article  MathSciNet  MATH  Google Scholar 

  6. Pons P, Latapy M (2005) Computing communities in large networks using random walks. In: International symposium on computer and information sciences. Springer, Berlin, pp 284–293. https://doi.org/10.1007/11569596_31

  7. Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76(3):036106. https://doi.org/10.1103/PhysRevE.76.036106

    Article  Google Scholar 

  8. De Meo P, Ferrara E, Fiumara G, Provetti A (2011) Generalized louvain method for community detection in large networks. In: 2011 11th international conference on intelligent systems design and applications (ISDA). IEEE, pp 88–93. https://doi.org/10.1109/isda.2011.6121636

  9. Newman ME (2006) Modularity and community structure in networks. Proc Natl Acad Sci 103(23):8577–8582. https://doi.org/10.1073/pnas.0601602103

    Article  Google Scholar 

  10. Newman ME (2004) Fast algorithm for detecting community structure in networks. Phys Rev E 69(6):066133. https://doi.org/10.1103/PhysRevE.69.066133

    Article  Google Scholar 

  11. Qi GJ, Aggarwal CC, Huang T (2012) Community detection with edge content in social media networks. In: 2012 IEEE 28th international conference on data engineering (ICDE). IEEE, pp 534–545. https://doi.org/10.1109/icde.2012.77

  12. Clauset A, Newman ME, Moore C (2004) Finding community structure in very large networks. Phys Rev E 70(6):066111. https://doi.org/10.1103/PhysRevE.70.066111

    Article  Google Scholar 

  13. Pizzuti C (2008) Ga-net: a genetic algorithm for community detection in social networks. In: International conference on parallel problem solving from nature. Springer, Berlin, pp 1081–1090. https://doi.org/10.1007/978-3-540-87700-4_107

  14. Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D (2004) Defining and identifying communities in networks. Proc Natl Acad Sci 101(9):2658–2663. https://doi.org/10.1073/pnas.0400054101

    Article  Google Scholar 

  15. Zhang P, Wang J, Li X, Li M, Di Z, Fan Y (2008) Clustering coefficient and community structure of bipartite networks. Phys A 387(27):6869–6875. https://doi.org/10.1016/j.physa.2008.09.006

    Article  Google Scholar 

  16. Jin D, He D, Liu D, Baquero C (2010) Genetic algorithm with local search for community mining in complex networks. In: 2010 22nd IEEE international conference on tools with artificial intelligence (ICTAI), vol 1, pp 105–112. IEEE. https://doi.org/10.1109/ictai.2010.23

  17. Chira C, Gog A (2011) Collaborative community detection in complex networks. In: International conference on hybrid artificial intelligence systems. Springer, Berlin, pp 380–387. https://doi.org/10.1007/978-3-642-21219-2_48

  18. Gong M, Fu B, Jiao L, Du H (2011) Memetic algorithm for community detection in networks. Phys Rev E 84(5):056101. https://doi.org/10.1103/PhysRevE.84.056101

    Article  Google Scholar 

  19. Gong M, Cai Q, Li Y, Ma J (2012) An improved memetic algorithm for community detection in complex networks. In: 2012 IEEE Congress on evolutionary computation (CEC). IEEE, pp 1–8. https://doi.org/10.1109/cec.2012.6252971

  20. Jia G, Cai Z, Musolesi M, Wang Y, Tennant DA, Weber RJ, Heath JK, He S (2012) Community detection in social and biological networks using differential evolution. In: Learning and intelligent optimization. Springer, Berlin, pp 71–85. https://doi.org/10.1007/978-3-642-34413-8_6

  21. Shang R, Bai J, Jiao L, Jin C (2013) Community detection based on modularity and an improved genetic algorithm. Phys A 392(5):1215–1231. https://doi.org/10.1016/j.physa.2012.11.003

    Article  Google Scholar 

  22. Liu D, Jin D, Baquero C, He D, Yang B, Yu Q (2013) Genetic algorithm with a local search strategy for discovering communities in complex networks. Int J Comput Intell Syst 6(2):354–369. https://doi.org/10.1080/18756891.2013.773175

    Article  Google Scholar 

  23. Shi C, Cai Y, Fu D, Dong Y, Wu B (2013) A link clustering based overlapping community detection algorithm. Data Knowl Eng 87:394–404. https://doi.org/10.1016/j.datak.2013.05.004

    Article  Google Scholar 

  24. Zadeh PM, Kobti Z (2015) A multi-population cultural algorithm for community detection in social networks. Procedia Comput Sci 52:342–349. https://doi.org/10.1016/j.procs.2015.05.105

    Article  Google Scholar 

  25. Gupta S, Mittal S, Gupta T, Singhal I, Khatri B, Gupta AK, Kumar N (2017) Parallel quantum-inspired evolutionary algorithms for community detection in social networks. Appl Soft Comput 61:331–353. https://doi.org/10.1016/j.asoc.2017.07.035

    Article  Google Scholar 

  26. Zhang L, Pan H, Su Y, Zhang X, Niu Y (2017) A mixed representation-based multiobjective evolutionary algorithm for overlapping community detection. IEEE Trans Cybern 47(9):2703–2716. https://doi.org/10.1109/TCYB.2017.2711038

    Article  Google Scholar 

  27. Guerrero M, Montoya FG, Baños R, Alcayde A, Gil C (2017) Adaptive community detection in complex networks using genetic algorithms. Neurocomputing 266:101–113. https://doi.org/10.1016/j.neucom.2017.05.029

    Article  Google Scholar 

  28. Wen X, Chen WN, Lin Y, Gu T, Zhang H, Li Y, Yin Y, Zhang J (2017) A maximal clique based multiobjective evolutionary algorithm for overlapping community detection. IEEE Trans Evol Comput 21(3):363–377. https://doi.org/10.1109/TEVC.2016.2605501

    Article  Google Scholar 

  29. Guendouz M, Amine A, Hamou RM (2017) A discrete modified fireworks algorithm for community detection in complex networks. Appl Intell 46(2):373–385. https://doi.org/10.1007/s10489-016-0840-9

    Article  Google Scholar 

  30. Chen J, Wang H, Wang L, Liu W (2016) A dynamic evolutionary clustering perspective: community detection in signed networks by reconstructing neighbor sets. Phys A 447:482–492. https://doi.org/10.1016/j.physa.2015.12.006

    Article  MathSciNet  MATH  Google Scholar 

  31. Ju Y, Zhang S, Ding N, Zeng X, Zhang X (2016) Complex network clustering by a multi-objective evolutionary algorithm based on decomposition and membrane structure. Sci Rep 6:33870. https://doi.org/10.1038/srep33870

    Article  Google Scholar 

  32. Rani S, Mehrotra M (2018) A hybrid bat algorithm for community detection in social networks. In: International conference on intelligent systems design and applications. Springer, Cham, pp 943–954. https://doi.org/10.1007/978-3-030-16660-1_92

  33. Behera R, Rath S, Misra S, Damaševičius R, Maskeliūnas R (2017) Large scale community detection using a small world model. Appl Sci 7(11):1173. https://doi.org/10.3390/app7111173

    Article  Google Scholar 

  34. Ji Z, Pi H, Wei W, Xiong B, Woźniak M, Damasevicius R (2019) Recommendation based on review texts and social communities: a hybrid model. IEEE Access 7:40416–40427. https://doi.org/10.1109/ACCESS.2019.2897586

    Article  Google Scholar 

  35. Azaouzi M, Rhouma D, Romdhane LB (2019) Community detection in large-scale social networks: state-of-the-art and future directions. Soc Netw Anal Min 9(1):23. https://doi.org/10.1007/s13278-019-0566-x

    Article  Google Scholar 

  36. Moscovici S (1988) Notes towards a description of social representations. Eur J Soc Psychol 18(3):211–250. https://doi.org/10.1002/ejsp.2420180303

    Article  Google Scholar 

  37. Pan Y, Li DH, Liu JG, Liang JZ (2010) Detecting community structure in complex networks via node similarity. Phys A 389(14):2849–2857. https://doi.org/10.1016/j.physa.2010.03.006

    Article  Google Scholar 

  38. Hunter PR, Gaston MA (1988) Numerical index of the discriminatory ability of typing systems: an application of Simpson’s index of diversity. J Clin Microbiol 26(11):2465–2466

    Article  Google Scholar 

  39. Hamers L (1989) Similarity measures in scientometric research: the Jaccard index versus Salton’s cosine formula. Inf Process Manag 25(3):315–318

    Article  Google Scholar 

  40. Blogs network dataset-KONECT, October 2016. https://doi.org/10.1145/1134271.1134277

  41. Chicago network dataset-KONECT, October 2016. http://konect.uni-koblenz.de/networks/tntp-ChicagoRegiona

  42. Lusseau D, Schneider K, Boisseau OJ, Haase P, Slooten E, Dawson SM (2003) The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behav Ecol Sociobiol 54(4):396–405. https://doi.org/10.1007/s00265-003-0651-y

    Article  Google Scholar 

  43. Leskovec J, Mcauley JJ (2012) Learning to discover social circles in ego networks. In: Advances in neural information processing systems, pp 539–547. http://dx.doi.org/10.1145/2556612

  44. Newman ME (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E 74(3):036104. https://doi.org/10.1103/PhysRevE.74.036

    Article  MathSciNet  Google Scholar 

  45. Danon L, Diaz-Guilera A, Duch J, Arenas A (2005) Comparing community structure identification. J Stat Mech: Theory Exp 2005(09):P09008

    Article  Google Scholar 

  46. Krieger AM, Green PE (1999) A generalized Rand-index method for consensus clustering of separate partitions of the same data base. J Classif 16(1):63–89. https://doi.org/10.1007/s003579900043

    Article  Google Scholar 

Download references

Acknowledgements

This research work was supported by Fund for Improvement of S&T Infrastructure in Universities and Higher Educational Institutions (FIST) scheme with a Grant No. SR/FST/ETI-359/2014 under Department of Science and Technology, Govt. of India. The authors wish to express their gratitude and heartiest thanks to the Department of Computer Science and Engineering, Indian Institute of Technology (ISM), Dhanbad, India, for providing their research support.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, National Institute of Technology, Rourkela, 769008, India

    Ranjan Kumar Behera, Santanu Kumar Rath & Ramesh Dharavath

  2. Department of Computer Science and Engineering, Indian Institute of Technology (ISM), Dhanbad, 769008, India

    Debadatta Naik

Authors
  1. Ranjan Kumar Behera
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Debadatta Naik
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Santanu Kumar Rath
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ramesh Dharavath
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ramesh Dharavath.

Ethics declarations

Conflict of interest

The authors do not have any conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Behera, R.K., Naik, D., Rath, S.K. et al. Genetic algorithm-based community detection in large-scale social networks. Neural Comput & Applic 32, 9649–9665 (2020). https://doi.org/10.1007/s00521-019-04487-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00521-019-04487-0

Keywords

Search

Navigation