PageRank算法简介及Map-Reduce实现

比眉伴天荒 2022-06-01 05:00 170阅读 0赞

PageRank对网页排名的算法，曾是Google发家致富的法宝。以前虽然有实验过，但理解还是不透彻，这几天又看了一下，这里总结一下PageRank算法的基本原理。

一、什么是pagerank

PageRank的Page可是认为是网页，表示网页排名，也可以认为是Larry Page(google 产品经理)，因为他是这个算法的发明者之一，还是google CEO（^\_^）。PageRank算法计算每一个网页的PageRank值，然后根据这个值的大小对网页的重要性进行排序。它的思想是模拟一个悠闲的上网者，上网者首先随机选择一个网页打开，然后在这个网页上呆了几分钟后，跳转到该网页所指向的链接，这样无所事事、漫无目的地在网页上跳来跳去，PageRank就是估计这个悠闲的上网者分布在各个网页上的概率。

二、最简单pagerank模型

互联网中的网页可以看出是一个有向图，其中网页是结点，如果网页A有链接到网页B，则存在一条有向边A->B，下面是一个简单的示例：

[![201959072629566][]][201959072629566]

这个例子中只有四个网页，如果当前在A网页，那么悠闲的上网者将会各以1/3的概率跳转到B、C、D，这里的3表示A有3条出链，如果一个网页有k条出链，那么跳转任意一个出链上的概率是1/k，同理D到B、C的概率各为1/2，而B到C的概率为0。一般用转移矩阵表示上网者的跳转概率，如果用n表示网页的数目，则转移矩阵M是一个n\*n的方阵；如果网页j有k个出链，那么对每一个出链指向的网页i，有M\[i\]\[j\]=1/k，而其他网页的M\[i\]\[j\]=0；上面示例图对应的转移矩阵如下：

[![202015378717604][]][202015378717604]

初试时，假设上网者在每一个网页的概率都是相等的，即1/n，于是初试的概率分布就是一个所有值都为1/n的n维列向量V0，用V0去右乘转移矩阵M，就得到了第一步之后上网者的概率分布向量MV0,（nXn）\*(nX1)依然得到一个nX1的矩阵。下面是V1的计算过程：

[![202114099185287][]][202114099185287]

注意矩阵M中M\[i\]\[j\]不为0表示用一个链接从j指向i，M的第一行乘以V0，表示累加所有网页到网页A的概率即得到9/24。得到了V1后，再用V1去右乘M得到V2，一直下去，最终V会收敛，即Vn=MV(n-1)，上面的图示例，不断的迭代，最终V=\[3/9,2/9,2/9,2/9\]’：

[![261719185728644][]][261719185728644]

三、终止点问题

上述上网者的行为是一个马尔科夫过程的实例，要满足收敛性，需要具备一个条件：

*  图是强连通的，即从任意网页可以到达其他任意网页：

互联网上的网页不满足强连通的特性，因为有一些网页不指向任何网页，如果按照上面的计算，上网者到达这样的网页后便走投无路、四顾茫然，导致前面累计得到的转移概率被清零，这样下去，最终的得到的概率分布向量所有元素几乎都为0。假设我们把上面图中C到A的链接丢掉，C变成了一个终止点，得到下面这个图：

[![fclkjfljaljfldkjglksajglasgj1][]][fclkjfljaljfldkjglksajglasgj1]

对应的转移矩阵为：

[![fclajsdfkdjsaglkjsdglsajg2][]][fclajsdfkdjsaglkjsdglsajg2]

连续迭代下去，最终所有元素都为0：

[![fclakjsgflkgjlsajgsajg3][]][fclakjsgflkgjlsajgsajg3]

四、陷阱问题

另外一个问题就是陷阱问题，即有些网页不存在指向其他网页的链接，但存在指向自己的链接。比如下面这个图：

[![ljlajkjasglkjsdgkjsgla1][]][ljlajkjasglkjsdgkjsgla1]

上网者跑到C网页后，就像跳进了陷阱，陷入了漩涡，再也不能从C中出来，将最终导致概率分布值全部转移到C上来，这使得其他网页的概率分布值为0，从而整个网页排名就失去了意义。如果按照上面图对应的转移矩阵为：

[![fclajsdfkdjsaglkjsdglsajg2][]][fclajsdfkdjsaglkjsdglsajg2]

不断的迭代下去，就变成了这样：

[![202136578712805][]][202136578712805]

五、解决终止点问题和陷阱问题

