Using Ants to Find Communities in Complex Networks

Open Access
Author:
Adi, Mohammad
Graduate Program:
Computer Science
Degree:
Master of Science
Document Type:
Master Thesis
Date of Defense:
April 03, 2014
Committee Members:
  • Thang Nguyen Bui, Thesis Advisor
Keywords:
  • ant-algorithms
  • complex-networks
  • community-detection
Abstract:
Many systems arising in different fields can be described as complex networks, a collection of nodes and edges connecting nodes. An interesting property of these complex networks is the presence of communities (or clusters), which represent subsets of nodes within the network such that the number of edges between nodes in the same community is large whereas the number of edges connecting nodes in different communities is small. In this thesis, we give an ant-based algorithm for finding communities in complex networks. We employ artificial ants to traverse the network based on a set of rules in order to discover a ``good set'' of edges that are likely to connect nodes within a community. Using these edges we construct the communities after which local optimization methods are used to further improve the solution quality. Experimental results on a total of 136 problem instances that include various synthetic and real world complex networks show that the algorithm is very competitive against current state-of-the-art techniques for community detection. In particular, our algorithm is more robust than existing algorithms as it performs well across many different types of networks.