在图上随机游走节点的概率

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，那么第i行将给你转换到任何其他状态的概率。这给你在短期内

根据您的源graph在一个给定的状态是概率的估计，这可能是因为P^k达到稳定状态分布 - 也就是说，P^k = P ^（k + 1）对于某个k值。这给你一个估计长期处于给定状态的概率

另外，在你做任何这些之前，在某个特定的状态下，某个时间的可能性是什么。

1. 如果您的图形具有不相交的组件，那么您在未启动的组件中的概率为零。
2. 如果你的图有一些状态是absorbing，也就是说，一旦你输入了一些状态（或者状态组），那么你就需要考虑这个状态。 如果您的图形是树状的，可能会发生这种情况。