有向加权图行走

Question

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

Answer 1

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

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

这个向量v就是特征值1对应的P的特征向量。P是否总是有这样的特征值呢？幸运的是，Perron-Frobenius 定理告诉我们确实如此，而且这是P的最大特征值。然后解决的方法是形成邻接矩阵P并找到其最大特征值对应的特征向量。

也有一个近似解。如果我们采用顶点概率向量x ，其中x _A = 1，并且其他元素设置为 0，则随着k趋向无穷大， P ^k x将收敛于v 。对于较小的k值， P ^k可能比特征向量更容易计算。

例子

我们来看下面这个简单的图表：

如果我们按字母顺序对顶点进行排序，则该图对应的矩阵P为：

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

P ¹⁶ [1 0 0 0]的值约为 [1 0 0.886 0.62]，精确到小数点后 6 位。