graph - 图上随机游走访问节点的概率

Question

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

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

我正在寻找一种算法，对于每个节点，它可以指示代理在从起点到目标的过程中访问该节点的概率。 谢谢。

Answer 1

与图表的情况一样，这只是了解描述问题的适当方法的问题。

编写图表的一种方法是 adjacency matrix 。如果你的图 G = (V, E) 有 |V|节点(其中 |V| 是顶点数)，该矩阵将为 |V| x|V|。如果一对顶点之间存在边，则将邻接矩阵中的该项设置为 1，如果不存在则设置为 0。

其自然延伸是 weighted graphs 。这里，邻接矩阵有一些权重概念，而不是 0 或 1。

在您描述的情况下，您有一个加权图，其中权重是从一个节点转换到另一个节点的概率。这种类型的矩阵有一个特殊的名字，它是stochastic matrix 。根据您排列矩阵的方式，该矩阵的行或列的总和分别为 1、右随机矩阵和左随机矩阵。

随机矩阵和图之间的一个链接是 Markov Chains 。在马尔可夫链文献中，您需要拥有的关键是一个转移矩阵(权重等于一个时间步后转移概率的邻接矩阵)。我们将转换矩阵称为P。

计算 k 个时间步后从一种状态转换到另一种状态的概率由 P^k 给出。如果你有一个已知的源状态 i，那么 P^k 的第 i 行将为你提供转换到任何其他状态的概率。这可以让您估计短期内处于给定状态的概率

取决于您的来源 graph ，P^k 可能达到稳态分布 - 即 P^k = P^(k+1) 对于k 的某个值。这可以让您估计长期处于给定状态的概率

顺便说一句，在执行任何操作之前，您应该能够查看图表，并说明在某个时间处于给定状态的概率是多少。

1. 如果您的图表具有不相交的组件，则位于您最初未使用的组件中的概率为零。
2. 如果您的图表有一些状态为 absorbing ，也就是说，某些状态(或状态组)一旦输入就不可避免，那么您需要考虑到这一点。 如果您的图表是树状的，则可能会发生这种情况。