# simulatedAnnealing: Simulated annealing algorithms In modMax: Community Structure Detection via Modularity Maximization

## Description

The functions presented here are based on simulated annealing and identify the community structure and maximize the modularity. `simulatedAnnealing` is only based on moving a single vertex from one community to another, while `saIndividualCollectiveMoves` considers movements of vertices, merging of communities and splitting of communities as alternatives to increase the modularity.

## Usage

 ```1 2 3 4 5 6``` ```simulatedAnnealing(adjacency, numRandom = 0, initial = c("general", "random","greedy", "own"), beta = length(adjacency[1, ])/2, alpha = 1.005, fixed) saIndividualCollectiveMoves(adjacency,numRandom=0,initial=c("general","own"), beta=length(adjacency[1,])/2,alpha=1.005, fixed=25,numIter=1.0) ```

## 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 the initial partition in the algorithm. See details below. `beta` Define the initial inverse temperature. `Default` is `(network size)/2` `alpha` Define the cooling parameter. `Default` is `1.005` `fixed` If the community structure has not changed for this specified number of steps, the algorithm is terminated. `numIter` Define the iteration factor. At each temperature, the algorithm performs fn^2 individual moves (movement of a single vertex) and fn collective moves (merge or split of a community) where n is the number of vertices in the network.

## 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 simulated annealing algorithms 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 identifying the initial number of communities and randomly assigning the vertices to one of these communities (`initial=random`) or the initial partition can be the community structure identified by the greedy algorithm (`initial=greedy`) 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 simulated annealing algorithms 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

Medus, A., Acua, G. and Dorso, C.O. Detection of community structures in networks via global optimization. Physica A: Statistical Mechanics and its Applications, 358(24):593-604, 2005.

Massen, C. and Doye, J. Identifying communities within energy landscapes. Phys. Rev. E, 71:046101, Apr 2005.

Guimera, R. and Amaral, L. A. N. Nunes amaral. Functional cartography of complex metabolic networks. Nature, 2005.

## Examples

 ```1 2 3 4 5 6 7 8 9``` ```#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 <- simulatedAnnealing(adj, fixed=10) ```

modMax documentation built on May 2, 2019, 12:20 p.m.