# extremalOptimization: Extremal optimization (EO) algorithms In modMax: Community Structure Detection via Modularity Maximization

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

 ```1 2 3 4``` ```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`, τ-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 τ-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

 ``` 1 2 3 4 5 6 7 8 9 10``` ```#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) ```

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