nach oben

Social Network Analysis and Mining

Erschienen in:

01.12.2020 | Original Article

A novel iterated greedy algorithm for detecting communities in complex network

verfasst von: Wenquan Li, Qinma Kang, Hanzhang Kong, Chao Liu, Yunfan Kang

Erschienen in: Social Network Analysis and Mining | Ausgabe 1/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Community structure is one of the most important properties in complex networks. Detecting such communities plays an important role in a wide range of applications such as information sharing and diffusion, recommendation, and classification. In this paper, we propose a novel iterated greedy algorithm for detecting communities in complex networks. The algorithm is based on an iterative process that combines a destruction phase and a reconstruction phase. During the destruction phase, the algorithm destructs community indexes of a certain percent nodes having lower modularity contribution. In the reconstruction phase, their community indexes are reconstructed using the well-known Louvain construction heuristic. A local search procedure can be applied after the reconstruction phase to improve the performance of the algorithm. Experiments on the computer-generated networks and real-world networks show that our algorithm is very efficient and competitive compared with several state-of-the-art methods.

Vorheriger Artikel A classification approach to link prediction in multiplex online ego-social networks

Nächster Artikel Core expansion: a new community detection algorithm based on neighborhood overlap

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Agarwal G, Kempe D (2008) Modularity-maximizing graph communities via mathematical programming. Eur Phys J B 66:409–418MathSciNetCrossRef

Asmi K, Lotfi D, El Marraki M (2017) Large-scale community detection based on a new dissimilarity measure. Soc Netw Anal Min 7:17. https://doi.org/10.1007/s13278-017-0436-3CrossRef

Baird D, Ulanowicz RE (1989) The seasonal dynamics of the Chesapeake bay ecosystem. Ecol Monogr 59:329–364. https://doi.org/10.2307/1943071CrossRef

Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech 2008:155–168CrossRef

Boettcher S, Percus AG (2001) Optimization with extremal dynamics. Phys Rev Lett 86:5211–5214. https://doi.org/10.1103/PhysRevLett.86.5211CrossRefMATH

Brandes U, Delling D, Gaertler M, Gorke R, Hoefer M, Nikoloski Z, Wagner D (2007) On modularity clustering. IEEE Trans Knowl Data Eng 20:172–188CrossRef

Cao C, Ni Q, Zhai Y (2015) A novel community detection method based on discrete particle swarm optimization algorithms in complex networks. In: Evolutionary computation, pp 171–178

Chaabani Y, Akaichi J (2017) Meaningful communities detection in medias network. Soc Netw Anal Min 7:11. https://doi.org/10.1007/s13278-017-0430-9CrossRef

Clauset A, Newman ME, Moore C (2004) Finding community structure in very large networks. Phys Rev E Stat Nonlinear Soft Matter Phys 70:066111CrossRef

Danon L, Díazguilera A, Duch J, Arenas A (2005) Comparing community structure identification. J Stat Mech 2005:09008CrossRef

Duch J, Arenas A (2005) Community detection in complex networks using extremal optimization. Phys Rev E Stat Nonlinear Soft Matter Phys 72:027104CrossRef

Fanjul-Peyro L, Ruiz R (2010) Iterated greedy local search methods for unrelated parallel machine scheduling. Eur J Oper Res Int J 207:55–69. https://doi.org/10.1016/j.ejor.2010.03.030MathSciNetCrossRefMATH

Fortunato S (2010) Community detection in graphs. Phys Rep 486:75–174MathSciNetCrossRef

Ghalmane Z, Hassouni ME, Cherifi H (2019) Immunization of networks with non-overlapping community structure. Soc Netw Anal Min 9:45. https://doi.org/10.1007/s13278-019-0591-9CrossRef

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

Guimerà R, Amaral LAN (2005) Functional cartography of complex metabolic networks. Nature 433:895CrossRef

Guimerã R, Danon L, Dã-Az-Guilera A, Giralt F, Arenas A (2003) Self-similar community structure in a network of human interactions. Phys Rev E Stat Nonlinear Soft Matter Phys 68:065103CrossRef

Kang Q, He H, Song H (2011) Task assignment in heterogeneous computing systems using an effective iterated greedy algorithm. J Syst Softw 84:985–992CrossRef

Lancichinetti A, Fortunato S (2009) Community detection algorithms: a comparative analysis. Phys Rev E Stat Nonlinear Soft Matter Phys 80:056117CrossRef

Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E Stat Nonlinear Soft Matter Phys 78:046110CrossRef

Liu X, Wang WJ, He DX, Jiao PG, Jin D, Cannistraci CV (2017) Semi-supervised community detection based on non-negative matrix factorization with node popularity. Inf Sci 381:304–321. https://doi.org/10.1016/j.ins.2016.11.028CrossRef

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: can geographic isolation explain this unique trait? Behav Ecol Sociobiol 54:396–405CrossRef

Mrvar A, Batagelj V (2006) Example data sets released with the Pajek software. http://vlado.fmf.uni-lj.si/pub/networks/pajek/data/gphs.htm. Accessed 26 June 2018

