Реализация PageRank с использованием MapReduce - PullRequest
Новая
       17

Реализация PageRank с использованием MapReduce

8 голосов
/ 17 февраля 2011

Я пытаюсь решить проблему с теорией реализации PageRank с MapReduce.

У меня есть следующий простой сценарий с тремя узлами: AB C.

Матрица смежности здесь: 

A { B, C }
B { A }

PageRank для B, например, равен: 

(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) будет известен.Как будет работать редуктор, при расчете PageRank от B путем агрегирования входящих ссылок на B будет известно количество исходящих ссылок с каждой страницы.Требуется ли поиск в каком-либо внешнем источнике данных?

Ответы [ 3 ]

16 голосов
/ 26 ноября 2012

Вот псевдокод: 

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 )

Важно, чтобы при сокращении вы выводили ссылки, а не ссылки, как предлагают некоторые статьи об интретре. Таким образом, последовательные итерации также будут иметь исходящие ссылки в качестве входных данных преобразователя.

Обратите внимание, что несколько исходящих ссылок с одним и тем же адресом на одной странице учитываются как одно. Кроме того, не считайте циклы (страница, ссылающаяся на себя).

Коэффициент демпфирования традиционно составляет 0,85, хотя вы можете поиграть и с другими значениями.

3 голосов
/ 18 февраля 2011
1 голос
/ 17 февраля 2011

Мы итеративно оцениваем PR.PR (x) = Сумма (PR (a) * weight (a), a in in_links) на 

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)

, поэтому выходной сигнал равен входному значению, и мы можем делать это до покрытия.

...