SEO篇章:专注于SEO优化,分享最新搜索引擎新闻动态!再牛逼的技术,也抵不过冒着傻气的坚持!

SEO优化 > SEO资讯 / PageRank算法之Google详解

PageRank算法之Google详解

SEO篇章 2016-08-31 13:45:12 SEO资讯

  PageRank算法PageRank算法是谷歌曾经独步天下的“倚天剑”,该算法由Larry Page和Sergey Brin在斯坦福大学读研时发明的,论文点击下载: The PageRank Citation Ranking: Bringi...

PageRank算法

PageRank算法是谷歌曾经独步天下的“倚天剑”,该算法由Larry Page和Sergey Brin在斯坦福大学读研时发明的,论文点击下载: The PageRank Citation Ranking: Bringing Order to the Web。

本文首先通过一些参考文献引出问题,然后给出了PageRank的几种实现算法,最后将其推广至在MapReduce框架下如何实现PageRank算法。

PageRank的核心思想有2点:

1.如果一个网页被很多其他网页链接到的话说明这个网页比较重要,也就是pagerank值会相对较高;

2.如果一个pagerank值很高的网页链接到一个其他的网页,那么被链接到的网页的pagerank值会相应地因此而提高。

下面是一张来自WikiPedia的图,每个球代表一个网页,球的大小反应了网页的pagerank值的大小。指向网页B和网页E的链接很多,所以B和E的pagerank值较高,另外,虽然很少有网页指向C,但是最重要的网页B指向了C,所以C的pagerank值比E还要大。

PageRank算法之Google详解

参考内容:

1.Wiki about PageRank

2.Google 的秘密- PageRank 彻底解说 中文版

3.数值分析与算法 Page 161 应用实例:Google的PageRank算法

4.Numeric Methods with Matlab 或者中文翻译版本Matlab数值计算

5.使用 MapReduce 思想计算 PageRank Page 62 PageRank和马尔可夫链


  1. 问题背景

来自参考内容3

2.jpg


2.数学建模

来自参考内容3,理解网页连接矩阵$G$,马尔科夫过程(“网上冲浪”),转移矩阵$A$,概率$p$为用户点击当前网页中的某个链接地址的概率(一般都为0.85)。

3.jpg

4.bmp

最后得到一个等式$Ax=x$,这实际上就是求矩阵$A$的特征值为1的特征向量!

下面的内容使用圆盘定理解释了1是矩阵$A$的主特征值,所以我们可以使用幂法来求解。

关于幂法的详细介绍参考另一篇文章Numerical Methods Using Matlab: 第三章 矩阵特征值和奇异值求解

5.jpg

6.jpg

3.求解PageRank

假设有如上图右侧所示的网页链接模型。

(1) 幂法

wiki上有一个PageRank的简便算法,它不考虑转移概率,而是采用的是迭代的方式,每次都更新所有网页的pagerank值,更新的方式就是将每个网页的pagerank值平摊分给它指向的所有网页,每个网页累计所有指向它的网页平摊给它的值作为它该回合的pagerank值,直到全部网页的pagerank值收敛了或者满足一定的阈值条件就停止。

后面的MapReduce框架下PageRank算法的实现就采用了这个思想。考虑转移概率的情况和这个算法类似,乘上一个转移概率再加上一个随机跳转的概率。

7.jpg

根据上面的思想,下面Matlab代码实现可以得到各个网页的PageRank值。

8.jpg

得到的向量$x$保存了各个网页的pagerank值,虽然链接数目一样,但是网页①比网页④和网页⑤都高,而网页②的pagerank值第二高,因为网页①链接到了它上面,相当于沾了网页①的光。

9.jpg

这篇文章给出该算法的一个Python版本实现,该博主使用第三方模块python-graph,python-graph模块实现了很多图算法,该模块的使用示例,使用前需要先安装,代码如下:

1.jpg

Python版本的算法实现:

2.jpg

3.jpg

