大背景

pageRank 是Google CEO 乔纳森凯斯明确提出的一类演算法，来排序网络里的中文网站的关键性，以对搜寻展开名列。

该处咋演算法叫pagerank，即使是以Google子公司创办者乔纳森·凯斯（Larry Page）之姓来重新命名。因此为的是有名，我们不懈努力的，发明者个演算法，以他们英文名字来重新命名的。

pagerank 基本上价值观

• 数目假定：两个页面越被其它页面镜像，表明他越关键（ps：想必好些控制技术网志的都相互镜像）
• 产品质量假定：越被高效率页面镜像，表明该页面越关键（ps：最合适能被大写手所推荐新一波，影迷蹭蹭蹭往下跌）

pagerank 数学模型

pagerank 开氏度的是两个使用者在网络上下载到每一页面的机率。

上面来两个单纯排序，更快的认知下

pg（A） = pg（C）/1 + pg(B) /2

A页面的pagerank值由页面B和页面C的pagerank贡献而来，即使B页面有两个外链，假定等机率贡献，则贡献给A的值为自身的一半。

再看两个例子

该处C即使没有外链，因此我们假定他给其它所有页面都贡献了pg，于是：

pg(A) = pg（C）/4 + pg(B) /2

在考虑两个情况，即使用者在下载页面的过程中，直接输入新网址展开下载，即两个页面都有可能跳转到任意其它页面，于是针对下图：

pg(A) = （a * pg(B) /2） + (1-a) / 4)

上面公式的含义是：

在任意时刻，使用者到达某页面后并继续向后下载的机率为a，则使用者停止下载的机率为(1-a)，此时使用者停止下载后，可能会直接通过输入下载器地址展开下载页面，此时跳转到任意网址的机率都一样，于是上面的 a * pg(B) /2 表示从b跳转过来的机率，(1-a) / 4 表示直接输入网址跳转过来的机率。

上面对上面公式展开推广：

写成矩阵形式：

上面式子中l(pi,pj)表示页面j指向页面i,其值为:

l(pi,pj) = 1 / L(pj)

其中L(pj)表示pj外链的数目。

排序示例

上面我们来看两个具体的例子，假定有如下图：

根据上面的矩阵，我们可以得到上面的矩阵：

于是整个迭代公式为：

注意：pagerank如果只考虑从其它页面转移过来，会出现上面的两个问题：

• 终止点问题：只入不出，则所有节点的机率最后会变为0
• 陷阱问题：页面只有指向他们的镜像，则最后所有的机率都会转移到这些中文网站

更具体的解释可以看 PageRank演算法简介及Map-Reduce实现

map reduce 实现

mapreduce关键在于设计map和reduce，先来看pr值的排序公式：

因此每一pr值都是由其它页面pr值贡献得到，因此我们还是以下图为例子：

1. A B C D
2. B A D
3. C 0
4. D B

现在每一行输入到map中，map输出为：

（B,1/3*pg(A)）
（C,1/3*pg(A)）
（D,1/3*pg(A)）

该处我们发现缺少的为每一页面的当前pg值，另外每一页面的pg值是单独存放的，因此我们需要先来两个map-reduce，将pg值映射到每一对应的行，具体流程如下图：

图片来自：PageRank演算法简介及Map-Reduce实现

总结

本文是对pagerank演算法的两个单纯总结，pagerank主要价值观就是模拟网络使用者下载页面的行为，从而排序出停留在每一页面的机率，关于pg更多的信息可以google的。

你的鼓励是我继续写下去的动力，期待我们共同进步。