跳到内容

图上的随机游走

来源：R/random_walk.R
random_walk.Rd

random_walk() 在图上执行随机游走，并返回随机游走经过的顶点。random_edge_walk() 的作用相同，但返回随机游走经过的边。

用法

random_walk(
  graph,
  start,
  steps,
  weights = NULL,
  mode = c("out", "in", "all", "total"),
  stuck = c("return", "error")
)

random_edge_walk(
  graph,
  start,
  steps,
  weights = NULL,
  mode = c("out", "in", "all", "total"),
  stuck = c("return", "error")
)

参数

graph

输入图，可以是无向图或有向图。

start

起始顶点。

steps

要进行的步数。

weights

边的权重。较大的边权重会增加随机游走者选择该边的概率。换句话说，较大的边权重对应于更强的连接。如果存在，则使用“weight”边属性。 如果要忽略“weight”边属性，请在此处提供 ‘NA’。

mode

如何沿着有向边行走。 "out" 沿着边的方向走，"in" 与之相反。 "all" 忽略边的方向。 此参数对于无向图将被忽略。

stuck

如果随机游走卡住该怎么办。 "return" 返回部分游走，"error" 引发错误。

值

对于 random_walk()，顶点序列的长度为 steps + 1，包含沿游走的顶点，从 start 开始。 对于 random_edge_walk()，边序列的长度为 steps，包含沿游走的边。

详细信息

进行随机游走。 从给定的起始顶点开始，采取给定的步数，从实际顶点均匀随机地选择一条边。 在有向图中观察边方向（也请参见 mode 参数）。 也会观察多重边和环边。

对于 igraph < 1.6.0，random_walk() 计算步数的方式不同，并返回长度为 steps 而不是 steps + 1 的序列。 更改此设置是为了提高与底层 C 库的一致性。

random_walk().

示例

## Stationary distribution of a Markov chain
g <- make_ring(10, directed = TRUE) %u%
  make_star(11, center = 11) + edge(11, 1)

ec <- eigen_centrality(g, directed = TRUE)$vector
pg <- page_rank(g, damping = 0.999)$vector
w <- random_walk(g, start = 1, steps = 10000)

## These are similar, but not exactly the same
cor(table(w), ec)
#> [1] 0.9618877

## But these are (almost) the same
cor(table(w), pg)
#> [1] 0.9998887