pagerank 算法

背景

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 表示直接输入网址跳转过来的概率。

下面对上面公式进行推广：

：网页中网页的总数；

d：阻尼因子，通常设为0.85，d即按照超链接进行浏览的概率；

1-d:用户手动输入网址随机跳转一个新页面的概率；

：网页的PR值；

：网页的链出网页数目；

写成矩阵形式：

上面式子中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 D2. B A D3. C 04. 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的。

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