A Polymorphic Ant-Based Algorithm for Graph Clustering

Simple item page
dc.contributor.authorLiu, Ying Ying
dc.contributor.authorLiu, Ying Ying
dc.contributor.examiningcommitteeWang, Yang (Computer Science) Lui, Shaun (Mathematics)en_US
dc.contributor.supervisorThulasiraman, Parimala (Computer Science)en_US
dc.date.accessioned2016-04-12T16:11:18Z
dc.date.available2016-04-12T16:11:18Z
dc.date.issued2016
dc.degree.disciplineComputer Scienceen_US
dc.degree.levelMaster of Science (M.Sc.)en_US
dc.description.abstractIn this thesis, I introduce two new algorithms: Ant Brood Clustering-Intelligent Ants (ABC-INTE) and Ant Brood Clustering-Polymorphic Ants (ABC-POLY) for the graph clustering problem. ABC-INTE uses techniques such as hopping ants, relaxed drop function, ants with memories, stagnation control, and addition of k-means cluster retrieval process, as an improvement of the basic ABC-KLS algorithm. ABC-POLY uses two types of ants, inspired by the division of labour between the major and minor ants in Pheidole genus, as an improvement of ABC-INTE. For comparison purpose, I also implement MMAS, an ACO clustering algorithm. When tested on the benchmark networks, ABC-POLY outperforms or achieves the same modularity values as MMAS and ABC-INTE on 7 out of 10 networks and is robust against different graphs. In practice, the speed of ABC-POLY is at least 10 times faster than MMAS, making it a scalable algorithm compared to MMAS. ABC-POLY also outputs a direct visual representation of the natural clusters on the graph that is appealing to human observation. This thesis opens an interesting research topic to apply polymorphic ants for graph clustering in the ABC-POLY algorithm. The distributive and self-organization nature of ABC-POLY makes it a candidate for analyzing clusters in more complex and dynamic graphs.en_US
dc.description.noteMay 2016en_US
dc.identifier.urihttp://hdl.handle.net/1993/31202
dc.language.isoengen_US
dc.rightsopen accessen_US
dc.subjectSwarm Intelligenceen_US
dc.subjectMetaheuristicsen_US
dc.subjectGraph Clusteringen_US
dc.subjectAnt Colony Optimizationen_US
dc.subjectAnt Brood Clusteringen_US
dc.titleA Polymorphic Ant-Based Algorithm for Graph Clusteringen_US
dc.typemaster thesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
liu_yingying.pdf
Size:
2.45 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.2 KB
Format:
Item-specific license agreed to upon submission
Description:
Download
Collections
FGS - Electronic Theses and Practica