theory - 有向加重グラフウォーク

Question

接続された有向加重グラフがあります。エッジの重みは、頂点間を移動する確率を表します。頂点の合計から1までのすべてのエッジの重み。グラフには、AとBの2つのシンクが含まれています。グラフの各頂点について、そこから発生する歩行がAに到達する確率とBに到達する確率を知りたいのですが、これはどのような問題ですか。どうすれば解決できますか？

Answer 1

この問題は代数の種類です。頂点から始まるパスの場合、Aに到達する確率は、隣接する各頂点からAに到達する確率の平均であり、エッジの重みで重み付けされます。これをもっと具体的に言いましょう。

Pをグラフの隣接行列とします。つまり、P _i、jは、頂点iから頂点jに移動する確率です。P _A、A = 1に設定します。各頂点に割り当てられた確率のベクトルを取得し、それをPで乗算すると、結果のベクトルには、各頂点の近傍の加重平均が含まれます。私たちが探しているのは、P v=vおよびvA =1で_あるようなベクトルvです。

このベクトルvは、 1の固有値に対応するPの固有ベクトルです。Pは常にそのような固有値を持っていますか？幸いなことに、ペロン-フロベニウスの定理は、それがそうであり、これがPの最大の固有値であることを示しています。次に、解決策は隣接行列Pを形成し、その最大の固有値に対応する固有ベクトルを見つけることです。

おおよその解決策もあります。x _A = 1で、他の要素を0に設定して、頂点確率のベクトルxをとると、 ^kが無限大になると、 Pkxはvに収束します。P ^kは、固有ベクトルよりもkの値が小さい場合の計算が簡単な場合があります。

---

例

次の簡単なグラフを見てみましょう。

頂点をアルファベット順に並べると、グラフに対応する行列Pは次のよ​​うになります。

この行列の固有値は1であり、対応する固有ベクトルは[1 070/7994/79]です。つまり、CからAに到達する正確な確率は70/79であり、Dからは49/79です。Bの答えを計算すると、9/79と30/79になります。これは、まさに私たちが期待していることです。

P ¹⁶ [1 000]の値はおよそ[100.886 0.62]であり、小数点以下6桁まで正確です。