R igraph 手册页

scg_group {igraph}

R 文档

SCG 问题求解器

描述

此函数求解谱粗粒化 (SCG) 问题；可以是精确求解，也可以是近似求解，但速度更快。

用法

scg_group(
  V,
  nt,
  mtype = c("symmetric", "laplacian", "stochastic"),
  algo = c("optimum", "interv_km", "interv", "exact_scg"),
  p = NULL,
  maxiter = 100
)

参数

V	要通过粗粒化保留的（特征）向量的数值矩阵（向量按列存储在 V 中）。
nt	长度为 1 或等于 length(ev) 的正整数向量。当 algo = “optimum” 时，nt 包含用于单独划分每个特征向量的组数。当 algo 等于 “interv_km” 或 “interv” 时，nt 包含用于划分每个特征向量的区间数。如果 nt 是单个整数，则每个特征向量使用相同的分区大小或区间数。当 algo = “exact_cg” 时，此参数将被忽略。
mtype	SCG 中使用的半投影类型。目前有“symmetric”、“laplacian”和“stochastic”可用。
algo	用于求解 SCG 问题的算法。可能的值为 “optimum”、“interv_km”、“interv” 和 “exact_scg”。
p	长度等于 nrow(V) 的概率向量。当 mtype = “stochastic” 时，p 是马尔可夫链的平稳概率分布。在所有其他情况下，此参数将被忽略。
maxiter	当 algo = “interv_km” 时，给出 k-means 算法的最大迭代次数的正整数。在所有其他情况下，此参数将被忽略。

详细信息

算法 “optimum” 精确求解 V 中每个特征向量的 SCG 问题。对于对称和拉普拉斯矩阵问题（即当 mtype 为 “symmetric” 或 “laplacian” 时），该算法的运行时间为 O(\max nt \cdot m^2)。对于随机问题，运行时间为 O(m^3)。这里 m 是 V 中的行数。在这三种情况下，内存使用量均为 O(m^2)。

算法 “interv” 和 “interv_km” 通过对特征向量的分量执行（目前）恒定的分箱来近似求解 SCG 问题，即使用 nt[i] 个恒定大小的箱来划分 V[,i]。当 algo = “interv_km” 时，(Lloyd) k-means 算法在 “interv” 获得的每个分区上运行，以提高精度。

一旦为每个特征向量找到最小化分区（精确或近似），最终分组将按如下方式进行：如果两个顶点在每个最小化分区中都分组在一起，则它们在最终分区中也分组在一起。一般来说，当 ncol(V)>1 时，最终分区的大小事先是未知的。

最后，算法 “exact_scg” 将每个特征向量中具有相等分量的顶点分组在一起。最后三个算法本质上具有线性运行时间和内存负载。

值

一个 nrow(V) 个整数的向量，给出分区中每个对象（顶点）的组标签。

作者

David Morton de Lachapelle david.morton@epfl.ch, david.mortondelachapelle@swissquote.ch

参考

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. http://people.epfl.ch/david.morton

参见

scg-method 获取详细介绍。 scg, scg_eps

示例

## We are not running these examples any more, because they
## take a long time 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.

## Not run: 
# 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 <- scg_group(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 <- scg_group(cbind(x), 100)
gr.km <- kmeans(x, 100, 100, 300)$cluster
scg_eps(cbind(x), gr.true)
scg_eps(cbind(x), gr.km)

## End(Not run)

---