Pagerank介绍
背景介绍
PageRank 算法由 Google 创始人 Larry Page 在斯坦福读大学时提出，又称 PR——佩奇排名。主要针对网页进行排名，计算网站的重要性，优化搜索引擎的搜索结果。PR 值是表示其重要性的因子
中心思想
实现网站排名的重点及难点就在于对网站重要性的衡量。一旦确认了网站的重要性，那么搜索引擎就可以根据网站的重要性对搜索结果的网站进行排名。
PR算法核心就在于：一、量化重要性；二、实际应用简化为理论模型
一、量化重要性
为了理解佩奇算法的核心思想——如何衡量一个网页的重要性，我们需要提前理解下面的一个观点（划重点）：
1、每个网页本身无重要性，网页重要性靠其他网页提供
2、所有指向该网页的其他网页，反映该网页的重要性（避开对网页内容的衡量）
三大指标
拉里佩奇老师在巧妙避开对网页内容衡量来确认重要性的陷阱后，提出了三个具体思考角度来衡量一个网页的重要性
1、下图网页大小与其重要性相挂钩，网页越大代表其越重要
2、不同图的大小重要标准相同，可以结合着看
1、数量指标
当在网页模型图中，一个网页接受到的其他网页指向的入链（in-links）越多，说明该网页越重要。换句话说，越多的网页引用了该网页，那么该网页就越重要（因为它影响力越大）
2、质量指标
当一个质量高的网页指向（out-links）一个网页，说明这个被指的网页重要。例如：一个诺贝尔奖的得主说你的网页好，和一个普通人说你的网页好所提供的影响力是不一样的。 
（图中右边网页，重要性就比左边的网页要高，因为一个重要性高的网页指向它）
3、稀释指标
假如一个质量很高的网页指向你的网页，但是同时也指向了很多其他的网页，那么此时这个网页能够给你的网页提供的重要性增幅也是有限的，重要性会被稀释掉。因为基于随机冲浪者理论，用户在浏览时有很大概率会通过这个高质量网站“冲浪”到其他它所指向的网站，而不是你的网站
（图中右边网页相比于上一张图中最右边网页较小，因为中间网页的重要性被稀释为了三份）
二、实际应用简化为理论模型
有了上面的三大衡量指标后，如何简化生活中的实际问题为数学理论的模型也是相当关键的。数学建模的过程也意味着，我们必须要：1、抽象、提炼问题的本质；2、简化问题的表象
在这里，PageRank算法，将网页以及他们之间的关系抽象为有向图。可以利用有向图的知识来求解
（上图每个节点代表一个网站，连接表示网站间的链接关系）
最终要实现的机器学习算法：给予网站关系有向图，算法能够自我学习这个关系图然后预测网站最终的重要度
PageRank公式
- PR(a)：a节点（a网站）的重要性
- i+1：第i+1次迭代，算法循环次数
- PR(Ti)：指向a节点的其他节点的PR值
- L(Ti)：指向a节点的其他节点的总出链数
1、PR（Ti）就体现了质量指标
2、
就体现了数量指标
3、除L（Ti）就体现了稀释指标
手动预测网站的重要度
具体计算过程（拿一个例子）：
关键点：
1、一开始要给每个节点初始重要值：1/N（N为节点总数）
2、每一轮都是按顺序给所有节点更新重要值，更新是拿前一轮的值
3、直到所有节点重要值不变为止
按照公式定义来计算PR值存在一个问题，就是我们需要一步步自己去迭代实现。拉里佩奇便要思考一个可以实现让计算机自己去一步步计算，最终输出结果的智能算法
马尔可夫矩阵预测网站的重要度
矩阵关键点：
1、列表示出链：例如第一列就表示A出链到ABCD各个点的概率值
2、行表示入链：例如第一行就表示ABCD入链到A的概率值
计算得到：
两个方法的联系
理解关键点：
1、矩阵*向量=矩阵行 *向量 作为结果向量的行
2、联系三个含义：矩阵行的含义，向量的含义，结果向量的含义
PageRank算法存在的问题
PageRank算法主要存在两个问题：一、Dead Ends问题；二、Spider Traps问题。这两个问题都是在特殊情况才会出现，但是一出现便会让我们的佩奇排序算法无法执行
Spider traps问题和Dead ends问题是PageRank算法中两种不同的情况，它们都会影响链接结构的平衡性。具体来说：
- Dead ends问题：指的是某些节点没有任何出边，即它们不会将PageRank值传递给其他页面。这会导致这些页面积累较高的PageRank值，因为它们只接收来自其他页面的值而不向外传递。
- Spider traps问题：是指一些网页故意设计成只有入链而几乎没有或没有出链，有时还包含指向自己的链接，即自环。这种结构会导致PageRank值在这些“陷阱”网页上积累，使得它们获得异常高的排名，从而影响整个网络的链接结构。
一、Dead Ends问题
问题描述
在多次迭代后，所有网站的重要性都转变为0
出现原因及解释
原因：由于网络中某些节点没有指向其他节点的出链，导致链接结构中断
解释：
1、利用佩奇算法确定网站的重要性可以理解为：让一个小虫子在网站间不停且随机地爬，它爬到哪个网站的次数最多，则这个网站的重要性就越高
2、此时假如其中一个网站没有出链，那么当小虫子爬到该网站时便无法离开，此时其他网站就无法被小虫子爬到，因此重要性都会迭代为0。最后由于该网站本身也是依靠其他网站的重要性来确定自身重要性的，所以该网站的重要性也将变为0，即虫子无法运动导致爬虫死亡
图解示例
使用马尔科夫矩阵快速计算PR值：
解决方法：Teleport
既然问题出现的原因是存在一个没有出链的网站，那么我们在PageRank算法执行前对有向图矩阵进行检查。如果存在这种不合要求的有向图矩阵，那么我们便执行下面的操作：
关键点：
1、 引入了“传送”（teleport）机制。当冲浪者遇到一个没有出链的页面时，1/n的概率随机跳转到任意一个页面（假设总共能跳转的页面有n个）
