Page Rank

背景介绍

（参考李思老师线性代数讲义 125 - 130 页: ）

PageRank 是 Google 搜索引擎用来排名网页相关性和重要性的算法. 其核心思想是一个网页的重要性与其链接到的网页的重要性的数量和质量有关. 基本数学原理是通过网页数据得到一个大型的矩阵, 然后通过求解最大特征值的特征向量得到排名数据.

我们将互联网看作一个巨大的有向图, 每个节点代表一个网页, 每条有向边代表一个链接, 边的方向表示链接的方向. PageRank 算法将给每网页 $i$ 匹配一个 PageRank 值 $r_i$ , $r_i$ 的值越大表示其越重要. 其基本思想是这个 PageRank 值是通过网络关系来体现的：如果更多更重要的网页关联到某个网页, 那么这个网页本身也更重要.

具体而言, 引入链接关系矩阵 $M = [m_{ij}]$ :

• 如果网页 $j$ 链接到网页 $i$ , 则

$$ m_{ij}=\frac{1}{L(j)} $$

其中 $L(j)$ 是所有从网页 $j$ 链接出的边数.

• 如果网页 $j$ 没有链接到网页 $i$ , 则

$$ m_{ij}=0 $$

• 特别的, 如果 $L(j)=0$, 则令

$$ m_{jj}=1 $$

PageRank 算法用来计算每个网页 PageRank 权重 $r_i$ 的方法为: 一个网页的 PageRank 值等于所有链接到它的网页的 PageRank 值的加权平均, 权重为链接概率. 具体公式为:

$$ r_i = \sum_j m_{ij} r_j $$

我们把所有网页的 PageRank 权重 $r_i$ 组合为列向量 $\vec{r}$ , 则上述方程可以写成矩阵形式

$$ M \vec{r} = \vec{r} $$

因此寻找网页的 PageRank 值即为求解链接关系矩阵 $M$ 属于特征值 $1$ 的特征向量.

为了保证 $\vec r$ 的唯一性, PageRank 算法引入了一个阻尼因子 $d$ (通常设置为 $0.85$ ). 阻尼因子表示用户有 $d$ 的概率点击链接, $1-d$ 的概率随机跳转到任意一个网页. 改进后的链接关系矩阵为

$$ \widehat{M} = d M + (1-d) S $$

这里的 $S$ 的每个矩阵元都是 $1/n$ ( $n$ 是网页的总个数)

$$ S = \begin{bmatrix} 1/n & 1/n & \cdots & 1/n \\ 1/n & 1/n & \cdots & 1/n \\ \vdots & \vdots & \ddots & \vdots \\ 1/n & 1/n & \cdots & 1/n \end{bmatrix} $$

可以证明, 改进后的链接关系矩阵 $\widehat{M}$ 绝对值最大的特征值为 $1$ , 且其对应的特征子空间是一维的. 同时, 给出如下 PageRank 算法:

(1) 取初始向量

$$ \vec{r}_0 = \begin{bmatrix} 1/n \\ 1/n \\ \vdots \\ 1/n \end{bmatrix} $$

(2) 进行迭代计算

$$ \vec{r}_N = \widehat{M} \vec{r}_{N-1} $$

(3) 当 $N$ 充分大时, 多次迭代得到的向量 $\vec{r}_N$ 即给出了 PageRank 向量 $\vec{r}$ 的近似值.

题目描述

本题要求你按上述要求实现 PageRank 算法, 对于给出的一组网站链接关系, 求出 PageRank 向量 $\vec{r}$ .

输入格式

输入共有 2 + m 行.

第 1 行为两个正整数 m , n , 其中 n 为网站总数.

第 2 行为 PageRank 算法中的阻尼因子 d 值.

接下来的 m 行, 每行给出一条链接关系, 包含两个正整数 a, b , 表示从网站 a 链接到网站 b .

输出格式

输出共有 n 行小数, 表示 PageRank向量 $\vec{r}$ . 与标准答案的相对误差不超过 1e-4 即可.

样例

此样例即为测试点1, 与讲义中案例的连接关系及结果相同.

样例输入

6 4
1.0
1 2
1 3
2 3
3 1
3 4
4 1

样例输出

0.3333333333
0.1666666667
0.3333333333
0.1666666667

数据范围

• 1 <= m <= 1000000

• 1 < n <= 1000000

• 0.0 < d <= 1.0

• 1 <= a,b <= n