从赌钱游戏看PageRank算法

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

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

下面是PageRank算法的公式：

我们其实可以直接阐述该公式本身，并介绍如何使用并行计算套用上面公式得到各网页的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轮后，看到结果如下：