# scg

##### All-in-one Function for the SCG of Matrices and Graphs

This function handles all the steps involved in the Spectral Coarse Graining (SCG) of some matrices and graphs as described in the reference below.

- Keywords
- graphs

##### Usage

```
scg(X, ev, nt, groups = NULL, mtype = c("symmetric", "laplacian",
"stochastic"), algo = c("optimum", "interv_km", "interv",
"exact_scg"), norm = c("row", "col"), direction = c("default",
"left", "right"), evec = NULL, p = NULL, use.arpack = FALSE,
maxiter = 300, sparse = getIgraphOpt("sparsematrices"), output =
c("default", "matrix", "graph"), semproj = FALSE, epairs = FALSE,
stat.prob = FALSE)
```

##### Arguments

- X
- The input graph or square matrix. Can be of class
`igraph`

,`matrix`

or`Matrix`

. - ev
- A vector of positive integers giving the indexes of the eigenpairs to be preserved. For real eigenpairs, 1 designates the eigenvalue with largest algebraic value, 2 the one with second largest algebraic value, etc. In the complex case, it is t
- nt
- A vector of positive integers of length one or equal
to
`length(ev)`

. When`algo`

=optimum ,`nt`

contains the number of groups used to partition each eigenvector separately. When`algo`

- groups
- A vector of
`nrow(X)`

or`vcount(X)`

integers labeling each group vertex in the partition. If this parameter is supplied most part of the function is bypassed. - mtype
- Character scalar. The type of semi-projector to be
used for the SCG. For now
symmetric ,laplacian andstochastic are available. - algo
- Character scalar. The algorithm used to solve the SCG
problem. Possible values are
optimum ,interv_km ,interv andexact_scg . - norm
- Character scalar. Either
row orcol . If set torow the rows of the Laplacian matrix sum up to zero and the rows of the stochastic matrix sum up to one; otherwise it is the columns. - direction
- Character scalar. When set to
right , resp.left , the parameters`ev`

and`evec`

refer to right, resp. left eigenvectors. When passeddefault it is the SCG described in th - evec
- A numeric matrix of (eigen)vectors to be preserved by the
coarse graining (the vectors are to be stored column-wise in
`evec`

). If supplied, the eigenvectors should correspond to the indexes in`ev`

as no cross-check will - p
- A probability vector of length
`nrow(X)`

(or`vcount(X)`

).`p`

is the stationary probability distribution of a Markov chain when`mtype`

=stochastic . This parameter is ignored in al - use.arpack
- Logical scalar. When set to
`TRUE`

uses the function`arpack`

to compute eigenpairs. This parameter should be set to`TRUE`

if one deals with large (over a few thousands) AND spa - maxiter
- A positive integer giving the maximum number of
iterations for the k-means algorithm when
`algo`

=interv_km . This parameter is ignored in all other cases. - sparse
- Logical scalar. Whether to return sparse matrices in the result, if matrices are requested.
- output
- Character scalar. Set this parameter to
default to retrieve a coarse-grained object of the same class as`X`

. - semproj
- Logical scalar. Set this parameter to
`TRUE`

to retrieve the semi-projectors of the SCG. - epairs
- Logical scalar. Set this to
`TRUE`

to collect the eigenpairs computed by`scg`

. - stat.prob
- Logical scalar. This is to collect the stationary
probability
`p`

when dealing with stochastic matrices.

##### Details

Please see SCG for an introduction.
In the following $V$ is the matrix of eigenvectors for which the
SCG is solved. $V$ is calculated from `X`

, if it is not given
in the `evec`

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

Xt The coarse-grained graph, or matrix, possibly a sparse matrix. groups A vector of `nrow(X)`

or`vcount(X)`

integers giving the group label of each object (vertex) in the partition.L The semi-projector $L$ if `semproj = TRUE`

.R The semi-projector $R$ if `semproj = TRUE`

.values The computed eigenvalues if `epairs = TRUE`

.vectors The computed or supplied eigenvectors if `epairs = TRUE`

.p The stationary probability vector if `mtype = stochastic`

and`stat.prob = TRUE`

. For other matrix types this is missing.

##### concept

Spectral coarse graining

##### 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 an introduction.
`scgNormEps`

, `scgGrouping`

and
`scgSemiProjectors`

.

##### Examples

```
## We are not running these examples any more, because they
## take a long time (~20 seconds) to run and this is against the CRAN
## repository policy. Copy and paste them by hand to your R prompt if
## you want to run them.
# SCG of a toy network
g <- graph.full(5) %du% graph.full(5) %du% graph.full(5)
g <- add.edges(g, c(1,6, 1,11, 6, 11))
cg <- scg(g, 1, 3, algo="exact_scg")
#plot the result
layout <- layout.kamada.kawai(g)
nt <- vcount(cg$Xt)
col <- rainbow(nt)
vsize <- table(cg$groups)
ewidth <- round(E(cg$Xt)$weight,2)
op <- par(mfrow=c(1,2))
plot(g, vertex.color = col[cg$groups], vertex.size = 20,
vertex.label = NA, layout = layout)
plot(cg$Xt, edge.width = ewidth, edge.label = ewidth,
vertex.color = col, vertex.size = 20*vsize/max(vsize),
vertex.label=NA, layout = layout.kamada.kawai)
par(op)
## SCG of real-world network
library(igraphdata)
data(immuno)
summary(immuno)
n <- vcount(immuno)
interv <- c(100,100,50,25,12,6,3,2,2)
cg <- scg(immuno, ev= n-(1:9), nt=interv, mtype="laplacian",
algo="interv", epairs=TRUE)
## are the eigenvalues well-preserved?
gt <- cg$Xt
nt <- vcount(gt)
Lt <- graph.laplacian(gt)
evalt <- eigen(Lt, only.values=TRUE)$values[nt-(1:9)]
res <- cbind(interv, cg$values, evalt)
res <- round(res,5)
colnames(res) <- c("interv","lambda_i","lambda_tilde_i")
rownames(res) <- c("N-1","N-2","N-3","N-4","N-5","N-6","N-7","N-8","N-9")
print(res)
## use SCG to get the communities
com <- scg(graph.laplacian(immuno), ev=n-c(1,2), nt=2)$groups
col <- rainbow(max(com))
layout <- layout.auto(immuno)
plot(immuno, layout=layout, vertex.size=3, vertex.color=col[com],
vertex.label=NA)
## display the coarse-grained graph
gt <- simplify(as.undirected(gt))
layout.cg <- layout.kamada.kawai(gt)
com.cg <- scg(graph.laplacian(gt), nt-c(1,2), 2)$groups
vsize <- sqrt(as.vector(table(cg$groups)))
op <- par(mfrow=c(1,2))
plot(immuno, layout=layout, vertex.size=3, vertex.color=col[com],
vertex.label=NA)
plot(gt, layout=layout.cg, vertex.size=15*vsize/max(vsize),
vertex.color=col[com.cg],vertex.label=NA)
par(op)
```

*Documentation reproduced from package igraph, version 0.6.5-2, License: GPL (>= 2)*