theory - 有向加权图游走

Question

我有一个连接的有向加权图。边权重表示顶点之间移动的概率；从一个顶点发出的所有边的权重总和为 1。该图包含两个汇:A 和 B。对于图中的每个顶点，我想知道从那里出发的步行到达 A 的概率以及 B 的相同概率。这是什么类型的问题？我该如何解决？

Answer 1

这个问题是代数类型的。对于从顶点开始的路径，到达 A 的概率是从其每个相邻顶点到达 A 的概率的平均值，由边权重加权。让我们用更具体的术语来表述。

令 P 为图的邻接矩阵。也就是说，Pi,j 是从顶点 i 移动到顶点 j 的概率。设置 PA,A = 1。如果我们取一个分配给每个顶点的概率向量并将其乘以 P，则结果向量包含每个顶点邻居的加权平均值。我们正在寻找的是一个向量 v，使得 P v = v 且 vA = 1。

这个向量 v 是 P 的特征向量，对应于 1 的特征值。 P 总是有这样的特征值吗？幸运的是，Perron-Frobenius theorem告诉我们它确实存在，并且这是 P 的最大特征值。然后解决方案是形成邻接矩阵 P 并找到与其最大特征值对应的特征向量。

还有一个近似解。如果我们取顶点概率向量 x，其中 xA = 1，并且其他元素设置为 0，那么随着 k 趋于无穷大，Pk x 将收敛到 v。对于较小的 k 值，PK 可能比特征向量更容易计算。

例子

让我们看看下面的简单图形:



如果我们按字母顺序排列顶点，则图对应的矩阵 P 为:



这个矩阵的特征值等于1，对应的特征向量是:[1 0 70/79 49/79]。也就是说，从 C 到达 A 的确切概率是 70/79，而从 D 到达 A 的确切概率是 49/79。如果你算出 B 的答案，结果是 9/79 和 30/79，这正是我们所期望的。

P16 [1 0 0 0] 的值大约为 [1 0 0.886 0.62]，并且精确到小数点后 6 位。