PageRank算法
PageRank算法原理
PageRank的计算充分利用了两个假设：数量假设和质量假设。步骤如下：
1）在初始阶段：网页通过链接关系构建起Web图，每个页面设置相同的PageRank值，通过若干轮的计算，会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。
2）在一轮中更新页面PageRank得分的计算方法：在一轮更新页面PageRank得分的计算中，每个页面将其当前的PageRank值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。
(常言道，看一个人怎样，看他有什么朋友就知道了。也就是说，一个人有着越多牛X朋友的人，他是牛X的概率就越大。将这个知识迁移到网页上就是“被越多优质的网页所指的网页，它是优质的概率就越大”。
PageRank的核心思想就是上述简单却有效的观点。)
PageRank算法优缺点
优点：
是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。
缺点：
人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低
旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接，除非它是某个站点的子站点。
该算法在初期的时候一直都是基于链接分析的,而一个网页上的链接包含很多:比如广告链接、功能链接、导航链接、以及多次重复的无效链接等等,这些链接都会被该算法计算在pr值传递之中,所以不能够对网页降噪之后在进行处理
基本思想：
如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/ L(T)
其中PR（T）为T的PageRank值，L(T)为T的出链数
则A的PageRank值为一系列类似于T的页面重要性得分值的累加。
即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面（链入页面）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。
3.3 PageRank简单计算：
假设一个由只有4个页面组成的集合：A，B，C和D。如果所有页面都链向A，那么A的PR（PageRank）值将是B，C及D的和。
继续假设B也有链接到C，并且D也有链接到包括A的3个页面。一个页面不能投票2次。所以B给每个页面半票。以同样的逻辑，D投出的票只有三分之一算到了A的PageRank上。
换句话说，根据链出总数平分一个页面的PR值。
如图1 所示的例子来说明PageRank的具体计算过程。
修正PageRank计算公式：
由于存在一些出链为0，也就是那些不链接任何其他网页的网， 也称为孤立网页，使得很多网页能被访问到。因此需要对 PageRank公式进行修正，即在简单公式的基础上增加了阻尼系数（dampingfactor）q， q一般取值q=0.85。
其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率。 1- q= 0.15就是用户停止点击，随机跳到新URL的概率）的算法被用到了所有页面上，估算页面可能被上网者放入书签的概率。
最后，即所有这些被换算为一个百分比再乘上一个系数q。由于下面的算法，没有页面的PageRank会是0。所以，Google通过数学系统给了每个页面一个最小值。
所以一个页面的PageRank是由其他页面的PageRank计算得到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值（非0），那么经过不断的重复计算，这些页面的PR值会趋向于正常和稳定。这就是搜索引擎使用它的原因。
(一个很显然的结论是，如果连通图中有一个顶点的入度为0，则经过有限次迭代之后，该连通图内的所有顶点的PageRank均为0，形象的说，这个顶点就像一个黑洞一样，把整体的PageRank值慢慢地“吸收”了。由于它不对外贡献任何PR值，所以整体的PR总和是在不断地减少，直到最终收敛到0。我把它称之为：PageRank的“黑洞效应”。至于说Google是如何防止这种情况的发生，毕竟一个网站没有外链是完全有可能的，我也尚未找到确切的答案。不过网上道是有人给出了一种解决办法：即如果一个网站没有外链，那么就假定该连通图内其余所有的网点都是它的外链，这样我们就避免了整体PageRank值被吸收的现象)
PageRank幂法计算(线性代数应用)
完整公式：
链入页面的数量，
链出页面的数量，而N是所有页面的数量。
PageRank值是一个特殊矩阵中的特征向量。这个特征向量为：
R是如下等式的一个解：
如果网页i有指向网页j的一个链接，则
4.2 使用幂法求PageRank
PageRank 公式可以转换为求解
其中矩阵为 A = q*P + (1-q) * e
幂法计算过程如下：
X 设任意一个初始向量, 即设置初始每个网页的 PageRank值均。一般为1.
R = AX;
while (1 )(
if ( l X - R I <ε ) { //如果最后两次的结果近似或者相同，返回R
returnR;
} else {
X =R;
R = AX;
}
}
求解步骤：
一、 P概率转移矩阵的计算过程:
先建立一个网页间的链接关系的模型,即我们需要合适的数据结构表示页面间的连接关系。
1) 首先我们使用图的形式来表述网页之间关系：
现在假设只有四张网页集合：A、B、C，其抽象结构如下图1：
图1 网页间的链接关系
显然这个图是强连通的（从任一节点出发都可以到达另外任何一个节点）。
2）我们用矩阵表示连通图：
用邻接矩阵 P表示这个图中顶点关系 ，如果顶（页面）i向顶点（页面）j有链接情况，则Pij = 1，否则Pij = 0。如图2所示。如果网页文件总数为N ，那么这个网页链接矩阵就是一个N*N 的矩阵 。
3）网页链接概率矩阵
然后将每一行除以该行非零数字之和，即（每行非0数之和就是链接网个数）则得到新矩阵P’，如图3所示。 这个矩阵记录了 每个网页跳转到其他网页的概率，即其中i行j列的值表示用户从页面i 转到页面j的概率。图1 中A页面链向B、C，所以一个用户从A跳转到B、C的概率各为1/2。
4）概率转移矩阵P
采用P’ 的转置矩 阵进行计算， 也就是上面提到的概率转移矩阵P 。 如图4所示：
二、 A矩阵计算过程。
1）P概率转移矩阵 :
2）e
3）A矩阵为：q × P + ( 1 一 q) * e
初始每个网页的 PageRank值均为1 ，即X~t = ( 1 ， 1 ， 1 ) 。
三、 循环迭代计算PageRank的过程
第一步：
因为X 与R的差别较大。 继续迭代。
第二步：
继续迭代这个过程...
直到最后两次的结果近似或者相同，即R最终收敛，R 约等于X，此时计算停止。最终的R 就是各个页面的 PageRank 值。
用幂法计算PageRank 值总是收敛的，即计算的次数是有限的。
不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到他们的真实值。
由于互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页，那么这个矩阵就有一百亿亿个元素。这样大的矩阵相乘，计算量是非常大的。Larry Page和Sergey Brin两人利用稀疏矩阵计算的技巧，大大的简化了计算量。
转载于:https://blog.51cto.com/9492221/1564068