2.5.14　从赌钱游戏看PageRank算法

2.5.14　从赌钱游戏看PageRank算法

谈到并行计算应用，会有人想到PageRank算法，我们有成千上万的网页分析链接关系确定排名先后，借助并行计算完成是一个很好的场景。长期以来，Google的发明PageRank算法吸引了很多人学习研究，据说当年Google创始者兴奋地找到Yahoo公司，说他们找到一种更好的搜索引擎算法，但是被Yahoo公司技术人员泼了冷水，说他们关心的不是更好的技术，而是搜索的盈利。后来Google包装成了“更先进技术的新一代搜索引擎”的身份，逐渐取代了市场，并实现了盈利。

由于PageRank算法有非常高的知名度和普及度，我们接下来以PageRank算法为例讲述“并行计算+数据算法”的经典搭配，并且这种“海量数据并行处理、迭代多轮后收敛”的分析过程也跟其他的数据挖掘或者机器学习算法应用类似，能起到很好的参考作用。

下面是PageRank算法的公式：

2.5.14　从赌钱游戏看PageRank算法 - 图1

我们其实可以直接阐述该公式本身，并介绍如何使用并行计算套用上面公式得到各网页的PageRank值，这样虽然通过并行计算方式完成了PageRank计算，但是大家仍然不明白上面的PageRank公式是怎么来的。

我们把这个PageRank算法公式先放在一边，看看一个赌钱的游戏。有甲、乙、丙三个人赌钱，他们的输赢关系如下：

❏　甲的钱输给乙和丙。

❏　乙的钱输给丙。

❏　丙的钱输给甲。

例如，甲、乙、丙各有本钱100元，按照以上输赢关系，玩一把下来：

❏　甲输给乙50元、输给丙50元。

❏　乙输给丙100元。

❏　丙输给甲100元。

如果仅是玩一把的话很容易算出谁输谁赢。但如果他们几个人维持这样的输赢关系，赢的钱又投进去继续赌，这样一轮一轮赌下去的话，最后会是什么样子呢？

我们可以写个单机程序看看，为了方便计算，初始本钱都设为1块钱，用x1、x2、x3代表甲、乙、丙：

double x1=1.0,x2=1.0,x3=1.0;

用x1_income，x2_income，x3_income代表每赌一把后各人赢的钱，根据输赢关系列出如下表达式：

double x2_ income =x1/2.0;
double x3_ income =x1/2.0+x2;
double x1_ income =x3;

最后再把各人赢的钱覆盖掉本钱，继续往下计算。

完整程序如下：

