MapReduce 基础算法【PageRank网页排名算法】

目录

PageRank网页排名算法

PangeRank算法是Google公司创始人之一Larry Page发明的，它是一个用来衡量评估网页重要性或者等级的算法。Google公司据此标识网页的PR值，最直观的条件就是有很多网页链接到它，尤其是要有很高Rank值的网页链接到该网页。

基本思想

如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋给A，这个重要性得分值为:PR(T)/L(T)$PR(T)/L(T)$.其中PR(T)$PR(T)$为T$T$的PangeRank值，L(T)$L(T)$为T$T$的输出链数。则A的PangeRank值为一系列类似于T$T$的页面重要性得分值的累加。

即一个页面的得票数由所有链向它的重要性来决定的，到一个页面的超链接相当于对该页面投一票。一个页面的PangeRank是由所有链向它的页面的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果第一个页面没有任何链入页面，那么它没有等级。

简单计算

假设一个由只有4个页面组成的集合：A,B,C和D$A,B,C和D$。如果所有页面都链向A$A$，那么A的PR值将是B，C,D$B，C,D$的和。

继续假设B$B$也有链接到C$C$，并且D$D$也有链接到包括A$A$的3个页面。一个页面不能投票2次。所以B$B$给每个页面半票。同样，D$D$投出的票只有三分之一算到了A的PangeRank上。

换句话说，根据链出的总数平分一个页面的PR值。

PageRank 的简化模型

互联网上的各个网页之间的连接关系我们都可以看成一个有向图，对于任意的网页，它的PR值可以表示为：

其中，Bu$B_u$是所有链接到网页u$u$的网页集合，网页v$v$是属于集合Bu$B_u$的网页，L(v)$L(v)$则是网页v$v$的对外链接数（即出度）。

简化模型的问题

排名泄露

如上图所示，如果存在网页没有出度链接，如A点，则会产生排名泄露问题，经过多次迭代之后，所有网页的PR值会趋向于0。其中，有向图可以得出如下的初始的转移矩阵：

在这个矩阵中，第一列表示用户网页A跳转到其他页面的概率。即用户分别有B、C、D、都没向A跳转。

注意： 这里所有点的初始PR值都是假设为0.25.

如下表所示(各个点的迭代计算)：

\	PR(A)	PR(B)	PR(C)	PR(D)
初始值	0.25	0.25	0.25	0.25
一次迭代	0.125	0.125	0.25	0.25
二次迭代	0.125	0.125	0.125	0.25
三次迭代	0.125	0.125	0.125	0.125
...$...$	...$...$	...$...$	...$...$	...$...$
n次迭代	0	0	0	0

排名下沉

若有网页没有入度链接，如节点A，其所产生的贡献会被由B、C、D构成的强连通分量“吞噬”掉，就会产生排名下沉，节点A的PR值会在迭代后趋向于0。

\	PR(A)	PR(B)	PR(C)	PR(D)
初始值	0.25	0.25	0.25	0.25
一次迭代	0	0.375	0.25	0.375
二次迭代	0	0.375	0.375	0.25
三次迭代	0	0.25	0.375	0.375
四次迭代	0	0.375	0.25	0.375
...$...$	0	...$...$	...$...$	...$...$
n次迭代	0	...$...$	...$...$	...$...$

PageRank的随机浏览模型

由于存在一些出链为0，也就是那些不连接任何其他网页的网，也称孤立网，使得很多网页能被访问到。因此，对PageRank公式进行修正，即在简单模型的基础上增加了阻尼系数q,q 一般取值q=0.85.$q=\mathrm{0.85.}$其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率。1−q=0.15$1-q=0.15$就是用户停止点击，随机跳到新的URL的概率的算法被用到了所有页面上，估算页面可能被上网者放入书签的概率。

公式如下:

所以一个页面的PageRank是由其他页面的PageRank计算得到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值，那么经过不断的重复计算，这些页面的PR值会趋向于正常和稳定。

PageRank幂法计算

完整公式

p1,p2,p3....,pn$p_1,p_2,p_3....,p_n$是被研究的页面，M(pi)$M(p_i)$是pi$p_i$链入页面的数量，L(pj)$L(p_j)$是pj$p_j$链出页面的数量，而N是所有页面的数量。
PageRank值是一个特殊矩阵中的特征向量，这个特征向量为：
R的一个解是：

如果网页i$i$有指向网页j$j$的一个链接，则∑Ni=1φ(pi,pj)=1$\sum _{i=1}^N\phi (p_i,p_j)=1$,否则φ(pi,pj)=0$\phi (p_i,p_j)=0$.

求解步骤

P概率转移矩阵的计算过程：

p 概率转移矩阵：

