scgGrouping
SCG Problem Solver
This function solves the Spectral Coarse Graining (SCG) problem; either exactly, or approximately but faster.
- Keywords
- graphs
Usage
scgGrouping(V, nt, mtype = c("symmetric", "laplacian",
"stochastic"), algo = c("optimum", "interv_km",
"interv","exact_scg"), p = NULL, maxiter = 100)
Arguments
- V
- A numeric matrix of (eigen)vectors to be preserved by the
coarse graining (the vectors are to be stored column-wise in
V
). - nt
- A vector of positive integers of length one or equal to
length(ev)
. Whenalgo
=optimum ,nt
contains the number of groups used to partition each eigenvector separately. Whenalgo
- mtype
- The type of semi-projectors used in the SCG. For now
symmetric ,laplacian andstochastic are available. - algo
- The algorithm used to solve the SCG problem. Possible
values are
optimum ,interv_km ,interv andexact_scg . - p
- A probability vector of length equal to
nrow(V)
.p
is the stationary probability distribution of a Markov chain whenmtype
=stochastic . This parameter is ignored in all other cases. - maxiter
- A positive
integer giving the maximum number of iterations of the k-means
algorithm when
algo
=interv_km . This parameter is ignored in all other cases.
Details
The algorithm V
. The running time of this algorithm is
$O(\max nt \cdot m^2)$ for the symmetric and
laplacian matrix problems (i.e. when mtype
is
V
.
In all three cases, the memory usage is $O(m^2)$.
The algorithms nt[i]
constant-size bins are used to partition V[,i]
. When
algo
=
Once a minimizing partition (either exact or approximate) has been
found for each eigenvector, the final grouping is worked out as
follows: two vertices are grouped together in the final partition if
they are grouped together in each minimizing partition. In general the
size of the final partition is not known in advance when
ncol(V)
>1.
Finally, the algorithm
Value
- A vector of
nrow(V)
integers giving the group label of each object (vertex) in the partition.
References
D. Morton de Lachapelle, D. Gfeller, and P. De Los Rios, Shrinking
Matrices while Preserving their Eigenpairs with Application to the
Spectral Coarse Graining of Graphs. Submitted to SIAM Journal on
Matrix Analysis and Applications, 2008.
See Also
SCG for a detailed introduction. scg
,
scgNormEps
Examples
# eigenvectors of a random symmetric matrix
M <- matrix(rexp(10^6), 10^3, 10^3)
M <- (M + t(M))/2
V <- eigen(M, symmetric=TRUE)$vectors[,c(1,2)]
# displays size of the groups in the final partition
gr <- scgGrouping(V, nt=c(2,3))
col <- rainbow(max(gr))
plot(table(gr), col=col, main="Group size", xlab="group", ylab="size")
## comparison with the grouping obtained by kmeans
## for a partition of same size
gr.km <- kmeans(V,centers=max(gr), iter.max=100, nstart=100)$cluster
op <- par(mfrow=c(1,2))
plot(V[,1], V[,2], col=col[gr],
main = "SCG grouping",
xlab = "1st eigenvector",
ylab = "2nd eigenvector")
plot(V[,1], V[,2], col=col[gr.km],
main = "K-means grouping",
xlab = "1st eigenvector",
ylab = "2nd eigenvector")
par(op)
## kmeans disregards the first eigenvector as it
## spreads a much smaller range of values than the second one
### comparing optimal and k-means solutions
### in the one-dimensional case.
x <- rexp(2000, 2)
gr.true <- scgGrouping(cbind(x), 100)
gr.km <- kmeans(x, 100, 100, 300)$cluster
scgNormEps(cbind(x), gr.true)
scgNormEps(cbind(x), gr.km)