// Gamble单机程序
public class Gamble
{
        public static double x1=1.0,x2=1.0,x3=1.0;
 
public static void playgame(){
           double x2_income=x1/2.0;
           double x3_income=x1/2.0+x2;
           double x1_income=x3;
           x1=x1_income;
           x2=x2_income;
           x3=x3_income;
           System.out.println("x1:"+x1+", x2:"+x2+", x3:"+x3）;
        }
 
        public static void main(String[] args){
           for(int i=0;i<500;i++){
               System.out.print("第"+i+"轮 ");
               playgame();
           }
        }
}

我们运行500轮后，看到结果如图2-38所示。

2.5.14　从赌钱游戏看PageRank算法 - 图2

图2-38　Gamble

我们发现，从107轮后，各人的输赢结果就一直是x1：1.2000000000000002，x2：0.6000000000000001，x3：1.2000000000000002

……

可能你都没想到会有这么个规律，这样一直赌下去，虽然各人每轮有输有赢，但是多轮后的输赢结果居然保持平衡，维持不变了。用技术术语来说就是多轮迭代后产生了收敛，用俗话来讲，就是玩下去甲和丙是不亏的，乙不服输再继续赌下去，也不会有扳本的机会的。

我们再把输赢关系稍微改一下，丙的钱输给甲和乙：

double x2_income=x1/2.0+x3/2.0;
double x3_income=x1/2.0+x2;
double x1_income=x3/2.0;

运行10000轮后，发现又收敛了：

x1:0.6666666666666667, x2:1.0, x3:1.3333333333333333

不过这次就变成了“甲是输的，乙保本，丙是赢的”，我们发现收敛的结果可用于排名，如果给他们做一个赌王排名的话，很显然：“丙排第一，乙第二，甲第三”。

那么这样的收敛是在所有情况下都会发生吗，什么情况不会收敛呢？

我们回过头观察上面的输赢关系，甲、乙、丙三人互相各有输赢，导致钱没有流走，所以他们三人才一直可以赌下去，如果把输赢关系改一下，让甲只输钱，不赢钱，关系如下：

double x2_income=x1/2.0+x3/2.0;
double x3_income=x1/2.0+x2;
double x1_income=0;

那么运行下来会是什么结果呢？如图2-39所示。

2.5.14　从赌钱游戏看PageRank算法 - 图3

图2-39　不收敛情况

我们发现很多轮后，全部为0了。我们分析一下过程，第一轮后，甲的钱就输光了，没有赢得一分钱。但是乙和丙各有输赢，他们一直赌到2000多轮时，乙的钱全部输光了，甲乙都没钱投进来赌了，导致丙再也赢不到钱了，最后所有人结果都变为0了。

2.5.14　从赌钱游戏看PageRank算法 - 图4 提示

这里，我们再分析一下输赢关系，甲的钱全部输给丙和乙后，丙跟乙赌，赢的多输的少，于是所有的钱慢慢都被丙赢走了，导致最后无法维持一个平衡的输赢结果。因此，如果我们要维持平衡和收敛，必须保证赢了钱的人不准走，必须又输给别人才行，让钱一直在三人圈里转而不流失。换句话说，如果存在某人只赢不输，那么这个游戏就玩不下去。

赌钱游戏讲完了，我们再看看PageRank算法的公式：

2.5.14　从赌钱游戏看PageRank算法 - 图5

上面的L(B)代表页面B指向其他页面的连接数，我们举个例子：

假设有A、B、C三张网页，它们的链接关系如下：

❏　A包含B和C的链接

❏　B包含C的链接

❏　C包含A的链接

根据上面的公式，得到各网页PR值如下：

PR(B)=PR(A)/2;
PR(B)=PR(A)/2+PR(C);
PR(A)=PR(C);

可以回过头对照一下，把A、B、C改成甲、乙、丙就是上面举的赌钱游戏例子。

那么q是干吗的？公式里的q叫做逃脱因子，名字很抽象，目的就是用于解决上面赌钱游戏中“只输不赢”不收敛的问题，1-q会保证其中一个PR值为0时计算下来不会全部为0，那么加了这么一个(…)*q+1-q的关系后，整体的PR值会变化吗？

当每个页面的初始PR值为1时，0<=q<=1(计算时通常取值0.8），我们把所有页面的PR值相加看看，假设有n张网页：

PR（x1）+PR（x2）+…+PR（xn）

=（（PR（x2）/L（x2）+…）q+1-q）+…+（（PR（x1）/L（x1）+…）q+1-q）

=（PR（x1）L（x1）/L（x1）+PR（x2）L（x2）/L（x2）+…+PR（xn）*L（xn)/

L（xn））q+n（1-q）

=（PR（x1）+PR（x2）+…+PR（xn））q+n-nq

=nq+n–nq

由于初始PR值为1，所以最后所有页面的PR值相加结果还是为n，保持不变，但是加上(…)*q+1-q的关系后，就避免了PR值为0可以寻求收敛进行排序。

当然实际应用中，这个公式还可以设计得更复杂，我们这里只是为了理解原理，并不是为了做搜索算法，所以就不再深入下去了。

2.5.14　从赌钱游戏看PageRank算法 - 图6 提示

世界的很多东西都是上面这样的游戏，就像炒股，股民赚的钱也就是机构亏的钱，机构赚的钱也就是股民亏的钱，也许股民们应该研究一下PageRank算法，看看股票起起落落的背后是不是收敛了，收敛了说明炒下去永远别想解套，而且机构永远不会亏。

如何使用并行计算方式求PR值？从前面的并行计算例子中，我们可以通过Fourinone提供的各种并行计算模式去设计，思路方法可以有很多种。

思路一：可以采取工人互相合并的机制（工人互相合并及receive使用可参见sayhello demo），每个工人分析当前网页链接，对每个链接进行一次PR值投票，通过receive直接投票到该链接对于网页所在的工人机器上，这样经过一轮工人的互相投票，然后再统计一下本机器各网页所得的投票数，这样就得到新的PR值。但是这种方式，对于每个链接投票都要调用一次receive到其他工人机器，比较耗用带宽，网页数量庞大链接众多时要调用很多次receive，导致性能不高。

思路二：由于求PR值的特点是输入数据大，输出数据小，也就是网页成千上万占空间多，但是算出来的PR值占空间小，我们姑且用内存可以装下。因此我们优先考虑每个工人统计各自机器上的网页，计算各链接对应网页所得投票，然后返回工头统一合并得到各网页的PR值。可以采用最基本的“总—分—总”并行计算模式实现（请参考分布式计算上手demo）。

并行计算的拆分和合并设计如图2-40所示。

2.5.14　从赌钱游戏看PageRank算法 - 图7

图2-40　并行计算方式求PR值

可以看到如下结论：

❏　工人负责统计各自机器上网页的各个链接的PR值。

❏　工头负责合并累加得到各链接对应网页的新PR值，并迭代计算。

程序实现方法如下：

❏　PageRankWorker：是一个PageRank工人实现，为了方便演示，它通过一个字符串数组代表包括的链接（实际上应该从本地网页文件里获取）：

links = new String[]{"B","C"};

然后对链接集合中的每个链接进行PR投票：

for(String p:links)
           outhouse.setObj(p, pr/links.length);

❏　PageRankCtor：是一个PageRank包工头实现，它将A、B、C三个网页的PageRank初始值设置为1.00，然后通过doTaskBatch进行阶段计算，doTaskBatch提供一个栅栏机制，等待每个工人计算完成才返回，工头将各工人返回的链接投票结果合并累加：

pagepr = pagepr+(Double)prwh.getObj(page);

得到各网页新的PR值（这里取q值为1进行计算），然后连续迭代500轮计算。

运行步骤如下：

1）启动ParkServerDemo（它的IP端口已经在配置文件指定，如图2-41所示）：

java -cp fourinone.jar; ParkServerDemo

2.5.14　从赌钱游戏看PageRank算法 - 图8

图2-41　ParkServerDemo

2）运行A、B、C三个PageRankWorker，传入不同的IP和端口号，如图2-42所示：

java  -cp fourinone.jar; PageRankWorker localhost 2008 A
java  -cp fourinone.jar; PageRankWorker localhost 2009 B
java  -cp fourinone.jar; PageRankWorker localhost 2010 C

2.5.14　从赌钱游戏看PageRank算法 - 图9

图2-42　PageRankWorker

3）运行PageRankCtor，结果如图2-43所示：

java -cp fourinone.jar; PageRankCtor

2.5.14　从赌钱游戏看PageRank算法 - 图10

图2-43　PageRankCtor

我们可以看到跟开始的单机程序结果是一样的，同时各工人窗口依次输出了各自的PR值，如图2-44所示。

2.5.14　从赌钱游戏看PageRank算法 - 图11

图2-44　工人运行结果

完整demo源码如下：

// ParkServerDemo
import com.fourinone.BeanContext;
public class ParkServerDemo
{
        public static void main(String[] args)
        {
           BeanContext.startPark();
        }
}
 
// PageRankWorker
import com.fourinone.MigrantWorker;
import com.fourinone.WareHouse;
import com.fourinone.Workman;
 
public class PageRankWorker extends MigrantWorker
{
        public String page = null;
        public String[] links = null;
 
