extremalOptimization {modMax}

Extremal optimization (EO) algorithms

Description

extremalOptimization is a function executing the extremal optimization approach and its modifications for calculating modularity and detecting communities (modules of nodes) of a network via modularity maximization

pcseoss is a function which uses extremal optimization, but also considers pairwise constraints when calculating the fitness function and the modularity. The violation of constraints is punished, leading to smaller fitness and modularity values for community structures that violate many pairwise constraints. The constraints are predefined as two matrices separately for must-links and cannot-links with punishment for violation.

Usage

extremalOptimization(adjacency, numRandom = 0, 
                      refine = c("none", "agents"), 
                      tau = FALSE, alpha_max = length(adjacency[1,]), steps = 3)
pcseoss(adjacency,constraints_ml,constraints_cl)

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.

refine

Specify whether or not a refinement step is needed, the default option is none. See details below.

tau

If TRUE, \tau-EO is executed where the vertices are ranked according to their fitness values and chosen by a probability depending on this ranking.

alpha_max

It gives the maximum number of iteration steps. If the community structure could not be improved for this number of steps, the algorithm terminates. It is 1 for the normal EO-algorithm and n for the \tau-EO where n is the number of vertices in the network

steps

The number of iteration steps for the random local search agent algorithm. The algorithm terminates, if the clusters have not changed for this number of steps. Ignored if refine is none.

constraints_ml

The matrix where each column is a must-link constraint given by two vertices in the first two rows which have to be in the same community and a punishment for the violation of the constraint in the third row

constraints_cl

The matrix where each column is a cannot-link constraint given by two vertices in the first two rows which cannot be in the same community and a punishment for the violation of the constraint in the third row

Details

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

The EO algorithm can be run with a certain refinement step, the local random search agent algorithm, applied at the end of one round of extremal where all communities have been split once.

This refinement algorithm is executed if refine equals agent, otherwise the generic EO algorithm is executed.

Value

The result of the extremal optimization 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

Duch, J. and Arenas, A. Community detection in complex networks using extremal optimization. Phys. Rev. E, 72:027104, Aug 2005.

Azizifard, N., Mahdavi, M. and Nasersharif, B. Modularity optimization for clustering in social networks. 2011.

Li, L., Du, M., Liu, G., Hu, X. and Wu, G. Extremal optimization-based semi-supervised algorithm with conflict pairwise constraints for community detection. In Advances in Social Network Analysis and Mining (ASONAM), 2014 IEEE/ACM International Conference on, 2014.

Examples

#weighted 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)
graph <- set.edge.attribute(graph, "weight", value=runif(ecount(graph),0,1))

adj <- get.adjacency(graph, attr="weight")
result <- extremalOptimization(adj)