- Title
- M-Link: a link clustering memetic algorithm for overlapping community detection
- Creator
- Gabardo, Ademir C.; Berretta, Regina; Moscato, Pablo
- Relation
- Memetic Computing Vol. 12, Issue 2, p. 87-99
- Publisher Link
- http://dx.doi.org/10.1007/s12293-020-00300-x
- Publisher
- Springer
- Resource Type
- journal article
- Date
- 2020
- Description
- 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.
- Subject
- overlapping community detection; memetic algorithm; evolutionary algorithms; community detection
- Identifier
- http://hdl.handle.net/1959.13/1438957
- Identifier
- uon:40778
- Identifier
- ISSN:1865-9284
- Language
- eng
- Reviewed
- Hits: 729
- Visitors: 723
- Downloads: 1
| Thumbnail | File | Description | Size | Format |
|---|