11

MapReduce を使用して PageRank を実装するという理論に関する問題を回避しようとしています。

次の 3 つのノードを持つ単純なシナリオがあります: AB C.

隣接行列は次のとおりです。

A { B, C }
B { A }

たとえば、B の PageRank は次のようになります。

(1-d)/N + d ( PR(A) / C(A) ) 

N     = number of incoming links to B
PR(A) = PageRank of incoming link A
C(A)  = number of outgoing links from page A

私はすべての回路図とマッパーとレデューサーがどのように機能するかについては問題ありませんが、レデューサーによる計算時に C(A) がどのように認識されるかについて頭を悩ませることができません。レデューサーは、B への着信リンクを集計して B の PageRank を計算するときに、各ページからの発信リンクの数をどのように知るのでしょうか。これには、外部データ ソースでのルックアップが必要ですか?

4

3 に答える 3

19

擬似コードは次のとおりです。

map( key: [url, pagerank], value: outlink_list )
    for each outlink in outlink_list
        emit( key: outlink, value: pagerank/size(outlink_list) )

    emit( key: url, value: outlink_list )

reducer( key: url, value: list_pr_or_urls )
    outlink_list = []
    pagerank = 0

    for each pr_or_urls in list_pr_or_urls
        if is_list( pr_or_urls )
            outlink_list = pr_or_urls
        else
            pagerank += pr_or_urls

    pagerank = 1 - DAMPING_FACTOR + ( DAMPING_FACTOR * pagerank )

    emit( key: [url, pagerank], value: outlink_list )

インテレットに関するいくつかの記事が示唆しているように、リデュースではインリンクではなくアウトリンクを出力することが重要です。このようにして、連続する反復にもマッパーの入力としてアウトリンクが含まれます。

同一ページからの同一アドレスへの複数のアウトリンクは1つとして数えますのでご注意ください。また、ループ (ページ自体へのリンク) もカウントしないでください。

ダンピング ファクターは伝統的に 0.85 ですが、他の値をいじることもできます。

于 2012-11-26T15:49:17.667 に答える
4

Michael Nielsen によるPython コードによる詳細な説明。

于 2011-02-17T23:21:41.160 に答える
1

PRを繰り返し評価します。PR(x) = Sum(PR(a)*weight(a), in_links の a) by

map ((url,PR), out_links) //PR = random at start
for link in out_links
   emit(link, ((PR/size(out_links)), url))

reduce(url, List[(weight, url)):
   PR =0
   for v in weights
       PR = PR + v
   Set urls = all urls from list

   emit((url, PR), urls)

したがって、出力は入力と等しくなり、カバレッジまでこれを行うことができます。

于 2011-02-17T13:50:33.417 に答える