Pagerank在Hadoop上的实现原理

转自：pagerank 在 hadoop 上的实现原理

 

PageRank 算法的基本思想是，网页的热门程度依赖于指向它的网页的热门程度。假设有页面 ，有  这  个页面包含指向  的链接，代表页面  所包含的指向别的页面的链接的数量， 是一个介于 0 和 1 之间的常数（称为阻尼系数，一般取 0.85），则页面 的 PR 值（PageRank 值）

 

 

这个思想也可以由随即散步模型来解释：即从一随机网页起步，以概率  跳到另一随机选择的网页， 或以概率  随机选择一个当前网页上的链接并跟随此链接。一个网页的 PageRank 就是随机散步者在任意给定时刻访问该网页的概率。被许多网页指向的网页更可能被访问，被具有高 PageRank 的网页指向的网页更可能被访问。

 

为了求出各个网页的 PR 值，需要对上述方程组进行迭代求解（每个页面的PR值都可以根据上述公式得到一个方程），直到方程组的解收敛，或变化的范围很小。在本次实验中，第一次迭代每个页面的初始PR值为0.5，当所有页面相邻两次迭代的PR值变化小于0.00001时，程序认为函数已经收敛。

 

实验中的Map函数和Reduce函数的伪代码如下：

function map
input (PageN, RankN) -> (PageA, PageB, PageC ...)
begin
    Nn := the number of outlinks for PageN
    for each outlink PageK
        TempN = RankN/Nn
        output (PageK) -> (PageN, TempN)
    output (PageN) -> (PageA, PageB, PageC ...)
end 
 
function reduce
input   
(PageK) -> (PageN1, TempN1)
(PageK) -> (PageN2, TempN2)
...
(PageK) -> (PageNt, TempNt)
(PageK) -> (PageAk, PageBk, PageCk ...)
begin
    TempK := 0
    for each inlink PageNi
        TempK += TempNi
    RankK = 1 + (TempK - 1) * d
    output (PageK, RankK) -> (PageAk, PageBk, PageCk ...)
end
 
function combine
input   
(PageK) -> (PageN1, TempN1)
(PageK) -> (PageN2, TempN2)
...
(PageK) -> (PageNt, TempNt)
(PageK) -> (PageAk, PageBk, PageCk ...)
begin
    TempK := 0
    for each inlink PageNi
        TempK += TempNi
    output (PageK) -> ("", TempK)
    if has (PageK) -> (PageAk, PageBk, PageCk ...)
        output (PageK) -> (PageAk, PageBk, PageCk ...)
end