Learn R Programming

modMax (version 1.1)

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

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

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.

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

Run this code
#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)

Run the code above in your browser using DataLab