Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Memetic Computing
Published in: Memetic Computing 2/2020

09-04-2020 | Regular Research Paper

M-Link: a link clustering memetic algorithm for overlapping community detection

Authors: Ademir C. Gabardo, Regina Berretta, Pablo Moscato

Published in: Memetic Computing | Issue 2/2020

Log in

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

search-config
loading …

Abstract

Graphs and networks are a useful abstraction to represent a wide range of systems. Sets of nodes that are more highly interconnected constitute a ‘community’. Community detection algorithms help to reveal a decomposition of a network in modules. These communities can overlap, and nodes can have several community memberships. We present M-Link, a memetic algorithm for overlapping community detection. It maximises an objective function called link partition density. The communities of edges obtained with this method naturally translate to overlapping communities of nodes. The method is based on local expansion and a specialised local search mechanism. Label propagation methods are used for initialising a multi-agent tertiary tree population structure. We use the normalised mutual information to evaluate the similarity between the known community structure in a collection of benchmark networks and the community structure detected by M-Link. The method outperforms other state-of-the-art algorithms for overlapping community detection and it has better accuracy and stability.
next article A probability first memetic algorithm for the dynamic multiple-fault diagnosis problem with non-ideal tests

Dont have a licence yet? Then find out more about our products and how to get one 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

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"

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
Literature
1.
Ahn YY, Bagrow JP, Lehmann S (2010) Link communities reveal multiscale complexity in networks. Nature 466(7307):761–764CrossRef
2.
Amelio A, Pizzuti C (2014) Overlapping community discovery methods: a survey. In: Social networks: analysis and case studies. Springer, Vienna, pp 105–125
3.
Baumes J, Goldberg MK, Krishnamoorthy MS, Magdon-Ismail M, Preston N (2005) Finding communities by clustering a graph into overlapping subgraphs. IADIS AC 5:97–104
4.
Berretta R, Rodrigues LF (2004) A memetic algorithm for a multistage capacitated lot-sizing problem. Int J Prod Econ 87(1):67–81CrossRef
5.
Bonacich P (1987) Power and centrality: a family of measures. Am J Sociol 92(5):1170–1182CrossRef
6.
Brandes U, Delling D, Gaertler M, Goerke R, Hoefer M, Nikoloski Z, Wagner D (2006) Maximizing modularity is hard
7.
Brandes U (2001) A faster algorithm for betweenness centrality. J Math Sociol 25(2):163–177CrossRef
8.
Derényi I, Palla G, Vicsek T (2005) Clique percolation in random networks. Phys Rev Lett 94(16):160202CrossRef
9.
Evans T, Lambiotte R (2009) Line graphs, link partitions, and overlapping communities. Phys Rev E 80(1):016105CrossRef
10.
11.
12.
Gabardo A, Berretta R, Moscato P (2019) Overlapping communities in co-purchasing and social interaction graphs: a memetic approach. In: Business and consumer analytics: new ideas. Springer, pp 435–466
13.
Girvan M, Newman ME (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826MathSciNetCrossRef
14.
Gregory S (2010) Finding overlapping communities in networks by label propagation. New J Phys 12(10):103018CrossRef
15.
Gupta P, Goel A, Lin J, Sharma A, Wang D, Zadeh R (2013) Wtf: The who to follow service at twitter. In: Proceedings of the 22nd international conference on world wide web, WWW’13. ACM, New York, NY, USA, pp 505–514
16.
Harris M, Berretta R, Inostroza-Ponta M, Moscato P (2015) A memetic algorithm for the quadratic assignment problem with parallel local search. In: 2015 IEEE congress on evolutionary computation (CEC). IEEE, Sendai, Japan, pp 838–845
17.
Hotelling H (1936) Simplified calculation of principal components. Psychometrika 1(1):27–35CrossRef
18.
Lancichinetti A, Fortunato S, Kertész J (2009) Detecting the overlapping and hierarchical community structure in complex networks. New J Phys 11(3):033015CrossRef
19.
Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78(4):046110CrossRef
20.
Liu X, Cheng HM, Zhang ZY (2019) Evaluation of community detection methods. IEEE Trans Knowl Data Eng
21.
Moscato P (2019) Business network analytics: from graphs to supernetworks. In: Moscato P, de Vries NJ (eds) Business and consumer analytics: new ideas. Springer, Berlin, pp 307–400CrossRef
22.
Moscato P, Mathieson L (2019) Memetic algorithms for business analytics and data science: a brief survey. Business and consumer analytics: new ideas. Springer, Berlin, pp 545–608CrossRef
23.
Naeni LM, Berretta R, Moscato P (2015) Ma-net: a reliable memetic algorithm for community detection by modularity optimization. In: Proceedings of the 18th Asia Pacific symposium on intelligent and evolutionary systems, volume 1. Springer, Berlin, Germany, pp 311–323
24.
Neri F, Cotta C, Moscato P (2012) Handbook of memetic algorithms, vol 379. Springer, BerlinCrossRef
25.
Newman ME (2006) Modularity and community structure in networks. Proc Natl Acad Sci 103(23):8577–8582CrossRef
26.
Palla G, Derényi I, Farkas I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043):814–818CrossRef
27.
Pizzuti C (2009) A multi-objective genetic algorithm for community detection in networks. In: IEEE 21st international conference on tools with artificial intelligence, 2009, ICTAI’09. IEEE Computer Society, Newark, pp 379–386
28.
Pizzuti C (2009) Overlapped community detection in complex networks. In: Proceedings of the 11th annual conference on genetic and evolutionary computation. ACM, ACM, New York, NY, USA, pp 859–866
29.
Shi C, Cai Y, Fu D, Dong Y, Wu B (2013) A link clustering based overlapping community detection algorithm. Data Knowl Eng 87:394–404CrossRef
30.
Spears WM, De Jong KD (1995) On the virtues of parameterized uniform crossover. Tech. rep, Naval Research Lab Washington, DC
31.
Wen X, Chen WN, Lin Y, Gu T, Zhang H, Li Y, Yin Y, Zhang J (2016) A maximal clique based multiobjective evolutionary algorithm for overlapping community detection. IEEE Trans Evol Comput 21(3):363–377
32.
Xie J, Kelley S, Szymanski BK (2013) Overlapping community detection in networks: the state-of-the-art and comparative study. ACM Comput Surv 45(4):43CrossRef
33.
Xie J, Szymanski BK (2012) Towards linear time overlapping community detection in social networks. In: Pacific-Asia conference on knowledge discovery and data mining. Springer, Springer Nature, London. pp. 25–36CrossRef
Metadata
Title
M-Link: a link clustering memetic algorithm for overlapping community detection
Authors
Ademir C. Gabardo
Regina Berretta
Pablo Moscato
Publication date
09-04-2020
Publisher
Springer Berlin Heidelberg
Published in
Memetic Computing / Issue 2/2020
Print ISSN: 1865-9284
Electronic ISSN: 1865-9292
DOI
https://doi.org/10.1007/s12293-020-00300-x

Other articles of this Issue 2/2020

Memetic Computing 2/2020 Go to the issue

Regular Research Paper

Conditioning optimization of extreme learning machine by multitask beetle antennae swarm algorithm

Regular Research Paper

Development of a multi-objective artificial tree (MOAT) algorithm and its application in acoustic metamaterials

Regular Research Paper

A comparative study between artificial bee colony (ABC) algorithm and its variants on big data optimization

Regular Research Paper

A probability first memetic algorithm for the dynamic multiple-fault diagnosis problem with non-ideal tests

Regular Research Paper

An improved multi-objective learning automata and its application in VLSI circuit design

Premium Partner

    Image Credits