r - 在转换矩阵上运行随机游走比 igraph::random_walk() 更有效

Question

我正在尝试在特定的转换矩阵 (20,000 * 20,000) 上创建随机游走器，到目前为止，我正在使用 R 包 中的 igraph::random_walk() 函数igraph.

该函数的作用是获取图形而不是转换矩阵作为输入。这意味着您首先必须使用以下命令将转换矩阵转换为图形:

# Transform transition matrix into graph
g <- igraph::graph.adjacency( as.matrix(tm), mode = "directed", weighted = TRUE )

由于我的转换矩阵是一个 20,000*20,000 的矩阵，变量 tm 占用了大约 3.1GB，对应的图 g 占用了 13.3GB。这种方法的缺点是脚本会填满整个内存(32GB RAM 系统)，有时内核(可能)会终止进程。

所以我想知道 R 中是否有任何其他包(找不到任何东西)返回转换矩阵上的随机游走，而不需要首先转换为图形。

Answer 1

手动实现怎么样？

library(igraph)
set.seed(1)
resample <- function(x, ...) x[sample.int(length(x), ...)]
n <- 1000
tm <- matrix(sample(0:1, n^2, prob = c(0.95, 0.05), replace = TRUE), n, n)
tm <- (tm == 1 | t(tm) == 1) * 1
diag(tm) <- 0

start <- 23 # Random walk starting vertex
len <- 10 # Walk length
path <- c(start, rep(NA, len))
for(i in 2:(len + 1)) {
  idx <- tm[path[i - 1], ] != 0
  if(any(idx)) {
    path[i] <- resample(which(idx), 1, prob = tm[path[i - 1], idx])
  } else {
    break # Stopping if we get stuck
  }
}
path
#  [1]   23 3434 4908 4600  332 4266 1752 1845 4847 4817 1992