A memetic algorithm for community detection by maximising the connected cohesion

Haque, MN; Mathieson, L; Moscato, P

A memetic algorithm for community detection by maximising the connected cohesion

Haque, MN Mathieson, L

Moscato, P

Permalink

Publication Type:: Conference Proceeding
Citation:: 2017 IEEE Symposium Series on Computational Intelligence, SSCI 2017 - Proceedings, 2018, 2018-January pp. 1 - 8
Issue Date:: 2018-02-02

Closed Access

	Filename	Description	Size
	08285404.pdf	Published version	38.74 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Haque, MN	en_US
dc.contributor.author	Mathieson, L https://orcid.org/0000-0001-6470-2296	en_US
dc.contributor.author	Moscato, P	en_US
dc.date.issued	2018-02-02	en_US
dc.identifier.citation	2017 IEEE Symposium Series on Computational Intelligence, SSCI 2017 - Proceedings, 2018, 2018-January pp. 1 - 8	en_US
dc.identifier.isbn	9781538627259	en_US
dc.identifier.uri	http://hdl.handle.net/10453/126048
dc.description.abstract	© 2017 IEEE. 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.	en_US
dc.relation.ispartof	2017 IEEE Symposium Series on Computational Intelligence, SSCI 2017 - Proceedings	en_US
dc.relation.isbasedon	10.1109/SSCI.2017.8285404	en_US
dc.title	A memetic algorithm for community detection by maximising the connected cohesion	en_US
dc.type	Conference Proceeding
utslib.citation.volume	2018-January	en_US
utslib.for	080201 Analysis of Algorithms and Complexity	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US
pubs.volume	2018-January	en_US

Abstract:

© 2017 IEEE. 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/126048