1

約 100 万のノードと 1,000 万のエッジを含むスパース グラフがあります。各ノードのパーソナライズされたPageRankを計算したいのですが、ノード n でのパーソナライズされた PageRank とは、次のことを意味します。

# x_0 is a column vector of all zeros, except a 1 in the position corresponding to node n
# adjacency_matrix is a matrix with a 1 in position (i, j) if there is an edge from node i to node j

x_1 = 0.5 * x_0 + 0.5 * adjacency_matrix * x_0
x_2 = 0.5 * x_0 + 0.5 * adjacency_matrix * x_1
x_3 = 0.5 * x_0 + 0.5 * adjacency_matrix * x_2

# x_3 now holds the personalized PageRank scores

# i'm basically approximating the personalized PageRank by running this for only 3 iterations

NumPy を使用してこれをコーディングしようとしましたが、実行に時間がかかりすぎました。(ノードごとにパーソナライズされた PageRank を計算するのに約 1 秒)

また、x_0 を行列に変更しようとしましたが (いくつかの異なるノードの列ベクトルを結合することによって)、これもあまり役に立たず、実際には計算にかなりの時間がかかりました。（おそらく、行列がかなり急速に密になり、RAMに収まらなくなったためでしょうか？よくわかりません）

できればPythonで、これを計算する別の提案された方法はありますか? また、PageRank の計算に非マトリックス アプローチを採用することも考えました。これは、一種のランダム ウォークのシミュレーションを 3 回繰り返すことで実現しました (つまり、各ノードをスコア 1 で開始し、このスコアを隣接するノードに伝播するなど)。しかし、これがより速くなるかどうかはわかりません。もしそうなら、なぜですか？

4

2 に答える 2

1

あなたの場合、データが正しい方法で保存されていれば、シミュレートされたランダムウォークの反復アプローチを使用するとうまくいくはずです。ノードの数に比べてエッジが非常に少ない場合（あなたの場合のように）、マトリックスアプローチは非常にスパースなマトリックスであるため、適切な選択ではないと思いますが、実際には、このアプローチは、任意のiおよびjに対してiからjまでのノードの存在。（ちなみに、これらのゼロの乗算に実際にかかる実行時間はわかりません。）

各ノードオブジェクトについて、その発信リンクの宛先のリストがあるようにデータを保存している場合、ランダムウォークシミュレーションアプローチはかなり高速になります。減衰係数を無視すると、これはランダムウォークシミュレーションの各反復で実際に行うことです。

for node in nodes:
    for destination in node.destinations:
        destination.pageRank += node.pageRank/len(destinations)

その場合、各反復の時間計算量はO（n * k）になります。ここで、n=1mおよびk=10です。私がここで何も見逃していないのであれば、これは良さそうです。

于 2012-08-21T21:05:35.093 に答える
1

「PageRank」アルゴリズムは、有向グラフhttp://en.wikipedia.org/wiki/Directed_graph (おそらく適切な重み付け)として表示するのが最適であると考えていました。

http://networkx.lanl.orgnetworkxのライブラリが好きです

適応できる可能性のあるアルゴリズムの下に「PageRank」の例もあります。

于 2012-07-16T06:28:40.107 に答える