R igraph 手册页

scg {igraph}

R 文档

用于矩阵和图的 SCG 的一体化函数

描述

此函数处理一些矩阵和图的谱粗粒化 (SCG) 中涉及的所有步骤，如下面的参考文献中所述。

用法

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 = igraph_opt("sparsematrices"),
  output = c("default", "matrix", "graph"),
  semproj = FALSE,
  epairs = FALSE,
  stat.prob = FALSE
)

参数

X	输入图或方阵。可以是 igraph、matrix 或 Matrix 类。
ev	一个正整数向量，给出要保留的特征对的索引。对于实特征对，1 表示代数值最大的特征值，2 表示代数值第二大的特征值，依此类推。在复数情况下，幅度很重要。
nt	长度为 1 或等于 length(ev) 的正整数向量。当 algo = “optimum” 时，nt 包含用于分别划分每个特征向量的组数。当 algo 等于 “interv_km” 或 “interv” 时，nt 包含用于划分每个特征向量的间隔数。如果 nt 是单个整数，则每个特征向量使用相同的分区大小或间隔数。当 algo = “exact_cg” 时，此参数将被忽略。
groups	一个 nrow(X) 或 vcount(X) 整数向量，标记分区中的每个组顶点。如果提供此参数，则函数的大部分将被绕过。
mtype	字符标量。用于 SCG 的半投影算子的类型。目前可以使用“symmetric”、“laplacian”和“stochastic”。
algo	字符标量。用于解决 SCG 问题的算法。可能的值为“optimum”、“interv_km”、“interv”和“exact_scg”。
norm	字符标量。可以是 “row” 或 “col”。如果设置为 “row”，则拉普拉斯矩阵的行总和为零，随机矩阵的行总和为一；否则为列。
direction	字符标量。当设置为“right”或“left”时，参数 ev 和 evec 分别指的是右特征向量或左特征向量。当传递“default”时，应用下面参考文献中描述的 SCG（常用用法）。此参数当前未实现，始终使用右特征向量。
evec	一个数字矩阵，包含要通过粗粒化保留的（特征）向量（向量应按列方式存储在 evec 中）。如果提供，则特征向量应与 ev 中的索引相对应，因为不会进行交叉检查。
p	长度为 nrow(X)（或 vcount(X)）的概率向量。当 mtype = “stochastic” 时，p 是马尔可夫链的平稳概率分布。在所有其他情况下，此参数将被忽略。
use.arpack	逻辑标量。当设置为 TRUE 时，使用函数 arpack 计算特征对。如果处理大的（超过几千个）且稀疏的图或矩阵，则应将此参数设置为 TRUE。此参数当前未实现，LAPACK 用于解决特征值问题。
maxiter	当 algo = “interv_km” 时，给出 k-means 算法的最大迭代次数的正整数。在所有其他情况下，此参数将被忽略。
sparse	逻辑标量。如果请求矩阵，是否在结果中返回稀疏矩阵。
输出	字符标量。将此参数设置为 “default” 以检索与 X 相同类的粗粒化对象。
semproj	逻辑标量。将此参数设置为 TRUE 以检索 SCG 的半投影算子。
epairs	逻辑标量。将其设置为 TRUE 以收集 scg 计算的特征对。
stat.prob	逻辑标量。这是为了在处理随机矩阵时收集平稳概率 p。

详细信息

请参阅 scg-method 以获取介绍。

在下面，V 是为其求解 SCG 的特征向量矩阵。如果未在 evec 参数中给出，则 V 是从 X 计算得出的。

算法“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] 个恒定大小的 bin 来划分 V[,i]。当 algo = “interv_km” 时，在由 “interv” 获得的每个分区上运行 (Lloyd) k-means 算法以提高准确性。

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

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

值

Xt	粗粒化图或矩阵，可能是稀疏矩阵。
groups	一个 nrow(X) 或 vcount(X) 整数向量，给出分区中每个对象（顶点）的组标签。
L	如果 semproj = TRUE，则半投影算子 L。
R	如果 semproj = TRUE，则半投影算子 R。
values	如果 epairs = TRUE，则计算出的特征值。
vectors	如果 epairs = TRUE，则计算出的或提供的特征向量。
p	如果 mtype = stochastic 且 stat.prob = TRUE，则平稳概率向量。对于其他矩阵类型，此项缺失。

作者

David Morton de Lachapelle, http://people.epfl.ch/david.morton.

参考

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_eps、scg_group 和 scg_semi_proj。

示例

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

## Not run: 
# SCG of a toy network
g <- make_full_graph(5) %du% make_full_graph(5) %du% make_full_graph(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_with_kk(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_with_kk)
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 <- laplacian_matrix(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(laplacian_matrix(immuno), ev=n-c(1,2), nt=2)$groups
col <- rainbow(max(com))
layout <- layout_nicely(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_with_kk(gt)
com.cg <- scg(laplacian_matrix(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)


## End(Not run)

---