3

ノード = 61634、エッジ = 28,378 の加重 DiGraph で PageRank を実行しています。

  • pagerank(G)私にZeroDivsionErrorをスローします

  • pagerank_numpy(G)ValueError : array to big をスローします

  • pagerank_scipy(G)ページランクを教えてくれます

エラーがメモリの制限によるものであることは理解できpagerank_numpyますが、ページランクが失敗するのはなぜですか? 重みがゼロのエッジに無限小の値を追加しようとしましたが、同じ問題が続きます。いくつかのポインタがいいでしょう。

私の GraphML ファイルへのリンク - https://mega.co.nz/#!xlYzEDAI!Lyh5pD-NJL61JPfkrNyJrEm0NnFc586A0MUD8OMYAO0

NetworkX バージョン - 1.8.1 Python - 2.7

4

2 に答える 2

4

@ mtitan8の答えは良いですが、話にはもう少しあります。

元の質問の時点から NetworkX コードが変更されたため、pagerank()、pagerank_numpy()、および pagerank_scipy() はすべて、ゼロまたは負の重みがある場合に同じ答えを返します ( https://github.com/networkx/networkx /プル/1001 )

負の重みがある場合にこれらの関数によって生成される結果は、おそらくあなたが望むものではありません (まったく機能する場合)。アルゴリズムが入力行列 (グラフの加重隣接行列) から「Google 行列」を作成する方法は、それがゼロでない限り、行が行の合計で除算されることです (その後、行全体がゼロに設定されます)。 . その合計はマイナスになる可能性があります。

結果の行列が依然として負のエントリで終わる場合、ペロン-フロベニウスの定理は適用されません http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theoremと一意の最大固有値を持つことが保証されません正の値の固有ベクトルを使用します。

于 2013-11-12T23:58:46.663 に答える
2

pagerankstochastic_graph-- とは異なりpagerank_numpyまたはを使用して計算を実行するため、失敗しますpagerank_scipy。ドキュメントから、stochastic_graph次が必要です。

NetworkX グラフには、有効なエッジの重みが必要です

この「有効なエッジの重み」ポイント (まったく説明されていませんが、これは間違いだと思います) が問題の原因です。

有向グラフの場合、各ノードの をstochastic_graph使用してエッジを正規化します。out_degree再びドキュメントから：

[out] 次数は、ノードに隣接するエッジの重みの合計です。

したがって、ゼロの重みまたは負の重みを持つエッジがある場合、正規化プロセスはZeroDivisionError. 負の重みが問題になる理由は、負の重みが正の重みを打ち消し、ノードの次数がゼロになる可能性があるためです。たとえば、グラフでは、ノード'2123271'には重みの合計が になる 2 つのエッジがあり0ます。

>>> G.edges('2123271', data=True)
[('2123271', '1712899', {'weight': -1L}),
 ('2123271', '890839', {'weight': 1L})]

グラフ内の負またはゼロのエッジの重みを小さな正のエッジの重みに置き換えると、pagerank次のように実行できるようになりました。

In [1]: import networkx as nx
In [2]: G = nx.read_graphml("your_graph.graphml")
In [3]: defaultEdgeWeight = 0.01
In [4]: for u, v, d in G.edges(data=True):
            if d['weight'] <= 0:
                G[u][v]['weight'] = defaultEdgeWeight
In [5]: P = nx.pagerank( G )

もちろん、pagerank102 回の反復後に収束しませんでしたが、それは別の問題です。

于 2013-11-05T20:00:15.557 に答える