Community Detection Using Genetic Algorithm and Cuckoo Search

This project was an assignment for an AI course at the Amirkabir University of Technology, where the goal was to identify communities in a network using the Genetic Algorithm and Cuckoo Search. This post will focus on the problem-specific implementations rather than a detailed explanation of the algorithms themselves.

First, let’s consider a sample input graph:

Finding Communities Using Genetic Algorithm

1. Genetic Representation and Fitness Function:

   • I used a locus-based representation for this problem, as illustrated below:
   • The modularity measure was used as the fitness function.

2. Selection:

   • Roulette Wheel Selection was utilized for the selection step.

3. Crossover and Mutation:

   • A uniform crossover was used as follows:
   • The initial population was not entirely random. Instead, the process considered the network’s existing connections to avoid uninteresting divisions of unconnected nodes. This approach restricts the search space and promotes faster convergence.

After 50 iterations with an initial population of 200 and a mutation rate of 0.4, the following communities were identified, achieving a fitness function value of 0.41978961209730353.

Finding Communities Using Cuckoo Search

The Cuckoo Search algorithm is based on three idealized rules:

1. Each cuckoo lays one egg at a time in a randomly chosen nest.
2. The best nests with high-quality eggs are carried over to the next generation.
3. The number of available host nests is fixed, and a host bird can discover an egg with a certain probability, at which point it can either discard the egg or abandon the nest and build a new one.

The pseudo-code for the algorithm is as follows:

New solutions are generated using a Levy flight, a random walk where the step lengths follow a Levy distribution. Since the original Cuckoo Search is designed for continuous spaces, the nest location updating and abandon operators were adapted for the discrete nature of community detection.

After 30 iterations with an initial population of 200, the following communities were found, with a fitness function value of 0.4197896120973035.

All parameter choices and the source code are available in this GitHub repository.

References:

1. Pizzuti Clara. GA-Net: A Genetic Algorithm for Community Detection in Social Networks.
2. Xin-She Yang and Suash Deb. Cuckoo Search via Lévy flights.
3. Xu Zhou, Yanheng Liu and Bin Li. A multi-objective discrete cuckoo search algorithm with local search for community detection in complex networks.