P=⎡⎣⎢001100110⎤⎦⎥(网页链接矩阵)，P′=⎡⎣⎢00112001210⎤⎦⎥(网页链接概率矩阵)，P′T=⎡⎣⎢⎢01212001100⎤⎦⎥⎥（P′的转置矩阵）$$P=\left[\begin{array}{ccc}0& 1& 1\\ 0& 0& 1\\ 1& 0& 0\end{array}\right](网页链接矩阵)，P^{\prime }=\left[\begin{array}{ccc}0& \frac{1}{2}& \frac{1}{2}\\ 0& 0& 1\\ 1& 0& 0\end{array}\right](网页链接概率矩阵)，P^{\prime T}=\left[\begin{array}{ccc}0& 0& 1\\ \frac{1}{2}& 0& 0\\ \frac{1}{2}& 1& 0\end{array}\right]（P^{\prime }的转置矩阵）$$

A矩阵的计算过程：

PageRank公式可以转换为limx→∞AnX$\underset{x\to \mathrm{\infty }}{lim}{A}^{n}X$的值。
其余矩阵为A=q×P+(1−q)∗eet/N$A=q\times P+(1-q)\ast e{e}^t/N$,P为概率转移矩阵，et$e^t$为n维的全1行（即单位矩阵）。

P概率转移矩阵

P=⎡⎣⎢⎢01212001100⎤⎦⎥⎥$$P=\left[\begin{array}{ccc}0& 0& 1\\ \frac{1}{2}& 0& 0\\ \frac{1}{2}& 1& 0\end{array}\right]$$

ee^t/N为

eet/N=⎡⎣⎢⎢131313131313131313⎤⎦⎥⎥$$e{e}^t/N=\left[\begin{array}{ccc}\frac{1}{3}& \frac{1}{3}& \frac{1}{3}\\ \frac{1}{3}& \frac{1}{3}& \frac{1}{3}\\ \frac{1}{3}& \frac{1}{3}& \frac{1}{3}\end{array}\right]$$

A矩阵为：q×P+(1−q)∗eet/N=0.85×P+0.15∗eet/N$q\times P+(1-q)\ast e{e}^t/N=0.85\times P+0.15\ast e{e}^t/N$

A=⎡⎣⎢0.050.450.450.050.050.90.90.050.05⎤⎦⎥$$A=\left[\begin{array}{ccc}0.05& 0.05& 0.9\\ 0.45& 0.05& 0.05\\ 0.45& 0.9& 0.05\end{array}\right]$$

初始的每个网页的PageRank值均为1，即：

x∼=(1,1,1)$x\sim =(1,1,1)$.

循环迭代计算PageRank的过程

第一步：

AX=⎡⎣⎢0.050.450.450.050.050.90.90.050.05⎤⎦⎥∗⎡⎣⎢111⎤⎦⎥=⎡⎣⎢0.05+0.05+0.90.45+0.05+0.050.45+0.9+0.05⎤⎦⎥=⎡⎣⎢10.551.4⎤⎦⎥=R$$AX=\left[\begin{array}{ccc}0.05& 0.05& 0.9\\ 0.45& 0.05& 0.05\\ 0.45& 0.9& 0.05\end{array}\right]\ast \left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]=\left[\begin{array}{c}0.05+0.05+0.9\\ 0.45+0.05+0.05\\ 0.45+0.9+0.05\end{array}\right]=\left[\begin{array}{c}1\\ 0.55\\ 1.4\end{array}\right]=R$$

因为X与R的差别较大，继续迭代。

第二步：

AX=⎡⎣⎢0.050.450.450.050.050.90.90.050.05⎤⎦⎥∗⎡⎣⎢10.551.4⎤⎦⎥=⎡⎣⎢1.3370.4551.109⎤⎦⎥=R$$AX=\left[\begin{array}{ccc}0.05& 0.05& 0.9\\ 0.45& 0.05& 0.05\\ 0.45& 0.9& 0.05\end{array}\right]\ast \left[\begin{array}{c}1\\ 0.55\\ 1.4\end{array}\right]=\left[\begin{array}{c}1.337\\ 0.455\\ 1.109\end{array}\right]=R$$

继续迭代这个过程，直到最后两次结果近似或者相同，即R最终收敛。最终的R就是各个页面的PageRank值。用幂法计算PageRank值总是收敛的，即计算过程是有限的。
由于互联网上的网页的数量是巨大的，这样，矩阵的元素会较多，矩阵相乘是非常的大，稀疏矩阵 简化了计算量。

PageRank优缺点

优点：

是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。

缺点：

• 人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低

• 旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接，除非它是某个站点的子站点。

参考文献

1、维基百科
2、《深入理解大数据大数据处理与编程实践》
3、《这就是搜索引擎:核心技术详解》