spectralOptimization: Spectral optimization algorithms
In modMax: Community Structure Detection via Modularity Maximization

Description Usage Arguments Details Value Author(s) References Examples

spectralOptimization uses the leading eigenvector to recursively split the communities of a network into two until no further improvement of modularity is possible.

multiWay, spectral1 and spectral2 use k-1 leading eigenvectors to split the network into k communities. The value for k leading to the best community structure is chosen as the final number of communities and the resulting split of the network into k communities as the final community structure. The 3 functions implement slightly different approaches leading to possibly different results.

spectralOptimization(adjacency, numRandom = 0, initial = c("general", "own"),
                      refine = FALSE)
multiWay(adjacency, numRandom=0, maxComm=length(adjacency[1,]))
spectral1(adjacency, numRandom=0, maxComm=(length(adjacency[1,])-1))
spectral2(adjacency, numRandom=0, maxComm=(length(adjacency[1,])-1))

`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 initial partition in the algorithm. See details below.
`refine`	If `TRUE`, Kernighan-Lin refinement is applied after splitting a community into two communities only on this part of the network.
`maxComm`	THe maximum number of communities that the network allows

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 spectral optimization algorithm can either be the generic one where all vertices are put in their own community (initial=general) 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.

The result of the spectral 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`

Maria Schelling, Cang Hui

Newman, M. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E, 74:036104, Sep 2006.

Newman, M. E. J. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23):8577-8582, 2006.

Wang, G., Shen, Y., and Ouyang, M. A vector partitioning approach to detecting community structure in complex networks. Computers and Mathematics with Applications, 55(12):2746-2752, 2008.

White, S. and Smyth, P. A spectral clustering approach to finding communities in graphs. In In SIAM International Conference on Data Mining, 2005.

#unweighted network
randomgraph1 <- erdos.renyi.game(10, 0.3, type="gnp",directed = FALSE, loops = FALSE)

#to ensure that the graph is connected
vertices1 <- which(clusters(randomgraph1)$membership==1)  
graph1 <- induced.subgraph(randomgraph1,vertices1)

adj1 <- get.adjacency(graph1)
result1 <- spectralOptimization(adj1, refine = TRUE)

#weighted network
randomgraph2 <- erdos.renyi.game(10, 0.3, type="gnp",directed = FALSE, loops = FALSE)

#to ensure that the graph is connected
vertices2 <- which(clusters(randomgraph2)$membership==1)  
graph2 <- induced.subgraph(randomgraph2,vertices2)
graph2 <- set.edge.attribute(graph2, "weight", value=runif(ecount(graph2),0,1))

adj2 <- get.adjacency(graph2, attr="weight")
result2 <- multiWay(adj2, maxComm=3)

Loading required package: gtools
Loading required package: igraph

Attaching package: 'igraph'

The following object is masked from 'package:gtools':

    permute

The following objects are masked from 'package:stats':

    decompose, spectrum

The following object is masked from 'package:base':

    union