-

大作业

本作业中的例子有A、B、C、D、E五个网页节点，如果当前在A节点，则条件到B、D、C的概率为1/3，这里的3表示A有3条出链，如果一个节点有k条出链，那么跳转任意一个出链上的概率是1/k，同理B到D、E的概率为1/2，C到E的概率为1，D到E的概率为1，E到A的概率为1。使用转移矩阵来表示节点间跳转的概率，n代表节点的数目，转移矩阵M是一个n*n的方阵，上面节点的转移矩阵如下：

        |0   0    0    0   1|
        |1/3 0    0    0   0|
  S  =  |1/3 0    0    0   0|
        |1/3 1/2  0    0   0|
        |0   1/2  1    1   0|

互联网中一个网页只有对自己的出链，或者几个网页的出链形成一个循环圈。那么在不断地迭代过程中，这一个或几个网页的PR值将只增不减，显然不合理。为了解决这个问题。想象一个随机浏览网页的人，当他到达C网页后，假定他有一个确定的概率会输入网址直接跳转到一个随机的网页，并且跳转到每个网页的概率是一样的。于是下面这个转移矩阵：

 A = αS + （1-α）/n e （取e为所有元素全是1的n*n的方阵）

每个网页的PR值初始值为1/n，在不断迭代趋于平稳的时候，即为最终结果。 PR值的计算如下，其中P(n)为第n次迭代时各网页PR值组成的列向量:

 P(n+1) = AP(n)

然后通过P(n+1) = AP(n)不断地迭代PR值。当满足下面的不等式后迭代结束，获得所有页面的PR值：

 |P(n+1) - P(n)| < ϵ

最终得到PageRank值为：

{'A': 0.16528150209325865, 'B': 0.10024463838963493, 'C': 0.17048927677926984, 'D': 0.25569721941045953, 'E': 0.47746646439245966}