搜索引擎PageRank算法介绍及实现

今天来讲一下搜索引擎的PageRank算法

一、算法介绍

早期的搜索引擎大都采用分类检索的方式，即靠人工辨别来对网站进行分类,类似hao123这样的网站。

随着时代的发展，网页变得越来越多，用人工识别的方式对网页进行识别变得越来越不现实，搜索引擎开始采用文本检索的方式来对返回用户所查询的信息，就是根据用户搜索的文本与网页内容的相关联程度来返回搜索的网站。但是这种方法的搜索结果不好，因为，有一些网站采用作弊的方式，在网页中添加许多关键词来提高自己的排名，在这种情况下，Google的两名创始人Larry Page与Sergey Brin开始对网页排序问题进行研究，依据学术界评判论文的重要程度的方法，查看论文引用次数，将这种方法用到了网页排序中，PageRank算法就产生了。

PageRank算法是最流行的基于链接的方法来确定页面的全局相关性或重要性。PageRank算法分配一个重要的分数比（页面排名），对于指向它的其他网页。一个页面的分数，由所有指向它的页面的分数来确定即一个页面的排名是由所有指向它的页面的重要性经过递归算法得到。一个页面如果有较多的链如页面便会有较高的等级，相反，如果一个页面没有任何链入页面，那么它没有等级。

二、公式实现

PageRank算法中页面p的得分可用r(p)来计算，计算公式如下：

其中是α衰减因子,一般取值0.8或0.85，outdegree(q)是页面q指向页面p的出度，N为页面的数量。

上面公式可简化如下：

初始化R的值均为1/N。

如果PageRank算法被执行在网站的链接结构上，每个网站会有一个全局重要性分数。如果网站被按照他们的PageRank算法分数从大到小排序，那些位于序列顶端的网站被认为是值得信赖的。在这些网站汇总标签为可信赖的网站被选作种子。

在上面的公式之中，我们能看出页面p的PageRank算法分数是由两个部分组成。一部分来自指向它的页面，另一部分来自其他所有页面的平均值。前者说明指向一个网页的重要网页越多这个页面就越重要。结果，PageRank算法高排名的页面都有很高的入度。

三、算法示例

我们首先设计一个简单的网络链接关系图，每个圆代表一个网站，然后圆之间的箭头代表网站之间的链接关系：

初始化：

通过公式不断地迭代运算，最后得到结果R。