グラフ上の偏りのあるランダムウォーク

ネットワーク科学では、グラフ上のバイアス付きランダム ウォークは、進化する変数が現在の状態からさまざまな潜在的な新しい状態のいずれかにジャンプする時間経路プロセスです。純粋なランダム ウォークとは異なり、潜在的な新しい状態の確率は不等です。

グラフ上のバイアスランダムウォークは、ネットワークが複雑すぎる場合や統計的手法で分析するには規模が小さすぎる場合に、無向グラフの構造解析を行って対称性を抽出するためのアプローチを提供します。グラフ上のバイアスランダムウォークの概念は、過去10年間、特に交通やソーシャルネットワークの分野で多くの研究者やデータ企業の注目を集めてきました。^[1]

グラフ上のバイアスランダムウォークについては、分析の目的に応じてさまざまな表現が書かれてきました。無向グラフのメカニズムの一般的な表現は次のとおりです。^[2]

無向グラフでは、ウォーカーは現在のノードからノードに1歩進みます。各ノードに属性があると仮定すると、ノードからノードにジャンプする確率は次のように与えられます。 ${\displaystyle j,}$${\displaystyle i.}$${\displaystyle \alpha _{i},}$${\displaystyle j}$${\displaystyle i}$

${\displaystyle T_{ij}^{\alpha }={\frac {\alpha _{i}A_{ij}}{\sum _{k}\alpha _{k}A_{kj}}},}$

ここで、はからへの辺の位相重みを表す。${\displaystyle A_{ij}}$${\displaystyle j}$${\displaystyle i.}$

実際、歩行者の歩数はノードごとに異なる要因によって偏向している。^[3]${\displaystyle \alpha }$

ネットワークに応じて、属性の解釈は異なります。ソーシャル ネットワーク内の人物の魅力として暗示される場合もあれば、媒介中心性として説明される場合もあります。また、ノード固有の特性として説明される場合もあります。公平なランダム ウォークの場合、グラフ上のランダム ウォークはすべてのノードに対して 1 つです。 ${\displaystyle \alpha }$${\displaystyle \alpha }$

最短経路の場合、ランダムウォーク^[4] は、ノードを通過するすべてのノードペア間の最短経路の合計数です。実際、ウォーカーは以下のように定義される 媒介中心性が高いノードを好みます。${\displaystyle \alpha _{i}}$${\displaystyle i}$

${\displaystyle C(i)={\tfrac {{\text{Total number of shortest paths through }}i}{\text{Total number of shortest paths}}}}$

上記の式に基づくと、バイアスウォークにおけるノードへの再帰時間は次のように表される。^[5]

${\displaystyle r_{i}={\frac {1}{C(i)}}}$

グラフ上のバイアスランダムウォークを用いたアプリケーションは多岐にわたります。そのようなアプリケーションには、拡散の制御、^[6]ソーシャルネットワーク上での製品の宣伝、^[7]動物や微生物の分散と個体群再分布の説明、^[8]コミュニティ検出、^[9]ワイヤレスネットワーク、^[10]検索エンジンなどがあります。^[11]

• 媒介中心性
• コミュニティ構造
• カルバック・ライブラー距離
• マルコフ連鎖
• 最大エントロピーランダムウォーク
• ランダムウォークの近接中心性
• ソーシャルネットワーク分析
• 巡回セールスマン問題

• Gábor Simonyi、「グラフエントロピー: 概要」。Combinatorial Optimization (W. Cook、L. Lovász、P. Seymour 編)。プロビデンス、ロードアイランド州: Amer. Math. Soc.、pp. 399–441、1995 年。
• Anne-Marie Kermarrec、Erwan Le Merrer、Bruno Sericola、Gilles Trédan、「ランダム ウォークによるネットワーク トポロジの品質の評価」、Gadi Taubenfeld (編) 『Distributed Computing』