Newman MEJ (2001) The structure of scientific collaboration networks. Proc Natl Acad Sci USA 98:404–409. https://doi.org/10.1073/pnas.021544898MathSciNetCrossRefMATH

Newman ME (2004) Fast algorithm for detecting community structure in networks. Phys Rev E Stat Nonlinear Soft Matter Phys 69:066133CrossRef

Newman ME (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E Stat Nonlinear Soft Matter Phys 74:036104MathSciNetCrossRef

Newman MEJ (2013) Network data form Mark Newman’s homepage. http://www-personal.umich.edu/~mejn/netdata. Accessed 19 Apr 2018

Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E. https://doi.org/10.1103/PhysRevE.69.026113CrossRef

Noack A, Rotta R (2009) Multi-level algorithms for modularity clustering. In: International symposium on experimental algorithms, pp 257–268

Pagnozzi F (2017) An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem. Elsevier, AmsterdamMATH

Pan QK, Ruiz R (2014) An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem. Omega Int J Manag Sci 44:41–50. https://doi.org/10.1016/j.omega.2013.10.002CrossRef

Pons P, Latapy M (2005) Computing communities in large networks using random walks. In: Yolum P, Gungor T, Gurgen F, Ozturan C (eds) Computer and information sciences—Iscis 2005, proceedings. Lecture notes in computer science, vol 3733. Springer, Berlin, pp 284–293CrossRef

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

Ranjbar A, Maheswaran M (2014) Using community structure to control information sharing in online social networks. Comput Commun 41:11–21CrossRef

Rossi RA, Ahmed NK, AAAI (2015) The network data repository with interactive graph analytics and visualization. In: Proceedings of the twenty-ninth AAAI conference on artificial intelligence

Rosvall M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci USA 105:1118–1123CrossRef

Rotta R, Noack A (2011) Multilevel local search algorithms for modularity clustering. J Exp Algorithm 16:2(3)MathSciNetCrossRef

Ruiz R, Stutzle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res Int J 177:2033–2049. https://doi.org/10.1016/j.ejor.2005.12.009CrossRefMATH

Said A, Abbasi RA, Maqbool O, Daud A, Aljohani NR (2018) CC-GA: a clustering coefficient based genetic algorithm for detecting communities in social networks. Appl Soft Comput 63:59–70. https://doi.org/10.1016/j.asoc.2017.11.014CrossRef

Sanchez-Oro J, Duarte A (2018) Iterated greedy algorithm for performing community detection in social networks. Future Gener Comput Syst 88:785–791. https://doi.org/10.1016/j.future.2018.06.010CrossRef

Shi C, Wang Y, Wu B, Zhong C (2009) A new genetic algorithm for community detection. In: Complex sciences, first international conference, complex 2009, Shanghai, China, February 23–25, 2009. Revised papers, 2009, pp 1298–1309

Stutzle T (2006) Iterated local search for the quadratic assignment problem. Eur J Oper Res Int J 174:1519–1539. https://doi.org/10.1016/j.ejor.2005.01.066MathSciNetCrossRefMATH

Tchuente D, Canut M-F, Jessel N, Peninou A, Sèdes F (2013) A community-based algorithm for deriving users’ profiles from egocentrics networks: experiment on Facebook and DBLP. Soc Netw Anal Min 3:667–683. https://doi.org/10.1007/s13278-013-0113-0CrossRef

Wang RS, Zhang S, Wang Y, Zhang XS, Chen L (2008) Clustering complex networks and biological networks by nonnegative matrix factorization with various similarity measures. Neurocomputing 72:134–141CrossRef

Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393:440–442CrossRef

Wellman B (2005) The development of social network analysis: a study in the sociology of science, vol 27. Linton C. Freeman Social Networks, Vancouver, pp 275–282

Yang J, Leskovec J (2012) Defining and evaluating network communities based on ground-truth. Knowl Inf Syst 42:181–213CrossRef

Yang Z, Algesheimer R, Tessone CJ (2017) A comparative analysis of community detection algorithms on artificial networks (vol 6, 30750, 2017). Sci Rep 7:2. https://doi.org/10.1038/srep46845CrossRef

Ye Z, Hu S, Yu J (2008) Adaptive clustering algorithm for community detection in complex networks. Phys Rev E Stat Nonlinear Soft Matter Phys 78:046115MathSciNetCrossRef

Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33:452–473CrossRef

Titel: A novel iterated greedy algorithm for detecting communities in complex network
verfasst von: Wenquan Li
Qinma Kang
Hanzhang Kong
Chao Liu
Yunfan Kang
Publikationsdatum: 01.12.2020
Verlag: Springer Vienna
Erschienen in: Social Network Analysis and Mining / Ausgabe 1/2020
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-020-00641-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2020

Optimal control of a delayed rumor propagation model with saturated control functions and -type objectives

Design and development of a friendly user interface for building social network traceability system

t-PINE: tensor-based predictable and interpretable node embeddings

Nonlinear dynamic information propagation mathematic modeling and analysis based on microblog social network

Good and bad events: combining network-based event detection with sentiment analysis

Ranking and grouping social media requests for emergency services using serviceability model

Premium Partner