A Self Fixing Intelligent Ant Clustering Algorithm For Graphs

摘要

In this paper, we introduce two ant based algorithms for the graph clustering problem. The first algorithm, Intelligent Ant Clustering (IAC), uses techniques such as hopping ants, relaxed drop function, ants with memories, and stagnation control as improvements to the original ant graph clustering algorithm AC-KLS by Kuntz et al. [1]. The second algorithm, Self Fixing Intelligent Ant Clustering (SFIAC), is inspired by polymorphic ant species such as the Pheidole genus [2]. In SFIAC, a second type of major ants (the foragers) is introduced to improve the global clustering quality in addition to the minor workers (the housekeepers) that run IAC locally. SFIAC outperforms or achieves the same modularity values as ACO-MMAS [3] and IAC on 7 out of 10 benchmark networks and is robust against different graphs. In practice, the speed of SFIAC is at least 10 times faster than MMAS, making it a comparatively scalable algorithm.