4.jpg

经过32次迭代之后得到的结果如下,和前面的结果一致:

5.jpg

(2) 利用马尔可夫矩阵的特殊结构

来自参考内容4,其中$delta=frac{1-p}{n}$

7.jpg

也就是将矩阵$A$进行分解,并不需要显示求出矩阵$A$,然后便是求解一个线性方程组即可。

8.jpg

(3) 巧妙解法:逆迭代算法

巧妙利用Matlab中的精度误差导致原本是一个奇异矩阵的$I-A$变成一个非奇异矩阵,运行时只是会有些警告提示,但是运行结果和其他算法一样。

9.jpg

1.jpg

最后,附上参考内容4中给出的一份好代码,用于模拟随机冲浪生成矩阵$G$的代码


2.jpg

3.jpg

4.jpg

5.jpg

4.MapReduce框架下PageRank算法的实现

利用前面wiki上的迭代(或者幂法)的思想来实现MapReduce框架下PageRank算法很简单,可以先阅读下参考内容5。

这篇文章using-mapreduce-to-compute-pagerank更加详细,可以参考

以下是我的大数据的一次作业,要求是参考wiki上的简便算法,实现MapReduce框架下的PageRank算法。给的数据集是Twitter的用户之间的关系,可以看做是网页之间的关系,但是助教没要求写代码以及运行这个数据集(有1G多),所以下面只是一个Python版本的理想可行版本,并没有通过实际大数据集的验证,另外,博主暂时还不太会Python的mapreduce框架中的一些函数,所以实现的是一个简明的可以测试的PageRank算法。

1.输入输出格式

map函数的输入是<节点,从该节点引出的边列表>,其中节点是一个类,包含了其当前的pagerank值,输出是<节点,反向节点pagerank值/反向节点引出边的总数>;

reduce函数的输入是<节点,反向节点pagerank值/反向节点引出边的总数>,输出是<节点,从该节点引出的边列表>,其中节点包含了其更新后的pagerank值。

伪代码: [一时犯二写了个英文形式的 ]

11.jpg

2.示例演示

假设用户1,2,3,4是如下图所示的关系:12.png

假设有2个mapper(A和B)和1个reducer(C),初始时4个节点的pagerank值都是0.25

其中,关于用户1和2的数据被mapperA读取并处理,关于用户3和4的数据被mapperB读取并处理 [经验证,即使一个用户的数据是由不同的mapper来读取的,最终收敛到的结果差不多]

map的输入输出结果如下:

13.png

reduce的输入输出结果如下,输入是2个mapper的输出,输出的结果中更新了节点的pagerank值

14.png

reducer处理完了之后又将它的结果输入给mapper处理,直到迭代的次数超过了设定值或者两次迭代之后得到的所有节点的pagerank值之差的总和(也可以是取二范数)小于设定的阈值。

3.示例的实验结果

(1)首先是使用Matlab采用幂法的方式计算出在p=1.0的情况下示例得到的结果 [它的主要作用是验证后面python版本的正确性]

matlab源码如下:

15.jpg

结果为:

16.jpg

(2)matlab版本的page rank没有采用mapreduce的思想进行迭代,所以我另外写了一个python版本的利用mapreduce思想实现的pagerank算法(注:我并没有使用python的map和reduce函数去实现,而是使用更加容易明白的实现),使用的阈值为0.0001,最多迭代的次数为100次。

17.jpg

18.jpg

19.jpg

得到的结果为如下,总共迭代了15次

20.jpg

上面的结果和Matlab用幂法得到的pagerank值差别很小,可以认为是正确的,所以说明了使用这种mapreduce输入输出格式的正确性。

OK,差不多了,希望对需要理解PageRank算法的人有帮助!


本文地址:https://www.seopz.com/seozixun/1970.html

当前位置:SEO优化 > SEO资讯 > PageRank算法之Google详解

Tags:seo资讯

搜索
网站分类
标签列表