大规模分布式系统架构与设计实战笔记之PageRank

在千峰老师的《大规模分布式系统架构与设计实战》一书中的有一个从赌钱游戏看PageRank算法,以下简称PR算法

首先我们来说下PR算法，PR(A)=(PR(B)/L(B)+PR(C)/L(C)+...+PR(X)/L(X))*q+1-q
其中q为逃脱因子，暂且不去理解它（取q=1），此时有公式PR(A)=PR(B)/L(B)+PR(C)/L(C)+...+PR(X)/L(X)，说白了网页A的PR值等于他的所有入站链接的PR值得和。

但是网页的PR值我们没法孤立出来进行求算，你想啊，比如现在我想算网页A的PR值，那么我得知道链接到A的那些网页的PR值以及他们的L值，而要想知道这些网页的PR和L值，又得算...这就使得我们的求算没有尽头。所以我们得考虑换种方案。

我们可以对于所有的网页，计算它们的出站链接的PR值，就是说计算所有网络中存在的链接的PR值，然后我们以这些链接链接到的网页作为标准分类，最终求得每个网页的PR值。

举例，比如现在我们有3个网页A,B,C,他们互相都有链接，一共有六个链接。按照上面的方案，对于网页A，有出站链接A->B(PR值为PR(A)/2),有出站链接A->C(PR值为PR(A)/2);
对于网页B，有出站链接B->A(PR值为PR(B)/2),有出站链接B->C(PR值为PR(B)/2);
对于网页C，有出站链接C->A(PR值为PR(C)/2),有出站链接C->B(PR值为PR(C)/2);

网络中一共存在6个链接，他们的PR值也已经算出，此时进行统计可以看到，网页A的入站链接有2个，B->A(PR值为PR(B)/2),C->A(PR值为PR(C)/2),则PR(A)=PR(B)/2+PR(C)/2;
以此类推，PR(B)=PR(A)/2+PR(C)/2;PR(C)=PR(A)/2+PR(B)/2;

自此，我们就找到了每个网页PR值的算法，然后我们仅仅需要为PR(A),PR(B),PR(C)赋值，然后进行多轮迭代，就可求出最终的每个网页的PR值。

在PR值得求算过程中，PR值一直在网页之间流动，因此多轮计算后回收敛。

类似这种“并行计算+数据算法”的经典搭配，并且这种“海量数据并行计算，迭代多轮后收敛”的分析过程十分常见。

附件中是书中的源代码

评论

1 楼 beiwang 2014-08-02  

学习了收藏
http://www.tc5u.com