上面过程，我们忽略了一个问题，那就是上网者是一个悠闲的上网者，而不是一个愚蠢的上网者，我们的上网者是聪明而悠闲，他悠闲，漫无目的，总是随机的选择网页，他聪明，在走到一个终结网页或者一个陷阱网页（比如两个示例中的C），不会傻傻的干着急，他会在浏览器的地址随机输入一个地址，当然这个地址可能又是原来的网页，但这里给了他一个逃离的机会，让他离开这万丈深渊。模拟聪明而又悠闲的上网者，对算法进行改进，每一步，上网者可能都不想看当前网页了，不看当前网页也就不会点击上面的连接，而上悄悄地在地址栏输入另外一个地址，而在地址栏输入而跳转到各个网页的概率是1/n。假设上网者每一步查看当前网页的概率为a，那么他从浏览器地址栏跳转的概率为(1-a)，于是原来的迭代公式转化为：

[![202158112317322][]][202158112317322]

现在我们来计算带陷阱的网页图的概率分布：

[![202205000122441][]][202205000122441]

重复迭代下去，得到：

[![261719185728644][261719185728644 1]][261719185728644 1]

六、用Map-reduce计算Page Rank

上面的演算过程，采用矩阵相乘，不断迭代，直到迭代前后概率分布向量的值变化不大，一般迭代到30次以上就收敛了。真的的web结构的转移矩阵非常大，目前的网页数量已经超过100亿，转移矩阵是100亿\*100亿的矩阵，直接按矩阵乘法的计算方法不可行，需要借助Map-Reduce的计算方式来解决。实际上，google发明Map-Reduce最初就是为了分布式计算大规模网页的pagerank，Map-Reduce的pagerank有很多实现方式，我这里计算一种简单的。

考虑转移矩阵是一个很多的稀疏矩阵，我们可以用稀疏矩阵的形式表示，我们把web图中的每一个网页及其链出的网页作为一行，这样第四节中的web图结构用如下方式表示：

XHTML

A有三条出链，分布指向A、B、C，实际上，我们爬取的网页结构数据就是这样的。

1、Map阶段

Map操作的每一行，对所有出链发射当前网页概率值的1/k，k是当前网页的出链数，比如对第一行输出<B，1/3\*1/4>,<C，1/3\*1/4>,<D，1/3\*1/4>;

2、Reduce阶段

Reduce操作收集网页id相同的值，累加并按权重计算，pj=a\*(p1+p2+…Pm)+(1-a)\*1/n，其中m是指向网页j的网页j数，n所有网页数。

思路就是这么简单，但是实践的时候，怎样在Map阶段知道当前行网页的概率值，需要一个单独的文件专门保存上一轮的概率分布值，先进行一次排序，让出链行与概率值按网页id出现在同一Mapper里面，整个流程如下：

[![211557326376640][]][211557326376640]

这样进行一次迭代相当于需要两次MapReduce，但第一次的MapReduce只是简单的排序，不需要任何操作，用python调用Hadoop的Streaming.

SortMappert.py代码如下:

XHTML

SortReducer.py也是一样

XHTML

PageRankMapper.py代码:

XHTML

PageRankReducer.py代码:

XHTML

在linux下模仿Map-Reduce的过程：

XHTML

这个代码不用改动就可以直接在hadoop上跑起来。调用hadoop命令：

XHTML

关于使用python操作hadoop可以查看参考文献。python代码写得浓浓的C味，望海涵！

第四步中带环的陷阱图，迭代40次，权值a取0.8，计算结果如下：

Python

可以看到pagerank值已经基本趋于稳定，并与第四步的分数表示一致。

[201959072629566]: /images/20220601/5ce086a3e1bc4cf5a666dbe1b45ae57a.png
[202015378717604]: /images/20220601/6e82341cfe804010ab98ce555906ab95.png
[202114099185287]: /images/20220601/5aa72c32e2e64f879112a6747f93c6fb.png
[261719185728644]: /images/20220601/a567963a936c4443bfec70a8a9b549d0.png
[fclkjfljaljfldkjglksajglasgj1]: /images/20220601/a9d0eeea57e24985bf661dc175f1f8d9.png
[fclajsdfkdjsaglkjsdglsajg2]: /images/20220601/c385fcd7e7834f2bb2a6d44ab35cfc67.png
[fclakjsgflkgjlsajgsajg3]: /images/20220601/931875f1e159407e909fd7aa483cd72e.png
[ljlajkjasglkjsdgkjsgla1]: /images/20220601/ef1ba886ed0f4a43a40f27d1310c0e6f.png
[202136578712805]: /images/20220601/2d822c0a08c543d4a5ccf980ccdfeaa3.png
[202158112317322]: /images/20220601/3b79a23f0e4f4414a7470d36e4259caf.png
[202205000122441]: /images/20220601/87bee26f869942a3a22bd4f89136fb2a.png
[261719185728644 1]: /images/20220601/8d4fb337d1c2466893a82be74ea0d40d.png
[211557326376640]: /images/20220601/f0452c6d40d846c4a29983ba73293845.png