URL ссылки

blog.CSDN.net/Grace78/AR…

上面的公式，
u是需要计算pr值的网页，Bu是网页u的所有入链集合，及所有指向u网页的网页集合。
针对入链集合中的任意页面v，它能给u带来的影响力是其自身的pr(v)除以自身v的出链数量。
及页面v把自身的影响力pr(v)平均分配给了它的出链。
这样统计所有能给u带来链接的页面v，得到总和，就是页面u的影响力，及为pr(u)

Суммировать

pagerank
网页排名，网页级别(1-10级，级别越高，越重要，越受欢迎)，网页重要程度，网页受欢迎程度。
衡量网页重要程度的一种指标。
是谷歌的镇店之宝
衡量网络节点的重要程度，这里的节点就是网络中数以亿计的网页。
链接分析算法。

矩阵转移，表示网页节点之间的跳转概率。
如果网络中有n个网页节点，则可以构建成一个n*n的矩阵。矩阵中的任何一个元素都是某个网页节点跳转到另一个网页节点的概率。

pagerank的2个假设：
   <1>数量假设：接收来自其他网页的入链越多，说明这个网页越重要(暂时不考虑质量，只考虑数量)
   <2>质量假设：接收来自其他网页的质量不同，也是影响着这个网页的重要性。
              通俗来讲就是：身边的朋友牛逼，那我也牛逼，哈哈哈哈。

一个网页的pr值，除以它的出链数，就是该网页贡献给其他网页的pr值。

一个网页的pr值，只与它的入链有关系。
如果一个网页没有任何的入链接，那么它就是孤立网页。
阻尼系数alpha，默认值是0.85.
也就是说，如果一个网页指向2另一个网页，并不一定会100%跳转过去，
阻尼系数alpha就是这个跳转的概率

pagerank是一个与查询无关的静态算法。

Источник алгоритма PageRank

这个要从搜索引擎的发展开始。
最早的搜索引擎采用的是人工分类时代。及人工进行网页的`分类`，并且整理出`高质量`的网页。
后来网页的数量越来越多，人工已经不能实现了，于是搜索进入到了`文本检索`的时代，及根据用户的查询query,计算关键词与网页的相关程度来返回搜索的结果。
这种方法突破了网页数量的限制，但是效果不好，因为总有一些网页来回得倒腾某些关键词使得自己的网页排名靠前。
于是，后来出现了pagerank算法。
这是在用户query的关键词与网页相似度的基础上，又增加了网页的重要程度。

1/ Что такое рейтинг страницы

PageRank，即网页排名，又称网页级别，是衡量网页重要程度的指标。
PageRank是谷歌的镇店之宝，是一种用来对网络中节点的重要性进行排序的算法，这里的节点指的是网页。
PageRank是Google用来标识网页的等级/重要性的一种方法，是Google用来衡量一个网站的好坏的唯一标准。

为什么叫“PageRank”呢？一方面这个算法最初是用来对网页重要性进行排序的，另一方面它是Sergey Brin和Lawrence Page提出的。这个名字一语双关，特别好。
自从Google在商业上获得空前的成功后，该算法也成为其他搜索引擎和学术界十分关注的计算模型。
目前很多重要的链接分析算法都是在PageRank算法基础上衍生出来的。

在揉合了诸如Title标识和Keywords标识等所有其它因素之后，Google通过PageRank来调整重要性结果，使那些更具“等级/重要性”的网页在搜索结果中的排名获得提升，从而提高搜索结果的相关性和质量。
其级别从0到10级，10级为满分。级别越高，PR值越高。
PR值越高说明该网页越受欢迎（越重要）。

例如：一个PR值为1的网页表明这个网站不太具有流行度，而PR值为7到10则表明这个网站非常受欢迎。
一般PR值达到4，就算是一个不错的网站了。
Google把自己的网站的PR值定到10，这说明Google这个网站是非常受欢迎的，也可以说这个网站非常重要。

2/принцип PageRank

互联网是一张大网，是一张有向的社交网络图。是由无数个网页构成的，网页就是图中的节点node。
如果网页A可以跳转到网页B，则存在一条有向边A->B，
如果网页D可以跳转到网C，则存在一条有向边D->C。
下面是一个简单的示例：

上图中只有四个网页，如果有一个人当前在A网页，那么他会各以1/3的概率分别跳转到B、C、D网页，
这里的3表示A有3条出链，如果一个网页有k条出链，那么它跳转到其他任意一个网页上的概率是1/k，
同理D有2条出链，则从D跳转到B、C的概率各为1/2，
而B到C的概率为0，因为B没有出链指向C。

一般用`转移矩阵`表示网页节点之间的跳转概率，如果用n表示网页的数目，则转移矩阵M是一个n*n的方阵；
如果网页j有k个出链，那么对每一个出链指向的网页i，有M[i][j]=1/k，
而其他网页的M[i][j]=0；
上面示例图对应的转移矩阵如下：

pagerank算法总的来说就是一个网页被访问的概率，所以一般是1/N。N是总的网页的数量。
一般情况下，所有网页的pr值的总和是1。
如果和不是1的话也可以，最后计算出来的不同网页的pr值的大小关系依然是成立的，只是不能直接反应概率的大小了。

3/Процесс алгоритма PageRank

