M-Link: a link clustering memetic algorithm for overlapping community detection
| Autor: | Pablo Moscato, Ademir Cristiano Gabardo, Regina Berretta |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
0209 industrial biotechnology
Control and Optimization General Computer Science Computer science Population structure Complex system Community structure 02 engineering and technology Mutual information computer.software_genre Partition (database) 020901 industrial engineering & automation 0202 electrical engineering electronic engineering information engineering Memetic algorithm 020201 artificial intelligence & image processing Data mining Cluster analysis computer Label propagation |
| Zdroj: | Memetic Computing. 12:87-99 |
| ISSN: | 1865-9292 1865-9284 |
| DOI: | 10.1007/s12293-020-00300-x |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink