geneticAlgorithm {modMax}

Genetic algorithm

Description

geneticAlgorithm is a function executing the genetic algorithm and its modifications for identifying the community structure of a network via modularity maximization

Usage

geneticAlgorithm(adjacency, numRandom = 0, 
                  initial = c("general", "cluster", "own"), p, g, 
                  mutRat = 0.5, crossOver = 0.2, beta = 0.1, alpha = 0.4, 
                  n_l = 4, local = FALSE)

Arguments

adjacency

A nonnegative symmetric adjacency matrix of the network whose community structur will be analyzed

numRandom

The number of random networks with which the modularity of the resulting community structure should be compared (default: no comparison). see details below for further explanation of the used null model

initial

Specify the community structure to use as initial partition in the algorithm. See details below.

p

Population size

g

Number of generations

mutRat

Mutation rate. Default is 0.5

crossOver

Crossing over rate. Default is 0.2

beta

The fraction of chromosomes to save. The top \betap chromosomes are saved in each generation to ensure that the fitness scores of the top \betap chromosomes of the child generation are at least as good as the parent population. Default is 0.1

alpha

The fraction of repetitions for the identification of an initial partition according to cluster. Default is 0.4. Ignored if initial is not cluster.

n_l

The number of copies of a chromosome made by the local search operator. Default is 4. Ignored if local is FALSE

local

If TRUE, local search operator is applied at the end of each iteration in the genetic algorithm.

Details

The used random networks have the same number of vertices and the same degree distribution as the original network.

The initial partition used in the genetic algorithm can either be the generic one where all vertices are put in their own community (initial=general) or the initial partition can be identified by randomly picking a vertex \alphan times and assigning its cluster to all its neighbours (initial=cluster) or the initial partition can be given by the user (initial=own). In this case, the user needs to add a last column to the adjacency matrix indicating the initial partition. Hence, the adjacency matrix has to have one column more than the network has vertices.

Value

The result of the genetic algorithm is a list with the following components

number of communities

The number of communities detected by the algorithm

modularity

The modularity of the detected community structure

mean

The mean of the modularity values for random networks, only computed if numRandom>0

standard deviation

The standard deviation of the modularity values for random networks, only computed if numRandom>0

community structure

The community structure of the examined network given by a vector assigning each vertex its community number

random modularity values

The list of the modularity values for random networks, only computed if
numRandom>0

Author(s)

Maria Schelling, Cang Hui

References

Tasgin, M., Herdagdelen, A., and Bingol, H. Community detection in complex networks using genetic algorithms. arXiv preprint arXiv:0711.0491, 2007.

Li, S., Chen, Y., Du, H., and Feldman, M. W. A genetic algorithm with local search strategy for improved detection of community structure. Complexity, 15(4):53-60, 2010.

Examples

#unweighted network
randomgraph <- erdos.renyi.game(10, 0.3, type="gnp",directed = FALSE, loops = FALSE)

#to ensure that the graph is connected
vertices <- which(clusters(randomgraph)$membership==1)  
graph <- induced.subgraph(randomgraph,vertices)

adj <- get.adjacency(graph)
result <- geneticAlgorithm(adj, p=4, g=6)