        public PageRankWorker(String page, String[] links){
           this.page = page;
           this.links = links;
        }
 
        public WareHouse doTask(WareHouse inhouse)
        {
           Double pr = (Double)inhouse.getObj(page);
           System.out.println(pr);
 
           WareHouse outhouse = new WareHouse();
           for(String p:links)
               outhouse.setObj(p, pr/links.length);//对包括的链接PR投票
 
           return outhouse;
        }
 
        public static void main(String[] args)
        {
           String[] links = null;
           if(args[2].equals("A"))
               links = new String[]{"B","C"};//A页面包括的链接
           else if(args[2].equals("B"))
               links = new String[]{"C"};
           else if(args[2].equals("C"))
               links = new String[]{"A"};
 
           PageRankWorker mw = new PageRankWorker(args[2],links);
           mw.waitWorking(args[0],Integer.parseInt(args[1]),"pagerankworker");
        }
}
 
// PageRankCtor
import com.fourinone.Contractor;
import com.fourinone.WareHouse;
import com.fourinone.WorkerLocal;
import java.util.Iterator;
 
public class PageRankCtor extends Contractor
{
        public WareHouse giveTask(WareHouse inhouse)
        {
           WorkerLocal[] wks = getWaitingWorkers("pagerankworker");
           System.out.println("wks.length:"+wks.length);
 
           for(int i=0;i<500;i++){//500轮
               WareHouse[] hmarr = doTaskBatch(wks, inhouse);
               WareHouse prwh = new WareHouse();
               for(WareHouse result:hmarr){
                   for(Iterator 
                        iter=result.keySet().iterator();iter.hasNext();){
                        String page = (String)iter.next();
                        Double pagepr = (Double)result.getObj(page);
                        if(prwh.containsKey(page))
                            pagepr = pagepr+(Double)prwh.getObj(page);
                        prwh.setObj(page,pagepr);
                   }
               }
               inhouse = prwh;//迭代
               System.out.println("No."+i+":"+inhouse);
           }
           return inhouse;
        }
 
        public static void main(String[] args)
        {
           PageRankCtor a = new PageRankCtor();
           WareHouse inhouse = new WareHouse();
           inhouse.setObj("A",1.00d);//A的pr初始值
           inhouse.setObj("B",1.00d);//B的pr初始值
           inhouse.setObj("C",1.00d);//C的pr初始值
           a.giveTask(inhouse);
           a.exit();
        }
}

2.5.14 从赌钱游戏看PageRank算法