6

NetworkXヒッティングタイムの実装に使用できるかどうか知りたいですか? 基本的に、グラフ内の任意の 2 つのノード間のヒット時間を計算したいと考えています。私のグラフは加重も無向です。ヒット時間を正しく理解すれば、PageRank の考え方と非常によく似ています。

NetworkX が提供する PageRank メソッドを使用してヒット時間を実装するにはどうすればよいですか?

作業を開始するのに適した出発点があるかどうかを教えてください。

私はチェックしました：MapReduce、Python、およびNetworkXです が、それがどのように機能するかはよくわかりません.

4

1 に答える 1

14

networkX問題を解決する必要はありませんnumpy。背後にある数学を理解していれば問題を解決できます。無向で重みのないグラフは、常に [0,1] 隣接行列で表すことができます。nthこの行列の累乗は、次のステップからのステップ数を表し(i,j)ますn。adj の行正規化形式であるマルコフ行列を使用できます。マトリックス。この行列の累乗は、グラフ上のランダム ウォークを表します。グラフが小さい場合は、行列の累乗を取り、(start, end)関心のあるインデックスを調べることができます。最終状態を吸収状態にし、ウォークがスポットに到達すると、それは逃れられません。各パワーnで、 から拡散する確率が得られます(i,j)。ヒット時間は、この関数から計算できます (正確な離散ステップのヒット時間)。

以下は、エッジ リストによって定義された単純なグラフの例です。最後に、このヒット時間関数をプロットします。参照ポイントとして、これは使用されるグラフです。

ここに画像の説明を入力

from numpy import *

hit_idx = (0,4)

# Define a graph by edge list
edges = [[0,1],[1,2],[2,3],[2,4]]

# Create adj. matrix
A = zeros((5,5))
A[zip(*edges)] = 1
# Undirected condition
A += A.T

# Make the final state an absorbing condition
A[hit_idx[1],:] = 0
A[hit_idx[1],hit_idx[1]] = 1

# Make a proper Markov matrix by row normalizing
A = (A.T/A.sum(axis=1)).T

B = A.copy()
Z = []
for n in xrange(100):
    Z.append( B[hit_idx] )
    B = dot(B,A)

from pylab import *
plot(Z)
xlabel("steps")
ylabel("hit probability")
show()

ここに画像の説明を入力

于 2012-03-08T17:14:45.417 に答える