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

Question

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

在此图中，权重 w(u,v) 表示节点 (v) 从节点 (u) 访问了多少次。例如（See 这对于有向图图像）：

     1        3
  A ----- B ----- D
  | \____/|
 1|   4   |2
  |       |
  C       E

由于A访问了C和B一次，B访问了D 3次，依此类推。鉴于此数据，我如何计算到达每个终端节点的确切概率，即； C,E,D，如果从A开始。

有什么建议吗？

Answer 1

假设 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，你最终到C的概率是1/2。并且如果你从 B 开始，你最终到达 C 的概率是，如果你首先移动到 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个概率可以用同样的方法计算。

Answer 2

下面是马尔可夫链的未归一化后行归一化的转移矩阵，也如图所示。我们需要计算如图所示的吸收概率。

  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

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

probability of each terminal node in a directed graph

algorithm

graph

probability

markov-chains