pagerank算法是互联网中的众多网页看作是一张有向图。
算法过程是：
    <1>先给网页一个初始pr值，一般是1/N，N是互联网中网页的总数。
    <2>然后按照下面的公式不断地更新计算各个网页的pr值，一直到收敛。
       公式中的alpha是阻尼系数，默认是0.85，当然可以根据实际情况修改。

    <3>为了解决有些网页不被链接的问题(称之为孤立网页，比如有些新的网页就是这种情况)
       针对这种情况，引入了teleporting这个概念。
       这个概念是：我们认为在任何一个用户，都有可能以一个极小的概率从当前网页瞬间跳转到另外一个随机的页面。
       teleporting = （1-alpha）/ N
       该值很小

2 предположения 4/pagerank

pagerank的计算充分利用了2个假设，及‘数量假设’和‘质量假设’，

<1>数量假设：在互联网中，如果一个页面接收到的来自其他网页的入链数量越多，那么这个页面越重要。
           总之一句话就是：一个网页的入链越多，页面越重要。
           
<2>质量假设：指向页面A的入链质量不同，质量高的入链页面会给页面A带来更大的权重。
           所以越是质量高的页面指向页面A，则页面A越重要。
           总之一句话：身边的朋友越牛逼，也可以代表这个人很牛逼。

5/Как сходится расчет PageRank?

PageRank算法刚开始赋予每个网页相同的重要性得分，
通过迭代递归计算来更新每个页面节点的PageRank得分，直到得分稳定为止。

PageRank计算得出的结果是网页的重要性评价，这和用户输入的查询是没有任何关系的，即算法是主题无关的。
假设有一个搜索引擎（例如百度搜索引擎），其相似度计算函数不考虑内容相似因素，完全采用PageRank来进行排序，那么这个搜索引擎的表现是什么样子的呢？这个搜索引擎对于任意不同的查询请求query，返回的结果都是相同的，即返回PageRank值最高的页面。

也就是说，在搜索引擎中，就需要通过用户的query来计算网页与query的相似度，
又需要计算相似度比较高的网页的pagerank值。
然后综合这2方面的考虑，最终返还给用户最优质的网页。

6/Основная идея рейтинга страниц

如果网页T存在一个指向网页A的链接，及T-->A，
则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/L(T)
其中PR（T）为T的PageRank值，L(T)为T的出链数

则A的PageRank值为一系列类似于T的页面重要性得分值的累加。

即一个页面的重要程度由所有指向它的页面的重要程度来决定的
一个页面的PageRank是由所有链向它的页面的重要性经过递归算法得到的。
一个有较多入链的页面有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。

7/расчет рейтинга страницы

雨露均沾：每个网页对于它的每一个出链的pr贡献值都是均等的。

8/Корректировка формулы расчета PageRank (добавлен коэффициент демпфирования альфа)

一些网页的出链为0，也就是那些不链接其他任何网页的网页，称为孤立网页。
因此需要对 PageRank公式 进行修正，即在简单公式的基础上增加了阻尼系数q，q一般取值q=0.85。

q的意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率。 
1 - q = 0.15，就是用户停止继续向后浏览，随机跳到新URL的概率。
q的取值，需要根据具体的场景自己决定。

最后，即所有这些被换算为一个百分比再乘上一个系数q。
但是，由于有的页面的PageRank会是0。所以，Google通过数学系统给了每个页面一个最小值，及1-q。

从上面的图中，可以知道，
累加得到所有的入链网页的pr值之后，需要✖️阻尼系数，然后再加上自己本来就有的(1-q)

Преимущества и недостатки 9/pagerank

优点：
   是一个与查询无关的静态算法，所有网页的pr值都是经过离线计算来的。
   可以有效减少在线查询的计算量，极大的降低了用户查询的响应时间。
   
缺点：
   (1)没有区分站内导航链接。
      很多网站的首页都有很多对站内其他网页的链接?，称为站内导航链接。
      这些链接与不同网页之间的链接相比，肯定是后者更能体现出pagerank值的重要性。
      （比如58同城就是一个网站，这个网站有首页，我们可以从首页跳转到站内的其他网页，
        如果在首页又一个链接指向站内的其他网页，这就是站内导航链接）
      
   (2)没有过滤到广告链接和功能链接。
      比如分享到微博等链接。
      这些链接没有什么实际价值，前者链接到广告页面，后者常常链接到某个社交网站首页。
      
   (3)对新网页不友好。
      一个新网页的一般入链比较少。
      即使它的网页质量很高，要成为一个高PR值的网页仍然需要很长的时间的推广
      
   (4)人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低

Почему 10/pagerank сходится?

 为了证明pagerank的计算是可以收敛的，需要转换为markov过程。
 如何转换为markov过程呢？

11/ Несколько концепций рейтинга страниц

等级泄漏rank leak：
如果一个节点只有入度，没有出度，吸收了其他节点的pr值而不释放，最终会导致其他节点的pr值为0

等级沉淀 rank sink：
如果一个节点只有出度，没有入度，最终导致这个节点的pr值为0

为了解决这2个问题，拉里-佩奇提出了改进的pagerank模型。
该模型基于这样一个场景：在浏览网页时，用户并不总是依据链接跳转的方式，还有可能是用户就是要直接输入网址访问其他页面，虽然这个概率比较小。具体，定义阻尼因子alpha，表示用户通过链接跳转进入新的网页，一般设置为0.85