我有一个连接的有向加权图。边权重表示顶点之间移动的概率；从一个顶点发出的所有边的权重总和为 1。该图包含两个汇：A 和 B。对于图中的每个顶点，我想知道从那里出发的步行到达 A 的概率，对于 B 也是如此。这是什么问题？我该如何解决？
问问题
1660 次
1 回答
4
这个问题属于代数问题。对于从顶点开始的路径，到达 A 的概率是从其每个相邻顶点到达 A 的概率的平均值，由边权重加权。让我们用更具体的术语来表达。
令P为图的邻接矩阵。也就是说，P i,j是从顶点i移动到顶点j的概率。设置P A,A = 1。如果我们采用分配给每个顶点的概率向量并将其乘以P，则结果向量包含每个顶点的邻居的加权平均值。我们正在寻找的是一个向量v，使得P v = v和v A = 1。
这个向量v是P的特征向量对应1的特征值。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 16 [1 0 0 0] 的值大约为 [1 0 0.886 0.62] 并且精确到小数点后 6 位。
于 2012-05-29T21:19:52.687 回答