Web上超链接结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大的提高检索结果的质量。Sergey Brin(谢尔盖·布林 )和Lawrence Page(拉里·佩奇)在1998年提出了PageRank算法，PageRank(TM) 是美国 Google 公司的登记注册商标。
Google 查询的全过程通常不超过半秒时间，但在这短短的时间内需要完成多个步骤，然后才能将搜索结果交付给搜索信息的用户。
创始人：拉里佩奇(Larry Page ) —Google创始人之一
应 用：是Google用来衡量一个网站的好坏的唯一标准。
PageRank的提出
Google的创始人之一Larry Page于1998年提出了PageRank，并应用在Google搜索引擎的检索结果排序上，该技术也是Google早期的核心技术之一
Larry Page是Google的创始首席执行官，2001年4月转任现职产品总裁。他目前仍与Eric Schmidt和Sergey Brin一起共同负责 Google的日常运作。他在斯坦福大学攻读计算机科学博士学位期间，遇到了Sergey Brin，他们于1998年合伙创立Google。
Google的网页排序
在Google中搜索“体育新闻”
那么为什么是这样排序的呢，是按照什么规律排出来的呢？在Google中搜索“体育新闻”
搜索引擎工作的简要过程是针对查询词“体育新闻”进行分词——》“体育”、“新闻”
根据建立的倒排索引，将同时包含“体育”和“新闻”的文档返回，并根据相关性进行排序
这里的相关性主要是基于内容的相关性但是会有一些垃圾网页，虽然也包含大量的查询词，但却并非满足用户需要的文档，如下图，一个网页中虽然出现了四次“体育新闻”但却不是用户所需要的因此，页面本身的重要性在网页排序中也起着很重要的作用。
在Google中搜索“体育新闻”
如何度量网页本身的重要性呢？
互联网上的每一篇html文档除了包含文本、图片、视频等信息外，还包含了大量的链接关系，利用这些链接关系，能够发现某些重要的网页
直观地看，某网页A链向网页B，则可以认为网页A觉得网页B有链接价值，是比较重要的网页。某网页被指向的次数越多，则它的重要性越高；越是重要的网页，所链接的网页的重要性也越高。
比如，新华网体育在其首页中对新浪体育做了链接，人民网体育同样在其首页中对新浪体育做了链接
可见，新浪体育被链接的次数较多；同时，人民网体育和新华网体育也都是比较“重要”的网页，因此新浪体育也应该是比较“重要”的网页。
链向网页E的链接远远多于链向网页C的链接，但是网页C的重要性却大于网页E。这是因为网页C被网页B所链接，而网页B有很高的重要性。
PageRank是一种在搜索引擎中根据网页之间相互的链接关系计算网页排名的技术。
PageRank是Google用来标识网页的等级或重要性的一种方法。其级别从1到10级，PR值越高说明该网页越受欢迎（越重要）。
PageRank近似于一个用户，是指在Internet上随机地单击链接将会到达特定网页的可能性。通常，能够从更多地方到达的网页更为重要，因此具有更高的PageRank。
2.1.1概率转移矩阵
2.1.2 转置矩阵
2.1.3 矩阵乘法与矩阵数乘
假设A=x,B=y,C=z,D=w 可以推导出如下方程式,如下是一个一元多次方程组，那么即便我们得到了如下所示的多元一次方程组，那么又怎么对如下所示的多元一次方程组进行求解呢？
x =1/2y+z
y =1/3x+1/2w
z =1/3x+1/2w
w=1/3x+1/2y
如下所示我们可以把x,y,z,w转变成一个列向量与一个矩阵的乘积，那么如何才能得到结果呢，我们人类是解不出来了，但是我们可以看到变换后的公式就式一个A=B*A的式子，这个计算机可以求解啊，多次迭代不就可以求出结果来了吗。
那么这个矩阵式如何经过投票矩阵得到的呢，实际上他就是投票矩阵做一个概率转移以后，再求一次矩阵的转置就可以得到了。那么既然是一个递归求解的过程，我们不防设x+y+z+w=1。也就是说假设刚开始他们的重要性都是相等的1/n。那么我们通过计算机来计算一个结果
大家会发现，经过不断的迭代，会趋于一个恒定值，这样我们就把网页的排名求出来了。就可以知道哪个网页相对来说比较重要了。
2.2.1 简化模型面临的缺陷
实际的网络超链接环境没有这么理想化，比如一个网页没有连接指向它，或者它没有连接指向其他网页，再或者这个网页直接连接指向了自己。PageRank会面临三个问题：
- Rank leak（排名泄漏）
- Rank sink (排名下沉)
- Rank trap (排名陷阱)
2.2.2 Rank Leak(排名泄漏)
Rank leak：一个独立的网页如果没有出的链接就产生等级泄漏
如上图所示我们按简化模型的计算方式求得的结果，令人唏嘘，每一个网页看起来似乎都没那么重要了。更本没有得出排名的结果。
2.2.3 Rank sink (排名下沉)
Rank sink：整个网页图中的一组紧密链接成环的网页如果没有入的链接就产生Rank sink
如上结果所示造成了个别网页更本就没参与进来排名
2.2.4 Rank trap (排名陷阱)
Rank Trap：整个网页中，存在这么个网页，他链接到了他自己死循环
如上排名结果所示，也是如此会造成某个网页占满所有的排名值，那么是什么出问题了呢。
上面过程，我们忽略了一个问题，我们的上网者是聪明而悠闲，他悠闲，漫无目的，总是随机的选择网页，他聪明，在走到一个终结网页或者一个陷阱网页（比如两个示例中的C），不会傻傻的干着急，他会在浏览器的地址随机输入一个地址，当然这个地址可能又是原来的网页，但这里给了他一个逃离的机会，让他离开这万丈深渊。模拟聪明而又悠闲的上网者，对算法进行改进，每一步，上网者可能都不想看当前网页了，不看当前网页也就不会点击上面的连接，而上悄悄地在地址栏输入另外一个地址，而在地址栏输入而跳转到各个网页的概率是1/n。假设上网者每一步查看当前网页的概率为a，那么他从浏览器地址栏跳转的概率为(1-a)
如上图所示我们把整个图补充完整，用虚线表示的就是用户随机浏览在浏览器中输入的网址，的权重，然而它输入每个网址的概率度是1/n，所以呢我们就可以改写为下面的矩阵运算，这就是著名的google矩阵
接下来我们把前面有问题的模型进行代入，
奇迹般的发现问题确实被解决了 所有节点都有排名了.至此pagerank的整个算法已经讲完了。
上面的演算过程，采用矩阵相乘，不断迭代，直到迭代前后概率分布向量的值变化不大，一般迭代到30次以上就收敛了。真的的web结构的转移矩阵非常大，目前的网页数量已经超过100亿，转移矩阵是100亿*100亿的矩阵，直接按矩阵乘法的计算方法不可行，需要借助Map-Reduce的计算方式来解决。实际上，google发明Map-Reduce最初就是为了分布式计算大规模网页的pagerank，Map-Reduce的pagerank有很多实现方式。
2.4.1 爬虫获取到数据
1 A -> B C D
2 B -> A D
3 C -> C
4 D -> B C
A有三条出链，分别指向B、C、D，实际上，我们爬取的网页结构数据就是这样的。
1、Map阶段
Map操作的每一行，对所有出链发射当前网页概率值的1/k，k是当前网页的出链数，所以就是<1/k,1/n> 其中1/n代表初始的pagerank值,比如对第一行输出<B，1/3*1/4>,<C，1/3*1/4>,<D，1/3*1/4>;
2、Reduce阶段
Reduce操作收集网页id相同的值，累加并按权重计算，pj=a*(p1+p2+...Pm)+(1-a)*1/n，其中m是指向网页j的网页j数，n所有网页数。
思路就是这么简单，但是实践的时候，怎样在Map阶段知道当前行网页的概率值，需要一个单独的文件专门保存上一轮的概率分布值，先进行一次排序，让出链行与概率值按网页id出现在同一Mapper里面，整个流程如下：
分主题计算网页的PageRank向量：在计算网页在特定类别的PageRank分值时，在每个类别中网页划分为两个集合，一个集合是ODP对应分类主题下所包括的所有网页，即人工精选的高质量网页，可以称之为集合S，剩下的网页放入另外一个集合内，可称之为集合T。在计算PageRank时，由于集合S内的网页能够很好地表征分类主题，所以赋予较大的跳转概率值。通过这种设定，集合S内的网页根据链接关系向集合T中网页传递权值，因为直接有链接指向的往往主题类似，这样就将与该分类主题内容相似的网页赋予较高的PageRank值，而无关的网页则赋予较低权重的PageRank分值。
而s是这样一个向量：对于某 topic 的s，如果网页k在此 topic 中，则s中第k个元素为1，否则为0。注意对于每一个 topic 都有一个不同的s。而|s |表示s中 1 的数量。假设有页面A，B，C, D，假设页面A归为 Arts，B归为 Computers，C归为 Computers，D归为 Sports。那么对于 Computers 这个 topic，s就是：
假设我们设置阻尼系数q=0.8， 而|s|=2, 因此，迭代公式为
最后算出的向量就是 Computers 这个 topic 的 rank。如果实际计算一下，会发现B、C页在这个 topic 下的权重相比上面非 Topic-Sensitive 的 rank 会升高，这说明如果用户是一个倾向于 Computers topic 的人（例如程序员），那么在给他呈现的结果中B、C会更重要，因此可能排名更靠前。
在进行上述用户查询分类计算的同时，搜索系统读取索引，找出包含了用户查询“乔丹”的所有网页，并获得已计算好的各个分类主题的PageRank值，在图6-21的例子里，假设某个网页A的各个主题PageRank值分别为体育0.2，娱乐0.3以及商业0.1。
得到用户查询的类别向量和某个网页的主题PageRank向量后，即可计算这个网页和查询的相似度。通过计算两个向量的乘积就可以得出两者之间的相关性。在图6-21的例子里，网页A和用户查询“乔丹”的相似度为：
Sim(“乔丹”,A)= 0.6*0.2+0.1*0.3+0.3*0.1=0.18
对包含“乔丹”这个关键词的网页，都根据以上方法计算，得出其与用户查询的相似度后，就可以按照相似度由高到低排序输出，作为本次搜索的搜索结果返回给用户。
如上图所示，假设有四个网页节点，通过他们主题相关性，分别得到主题相关的列向量，在这个时候我们把主题相关性矩阵代入公式
如上图所示，就可以分别针对不同的主题计算得到，在各个主题下，那个网页节点的pagerank的值，那么假设这个时候
我们在浏览器搜索框中输入“商业街”。那么假设这个词在artist出现的概率为0.1 在sports 下面出现的概率为0.3，在business这个topic
下面出现的概率为0.6那么我们可以来计算一下这几个网页的相似度
如上所示我们计算得到了一个相似度的值。我们发现越接近的两个值代表的网页越式相似，所以我们可以得到结论，在