Pagerank在Hadoop上的实现原理

13719654321

　　转自：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