- Title
- A memetic algorithm for community detection by maximising the connected cohesion
- Creator
- Haque, Mohammad Nazmul; Mathieson, Luke; Moscato, Pablo
- Relation
- 2017 IEEE Symposium Series on Computational Intelligence (SSCI). 2017 SSCI Proceedings (Honolulu, HI 27 November - 1 December, 2017) p. 2475-2482
- Relation
- Funding BodyARCGrant NumberFT120100060 http://purl.org/au-research/grants/arc/FT120100060
- Publisher Link
- http://dx.doi.org/10.1109/SSCI.2017.8285404
- Publisher
- Institute of Electrical and Electronics Engineers (IEEE)
- Resource Type
- conference paper
- Date
- 2017
- Description
- Community detection is an exciting field of research which has attracted the interest of many researchers during the last decade. While many algorithms and heuristics have been proposed to scale existing approaches a relatively smaller number of studies have looked at exploring different measures of quality of the detected community. Recently, a new score called 'cohesion' was introduced in the computing literature. The cohesion score is based comparing the number of triangles in a given group of vertices to the number of triangles only partly in that group. In this contribution, we propose a memetic algorithm that aims to find a subset of the vertices of an undirected graph that maximizes the cohesion score. The associated combinatorial optimisation problem is known to be NP-Hard and we also prove it to be W[1]-hard when parameterized by the score. We used a Local Search individual improvement heuristic to expand the putative solution. Then we removed all vertices from the group which are not a part of any triangle and expand the neighbourhood by adding triangles which have at least two nodes already in the group. Finally we compute the maximum connected component of this group. The highest quality solutions of the memetic algorithm have been obtained for four real-world network scenarios and we compare our results with ground-truth information about the graphs. We also compare the results to those obtained with eight other community detection algorithms via interrater agreement measures. Our results give a new lower bound on the parameterized complexity of this problem and give novel insights on its potential usefulness as a new natural score for community detection.
- Subject
- community detection; triangles; connected cohesion; memetic algorithm
- Identifier
- http://hdl.handle.net/1959.13/1385480
- Identifier
- uon:32234
- Identifier
- ISBN:9781538627266
- Language
- eng
- Reviewed
- Hits: 6882
- Visitors: 1701
- Downloads: 1
| Thumbnail | File | Description | Size | Format |
|---|