Implémentation du PageRank en utilisant MapReduce

Question

J'essaie de résoudre un problème avec la théorie de l'implémentation du PageRank avec MapReduce.

Je le scénario simple suivant avec trois nœuds: AB C.

La matrice de contiguïté est ici:

A { B, C } 
B { A } 

Le PageRank B par exemple, est égal à:

(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 

Je vais bien avec tous les schémas et comment le mapper et le réducteur fonctionneraient mais je ne peux pas comprendre comment au moment du calcul par le réducteur, C (A) serait connu. Comment le réducteur, en calculant le PageRank de B en agrégeant les liens entrants à B connaîtra le nombre de liens sortants de chaque page. Cela nécessite-t-il une recherche dans une source de données externe?

Answer 1

Nous évaluons itérativement PR. PR (x) = Somme (PR (a) * poids (a), un à in_links) par

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) 

de sorte que la sortie est égale à l'entrée et nous pouvons le faire jusqu'à ce que la couverture.

Answer 2

A detailed explanation with Python code, par Michael Nielsen.

Answer 3

Voici un pseudo-code:

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) 

Il est important que dans la réduction, vous devriez outlinks de sortie et non inlinks, comme certains articles sur le intenret suggère. De cette façon, les itérations consécutives auront également des sorties en entrée du mappeur.

Faites attention à ce que plusieurs sorties avec la même adresse de la même page comptent pour un. De même, ne comptez pas les boucles (page qui se lie à elle-même).

Le facteur d'amortissement est traditionnellement de 0,85, bien que vous puissiez aussi jouer avec d'autres valeurs.