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