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

Question

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

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

# 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 中是否有任何其他包（找不到任何东西） returns 在转换矩阵上随机游走，而不需要首先转换成图形。

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

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

More efficient way to run a random walk on a transition matrix than the igraph::random_walk()

r

matrix

igraph

random-walk

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

More efficient way to run a random walk on a transition matrix than the igraph::random_walk()

r

matrix

igraph

random-walk

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