google的随机冲浪模型

Lawrence Page和Sergey Brin在不同的刊物中发表了2个不同版本的PageRank的算法公式。在第二个版本的算法里，页面A的PageRank值是这样得到的：

PR(A) = (1-d) / N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

他们将PageRank视作一种模型，就是用户不关心网页内容而随机点击链接。 这里的N是整个互联网网页的总数。 页面的PageRank值就是在点击许多链接后到达这个页面页面的实际概率。因此，互联网上所有网页的PageRank值形成一个概率分布，所有RageRank值之和为1。网页的PageRank值决定了随机访问到这个页面的概率。用户点击页面内的链接的概率，完全由页面上链接数量的多少决定的，这也是上面PR(Ti)/C(Ti)的原因。

因此，一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。并且，阻尼系数d减低了这个概率。阻尼系数d的引入，是因为用户不可能无限的点击链接，常常因无聊而随机跳入另一个页面。 阻尼系数d定义为用户不断随机点击链接的概率，所以，它取决于点击的次数，被设定为 0-1之间。d的值越高，继续点击链接的概率就越大。因此，用户停止点击并随机冲浪至另一页面的概率在式子中用常数(1-d)表示。无论入站链接如何，随机冲浪至一个页面的概率总是(1-d)。(1-d)本身也就是页面本身所具有的PageRank值。

如果互联网有100个网页，其中一个页面PageRank值为2;那么，如果他将访问互联网的过程重新开始100次(xdanger注：这句话具体含义是，该用户随机点击网页上的链接进入另一个页面，每点击一次都有一定概率因疲劳或厌倦或其他任何原因停止继续点击，这就是阻尼系数d的含义;每当停止点击后，即算作此次访问结束，然后随机给出一个页面让他开始另一次访问过程;让他将这样的“手续”重复进行100次)，平均就有2次访问到该页面。

假设一个小网站由三个页面A、B、C组成，A连接到B 和C，B连接到C，C连接到A。虽然Page和Brin实际上将阻尼系数d设为0.85，但这里我们为了简便计算就将其设为0.5。尽管阻尼系数d的精确值无疑是影响到PageRank值的，可是它并不影响PageRank计算的原理。因此，我们得到以下计算PageRank值的方程：

PR(A) = 0.5 + 0.5 PR(C)

PR(B) = 0.5 + 0.5 (PR(A) / 2)

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

这些方程很容易求解，以下得到每个页面的PageRank值：

PR(A) = 14/13 = 1.07692308

PR(B) = 10/13 = 0.76923077

PR(C) = 15/13 = 1.15384615

很明显所有页面PageRank之和为3，等于网页的总数。