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