Top

Neural Computing and Applications

Published in:

06-09-2019 | Original Article

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

Authors: Ranjan Kumar Behera, Debadatta Naik, Santanu Kumar Rath, Ramesh Dharavath

Published in: Neural Computing and Applications | Issue 13/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article A novel error-output recurrent neural network model for time series forecasting

next article Optimal quasi-synchronization of fractional-order memristive neural networks with PSOA

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

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

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

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

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 CrossRef

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 MathSciNetCrossRefMATH

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

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 CrossRef

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

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

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 MathSciNetCrossRefMATH

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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 CrossRef

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–2466CrossRef

39.

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

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 CrossRef

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 MathSciNetCrossRef

45.

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

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 CrossRef

Title: Genetic algorithm-based community detection in large-scale social networks
Authors: Ranjan Kumar Behera
Debadatta Naik
Santanu Kumar Rath
Ramesh Dharavath
Publication date: 06-09-2019
Publisher: Springer London
Published in: Neural Computing and Applications / Issue 13/2020
Print ISSN: 0941-0643
Electronic ISSN: 1433-3058
DOI: https://doi.org/10.1007/s00521-019-04487-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 13/2020

An improved SIFT algorithm for robust emotion recognition under various face poses and illuminations

Adversarial frontier stitching for remote neural network watermarking

Deep-PHURIE: deep learning based hurricane intensity estimation from infrared satellite imagery

A new discriminative collaborative representation-based classification method via l2 regularizations

Applying several machine learning approaches for prediction of unconfined compressive strength of stabilized pond ashes

A whale optimization algorithm-trained artificial neural network for smart grid cyber intrusion detection

Premium Partner