A Novel Similarity-based Modularity Function for Graph Partitioning - Clustering Challenges in Biological Network - page 228

a) Single point crossover (Crossover Rate = 50%, no roll back):

Parents Children

1113 2344 ⇒ 1113 4433

2231 4433 2231 2344

Crossover point

b) Single point crossover (Crossover Rate = 50%, with roll back):

Parents

Children

1 1132 344 ⇒ 1 1134 433

2 2314 433 2 2312 344

↑ ↑

Roll back Crossover point

Mutation - mutation adds random variation and diversity to the population.
Usually the mutation rate should be kept very small.

22 3 12344 ⇒ 22 1 12344

Replacement - new offspring are inserted into the original population, replac-
ing individuals with lower fitness. Usually, the replacement population size is

constant.

The above procedure is repeated until a predefined number of generations have
elapsed or the fitness of the population stops increasing. The string with highest
fitness is the solution.

11.5. A Fast Agglomerative Algorithm

Although GA has the potential to jump out of local optimums, it has the drawback
of being slow and thus may be unsuitable for large graphs. Here we extend New-
man's fast hierarchical agglomerative clustering (FHAC) algorithm [1, 13] to the
similarity-based modularity.
Formula (11.6) can be re-written as:

DS i
TS

2

k

With Q S i = IS i

Q S = Q S i

TS −

. (11.9)

i =1

The algorithm is as follows:

1. Initialize by placing every vertex v i into its own cluster c i , and calculates Q S i
for each cluster.