私はグラフマイニングの分野で働いている博士課程の学生です。人々は、グラフ内のノード間の類似性をトラバースして計算する際に、グラフ内でランダム ウォークの概念を使用してきました。ランダムウォークがグラフ上でどのように機能するかを誰か教えてもらえますか? 特に、グラフ内の任意の 2 つのノード/頂点を測定するために使用すると...??? 効果的で有益な返信を待っています... :roll:
1 に答える
1
大まかに言えば、2つのノード間に多くの可能なパスがある場合、それらの間に可能なパスがほとんどない別のノードのペアと比較すると、これら2つのノード間でランダムウォークが発生する可能性が高くなります。この意味で、2つのノード間のランダムウォークの確率は、グラフで接続されていないノードに類似関係を拡張します。
2つの側面はかなり重要です。まず、通常、特定のランダムグラフ、つまりノードから出て行くすべてのエッジ（アーク）の重みを合計して1に正規化することによって得られるグラフを検討します。元のエッジの重みを使用してサンプリング手順を実行するアプローチもありますが、明示的な構成の方が便利です。これにより、マルコフ行列と考えることができるマルコフグラフが得られます。次に、この正規化アプローチは、外れ値が突然他のノードに近づく可能性があるという意味で、エッジの重みの意味を変更します。つまり、ノードAがノードBおよびCに類似性10および40で接続され（他のノードはない）、ノードZがノードBおよびCに類似性1および4で接続されている（他のノードはない）場合、両方のA Zは、それぞれBとCへの遷移確率0.2と0.8になります。
このアプローチの利点は、エッジの重みが自然に考慮されることです。エッジの重みが高いほど確率が高くなり、1より長い歩行の確率は、マルコフ行列の乗算として非常に自然に低下します。比較すると、ランダムウォークの正規化ステップなしで計算された2つのノード間のパスの総数（またはこれの加重バージョン）は、非常に速く爆発し、エッジまたは三角形の密度の局所的な変動によって大きく歪む可能性があります。
このような定式化を使用する1つのアルゴリズムは、クラスタリングアルゴリズムMCLです。もう1つのアプリケーションはランダムウォーク間であり、これもクラスタリングを使用するために適用できます。ラベルの伝播方法も同様の考え方を使用しているようです。
于 2012-10-02T13:03:49.360 に答える