2.Page Rank算法的基本思想

    在Sergey Brin和Larry Page 的著名文章 the Page Rank Citation Ranking：Bring order to the web里，这两个Google创始人提出了现在被称为 Page Rank 的算法的基本思想。

在Brin和Page指出要利用互联网的链接结构来为网页计算一个可以用来表示网页的“重要”的通用指标。Brin和Page考虑到，既然在学术领域，被大量引用的文章往往就是比较“重要”的文章，那在互联网领域这样的规律同样适用。互联网上的网页之间是有联系的，一般来说，网页的管理者会通过网页上的联系向用户推荐认为内容相关并且值得浏览的网页。这样获得较多的关系的网页（也就是度数比较高的网页），可以被视为是大家“公认”比较值得关注的网页，因此也就比较“重要”。论文网

但只根据获得较多关系的网页来判断“重要性”显然不够严谨，有的网页虽然in-link少，但是指向它的都是Nature和New Worker类似的比较著名网站的网页，它就可能比获得一大堆无名网站联系的网页更重要。因此一个网页要获得较高的“重要性分值”可以有两种情况：1.指向它的网页很多，2. 指向它的网页不多，但都很“重要”。所谓的“重要”，又可以再次在链条的下一个环节上继续被分解为“多”或“重要”的问题。

Brin和Page在最终设计的Page Rank里，规定网页通过联系来传递“重要性分值”，每一个网页的总“重要性分值”就是所有指向它的网页传递给它的“重要性 分值”的加总。由此类推，分值就在整个网络中流动。从in-link来说，一个网页获得较高的分值可能是因为有很多网站给分，也可能是少数几个网页给分，但每个网页都给了它很高的分；从 out-link来讲，既然网页“收集”得到的分是一定的，那out-link愈多，每个out-link 给出去的分就越小。因此，Page Rank定理的核心思想是根本基础是从重要的网页链接过来的网页，必定还是重要优秀的网页的回归关系，根据改原理来判定所有网页的重要性。

    图1展示了的“重要性分值”是如何在网页间互相联系的。左上角的网页有 100分，通过两个out-link传给了右上角和右下角的网页，每个out-link传递出去 50分；左下角的网页有9分，通过 3个out-link 传递出去，每个out-link传递出去 3分，但只有一个out-link传递给右上角的网页，另外两个的传递对象不在这个示意图里，因此最后右上角的网页得到53分，右下角的网页得到50分，又因为它们都各有两个out-link，因此右上角网页每个out-link传递的分数要比右下角网页的高。

3.Page Rank算法的具体介绍

3.1 Page Rank算法

Page Rank算法的作用是评价网页的重要性，并以此作为搜索结果排序的重要依据之一，其算法思想：用户在浏览网页时主要通过点击不同超链接进行页面跳转，因此通过分析超链接组成的拓扑结构来推算每个网页被访问频率的高低，默认被用户访问最多的网页可能质量越高。可以把网络链接与邮箱链接图G（V，E）相对应，其中，V表示网页集合，E表示有向边集合。文献综述

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

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