spectralOptimization {modMax}

Spectral optimization algorithms

Description

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.

Usage

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

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

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

Value

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

Author(s)

Maria Schelling, Cang Hui

References

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.

Examples

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