随机在图上访问节点的概率 [英] Probability to visit nodes in a random walk on graph

问题描述

我有一个有限的无向图，其中一个节点标记为开始，另一个标记为目标。

代理最初放置在开始节点并随机导航图形，即在每一步随机选择一个邻居节点并移动到该节点。
当它到达目标节点时，它会停止。

我正在寻找一种算法，对于每个节点，都提供有关代理访问概率的指示它，从开始到目标旅行。
谢谢。

解决方案

与图形通常情况一样，只需要知道适当的方法描述这个问题。

编写图形的一种方法是将邻接矩阵。如果你的图G =（V，E）有| V |节点（其中| V |是顶点的数量），这个矩阵将是| V | x | V |。如果边缘存在于一对顶点之间，则将邻接矩阵中的项目设置为1，如果不存在，则将其设置为0.

是加权图。在这里，而不是0或1，邻接矩阵有一些权重的概念。

在你描述的情况下，你有一个加权图，权重是从一个节点过渡到另一个节点的概率。这种类型的矩阵有一个特殊的名称，它是一个随机矩阵。根据你对矩阵的排列方式，这个矩阵将有行或列，它们分别总和为1，左右随机矩阵。

随机矩阵和图形之间的一个链接是马尔可夫链。在马尔可夫链文献中，你需要的关键是转移矩阵（邻接矩阵的权重等于一个时间步后的转移概率）。我们称之为转换矩阵 P 。

计算k次时间后从一个状态转换到另一个状态的概率由下式给出：P ^ķ。如果你有一个已知的源状态i，那么第i行的 P ^ k会给你转换到任何其他状态的概率。这给你一个估计在短期内处于给定状态的概率

根据你的来源图，它可能是 P ^ k达到稳态分布 - 也就是对于k的某个值，P（k + 1）。这给你一个估计长期处于给定状态的可能性

另外，在你做任何这些事情之前，你应该能够看看你的图表，并且说出一些关于在某个特定状态下处于某种状态的可能性的一些事情。

1. 如果您的图形具有不相交的组件，则不在其中的组件的概率为零。


2. 如果图表的某些状态是吸收，也就是说，某些州（或国家）一旦输入它们就无法避免，那么你就需要对此进行解释。 如果您的图形像树状，则可能发生这种情况。

I have a finite undirected graph in which a node is marked as "start" and another is marked as "goal".

An agent is initially placed at the start node and it navigates through the graph randomly, i.e. at each step it chooses uniformly at random a neighbor node and moves to it. When it reaches the goal node it stops.

I am looking for an algorithm that, for each node, gives an indication about the probability that the agent visits it, while traveling from start to goal. Thank you.

解决方案

As is often the case with graphs, it's simply a matter of knowing an appropriate way to describe the problem.

One way of writing a graph is as an adjacency matrix. If your graph G = (V, E) has |V| nodes (where |V| is the number of vertices), the this matrix will be |V| x |V|. If an edge exists between a pair of vertices, you set the item in the adjacency matrix to 1, or 0 if it isn't present.

A natural extension of this is to weighted graphs. Here, rather than 0 or 1, the adjacency matrix has some notion of weight.

In the case you're describing, you have a weighted graph where the weights are the probability of transitioning from one node to another. This type of matrix has a special name, it is a stochastic matrix. Depending on how you've arranged your matrix, this matrix will have either rows or columns that sum to 1, right and left stochastic matrices respectively.

One link between stochastic matrices and graphs is Markov Chains. In Markov chain literature the critical thing you need to have is a transition matrix (the adjacency matrix with weights equal to the probability of transition after one time-step). Let's call the transition matrix P.

Working out the probability of transitioning from one state to another after k timesteps is given by P^k. If you have a known source state i, then the i-th row of P^k will give you the probability of transitioning to any other state. This gives you an estimate of the probability of being in a given state in the short term

Depending on your source graph, it may be that P^k reaches a steady state distribution - that is, P^k = P^(k+1) for some value of k. This gives you an estimate of the probability of being in a given state in the long term

As an aside, before you do any of this, you should be able to look at your graph, and say some things about what the probability of being in a given state is at some time.

1. If your graph has disjoint components, the probability of being in a component that you didn't start in is zero.
2. If your graph has some states that are absorbing, that is, some states (or groups of states) are inescapable once you've entered them, then you'll need to account for that. This may happen if your graph is tree-like.

这篇关于随机在图上访问节点的概率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！