参加数学建模的时候要研究一下PageRank，为了巩固3天从入门到精通的成果，把了解到的整理成文。

直观理解

基本思想

PageRank是以Google创始人Larry Page的姓命名的，于1999被提出来，用于测量网页的相对重要性（对网页进行排序），学术论文如下：

Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab. [PDF]

PageRank的设计受到学术论文引用启发（两人的父亲都是大学教授）。衡量一篇学术论文质量高与否，最重要的一个指标是引用次数，高引用量的论文通常意味着高质量。同理，如果一张网页被引用（以超链接的形式）多了，那么这张网页就比较重要。总结起来，PageRank的核心思想有两点（结合图1说明）：

• 越多的网页链接到一个网页（可以理解成投票，D --> B，D给B投了一票），说明这个网页更加重要，如图1的B。(一篇论文被很多论文引用)
• PageRank高的网页链接到一个网页，说明这张网页也很重要。如图1，尽管C只有一张网页B链接到它，但C的重要性高于E，尽管E有一堆小罗罗给它投票。（论文被大牛引用了，说明这篇论文很有价值）（也可以从话语权角度理解，重要的人说话份量重）

Fig. 1: PageRanks for a simple network (image from Wikipedia)

整个万维网（World Wide Web）可以抽象成一张有向图，节点表示网页，连线pi → pj表示网页pi包含了超链接pj（pi指向了pj）。如果能对图中每个节点重要性量化，那么就能对网页进行排序了。PageRank提出之初就是为了对网页进行排序。

搜索引擎的工作原理可以简化为：输入关键词，返回与该关键词相关的网页（一个集合，相当于得到一张子图），在该子图上计算每个节点的PageRank值，PR值高的网页排在前面，低的就排在后面。

如何计算

接下来的问题是，如何计算每个节点的PageRank。想要知道一个网页pi的PR值，需要知道：

• 有多少网页链接到了pi
• 这些网页的PR值是多少 其他网页的PR值又很可能是依赖于p，这就陷入了“先有鸡还是先有蛋”的循环，要想知道p的PR值，就得知道链向p所有网页的PR值，而要知道其他网页的PR值，又得先知道p的PR值。

为了打破这个循环，佩奇和布林采用了一个很巧妙的思路， 即分析一个虚拟用户在互联网上的漫游过程。 他们假定：虚拟用户一旦访问了一个网页，下一步将以相同的概率访问被该网页所链接的任何一个其它网页[3]。比如，网页pi包含N个超链接，那么虚拟用户访问这N个页面中的任何一个的概率是1/N。那么，网页的排序就可以看成一个虚拟用户在万维网漫游了很长时间，页面被访问的概率越大，其PR值就越高，网页排名也越靠前。

先从简化的PageRank说起，以PageRank论文的例子为例，看看PageRank是怎么计算的，如下：

Fig. 2: Simplified PageRank calculation (image from [1])