modMax (version 1.1)

simulatedAnnealing: Simulated annealing algorithms

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

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.

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

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.

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

#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)