有向图中每个末端节点的概率

Question

我有一个有向图G(V,E)，权重为w(u,v)。

在这个图中，权重w(u,v)表示从节点u到节点v的访问次数。例如(请看这张有向图的图片):

如C和B从A只被访问一次，D从B被访问了3次等等。鉴于此数据，如果从A开始，如何计算到达每个终端节点（即C、E、D）的确切概率？

有什么建议吗？

- ydrall

---

你可以先估计从node(i)到node(j)的概率。例如，你可以说从B到A的概率是4/(4+2+3)=4/9。你把这个概率放在一个矩阵中，除了直接连接在图中的节点外，其他都是零。这就是一个马尔可夫链。现在你可以进行模拟。在http://stats.stackexchange.com/上搜索马尔可夫过程，那里应该有一些有用的信息。 - giusti

Answer 1

以下是马尔可夫链的非归一化和行归一化转移矩阵，如图所示。我们需要根据图中所示计算吸收概率。

  A B C D E
A 0 1 1 0 0
B 4 0 0 3 2
C 0 0 0 0 0
D 0 0 0 0 0
E 0 0 0 0 0  

          A   B   C         D         E
A 0.0000000 0.5 0.5 0.0000000 0.0000000
B 0.4444444 0.0 0.0 0.3333333 0.2222222
C 0.0000000 0.0 0.0 0.0000000 0.0000000
D 0.0000000 0.0 0.0 0.0000000 0.0000000
E 0.0000000 0.0 0.0 0.0000000 0.0000000

- Sandipan Dey

Answer 2

pXY 是指从状态 X 开始，最终到达状态 Y 的概率。

你需要计算 pAC、pAD、pAE、pBC、pBD、pBE 的值。

例如，计算 pAC 时有两个方程式：

pAC = 1/2 + 1/2 pBC
pBC = 4/9 pAC

也就是说，从A出发到达C的概率是1/2（直接移动到那里时），如果你先移动到B，则有1/2的概率最终到达C。如果你从B开始，先移动到A，然后再到达C的概率是。

将第二个代入第一个得到：

pAC = 1/2 + 1/2 * 4/9 pAC
pAC(1 - 2/9) = 1/2
pAC = 9/14

这立即给出了 pBC = 4/14 = 2/7。

其他4个概率可以用同样的方法计算。

- Paul Hankin