Implementando PageRank usando MapReduce

Question

Estoy tratando de resolver un problema con la teoría de implementar el PageRank con MapReduce.

Tengo el siguiente escenario simple con tres nodos: AB C.

la matriz de adyacencia es aquí:

A { B, C } 
B { A } 

El PageRank para B, por ejemplo, es igual a:

(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 

Estoy bien con todos los esquemas y cómo funcionarían el asignador y el reductor, pero no entiendo cómo al momento del cálculo con el reductor, se conocería C (A). ¿Cómo el reductor, al calcular el PageRank de B al agregar los enlaces entrantes a B sabrá la cantidad de enlaces salientes de cada página? ¿Esto requiere una búsqueda en alguna fuente de datos externa?

Answer 1

Evaluamos iterativamente PR. PR (x) = Suma (PR (a) * Peso (a), una en in_links) por

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) 

lo que la salida es igual a la entrada y podemos hacer esto hasta que la cobertura.

Answer 2

A detailed explanation with Python code, por Michael Nielsen.

Answer 3

Aquí es un pseudocódigo:

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) 

Es importante que en el que debería reducir outlinks de salida y no inlinks, ya que algunos artículos sobre el intenret sugiere. De esta forma, las iteraciones consecutivas también tendrán enlaces externos como entrada del asignador.

Preste atención a que múltiples enlaces externos con la misma dirección de la misma página cuentan como uno. Además, no cuente los bucles (enlaces de página a sí mismo).

El factor de amortiguación es tradicionalmente 0.85, aunque también puede jugar con otros valores.