probabilité de chaque nœud terminal dans un graphe orienté

J'ai un graphe orienté G (V, E) et un poids w (u, v).probabilité de chaque nœud terminal dans un graphe orienté

Dans ce graphique, le poids w (u, v) représente le nombre de fois que le nœud (v) a visité le nœud (u). par exemple (See ce pour une image de graphe orienté):

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

Comme C et B sont visités une fois de A, D est visité 3 fois à partir de B et ainsi de suite. Compte tenu de ces données, comment puis-je calculer la probabilité exacte d'atteindre chaque nœud terminal, c'est-à-dire C, E, D, si à partir de A.

Une suggestion?

Source

2017-02-24 ydrall

Vous pouvez d'abord estimer la probabilité que vous aller de 'noeud (i)' 'à noeud (j)'. Par exemple, vous pourriez dire que la probabilité d'aller de «B» à «A» est de 4/(4 + 2 + 3) = 4/9. Vous mettez ceci dans une matrice qui est tous des zéros, à l'exception des nœuds qui sont directement connectés dans votre graphique. C'est une chaîne de Markov. Maintenant vous pouvez simuler. Recherche sur les processus de Markov dans http://stats.stackexchange.com/, il devrait y avoir quelque chose d'utile là-bas. – giusti

Voici les matrices de transition non normalisées puis normalisées en ligne de la chaîne markov, également illustrées sur la figure. Nous devons calculer les probabilités d'absorption comme indiqué sur la figure.

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

Source

2017-02-24 21:22:00

Soit pxy la probabilité que vous finissez par l'état de terminal Y si vous démarrez dans l'état X.

Vous voulez calculer pAC, Tampographie, pae pBC, pBD PBE.

Par exemple, pour calculer pAC vous avez deux équations:

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

C'est la probabilité que vous finissez en C à partir de A est de 1/2 (quand vous y passez directement), et 1/2 de la probabilité que vous finissiez en C si vous passez d'abord en B. Et si vous commencez en B, la probabilité que vous finissiez en C est si vous passez d'abord à A et de là finissez en C.

En remplaçant la seconde par la première, vous obtenez:

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

Cela vous donne immédiatement pBC = 4/14 = 2/7.

Les 4 autres probabilités peuvent être calculées de la même manière.

Source

2017-02-24 19:53:16

probabilité de chaque nœud terminal dans un graphe orienté

Répondre

Questions connexes