前面我们学习了PageRank算法的基本原理
事物往往是这样的,基本原理呢代表了一般性
那在现实中往往会遇到各种各样的特殊性,有些呢不重要或者不经常出现
因此可以不太管它啊,理解它们的存在就可以了
但是另外一些特殊性,或是特殊情况可能十分重要
必须要有系统的处理方法,否则呢,系统原理的用处呢就会大打折扣
这一节我们就来看一个情况,是针对PageRank算法 上一节啊,我们用这个图做了一个
PageRank算路,啊,很正常啊,没有什么令人吃惊的情况
如果稍微变化一下
变化呢啊我们去掉这条边
也去掉这条边,增加呢这样两条边
啊增加这样两条边 就得到不同的一个网络结构图,就是右边这个样子
我们来看看会发生什么情况,啊 ,在右边这个网络上边
如果运行PageRank算法
我们会看到F与G这么样的一个节点
就显得很自私
它们会不断地吸收别人的价值,但从不对外分享 因为它们没有对外的边
而且呢它们甚至有共谋作弊的嫌疑,我们就看看这个F自己啊
它似乎也有往外的边,这个G也是一样的
似乎也有往外的边,但是如果我们把它们两个看在一起
作为一个整体看的话呢
它们只是有吸纳,而没有贡献
在这样的网络上运行PageRank其结果是可想而知的
最后的结果就是F和G每个人0.5,其他的节点都是0
这个啊就是在 右边那个网络上啊运行PageRank基本算法
的终计,一轮轮一直运行下来
我们看到尽管开始的 八个节点都一样,都是0.125,这是我们最初的初始值,八个节点都
是0.125 它是一样的,啊,这个这一行呢表示它们这个更新的公式,根据这个网络结构
但是整个趋势,我们看到这些数字所有的趋势,就是所有的价值呢,都向
F,随着时间的进展,这个,这个叫时间的进展
F与G,我们就看到这些个值啊,似乎就有这么一个,就有这么一个态势
啊,有这么一个态势,向F和G进展
啊上面这些呢是越来越小
下面这是越来越大,越来越大,一直到,看这下面
它们趋向于0.5,F和G
现在没几轮它们已经是0.48了,0.48
而其他的,本来它们都好好的,我们来看一下,我们来说一个
这个A,啊这个A,它从0.125到这一轮的时候,它已经是0.006了
啊它们都越来越小,所有的值呢趋向于向F和G来集中
那么在这个网络中,F和G这两个节点,就真的那么重要吗? 似乎很难找到什么论据说明这一点
因此呢这也可以说是PageRank这个基本算法重要的缺陷
它太理想化了,只是适合于人人都贡献,每个群体都向外贡献的场合
这样一个缺陷被有些个网站抓住
刻意做出了一些链接关系,不正当抬高了自己的PageRank
这样的情况属于重要的特殊情况
因此需要有应对,一个办法就是这里要讲的同比缩减
与这个统一补偿,它是PageRank基本算法的一种修正,或者说是一种推广
引入一个参数,S,啊引入一个参数这个
S啊 在0和1之间,啊在0和1之间,如果S等于1的话呢就回到了
基本算法的情况,所以呢,做出一个推广
具体来说,在这个PageRank基本算法,具体算法执行的过程中
每一轮结束,每一轮结束,就给这个节点的值呢,统一
乘以S,节点的值统一乘以S
就是,这叫,都乘以一个小于1的比例因子
S,也就是让它们按照相同的比例缩减
然后再给每个节点加上一个(1-s)/n这样
这样算出来就称为统一补偿
可以想到,如果原来的值较大,比较大,那么缩减和补偿损失呢就会较大
如果原来的那个值较小,这么缩减和补偿后呢就可能得到一个净增加
这样呢就既维持了所有PageRank值等于1的这么
一个性质,就是这么一个 PR就叫PageRank
也防止了PageRank的值啊过渡的集中到个别节点上
这个呢是在刚才那个病态结构那个图上,设S
等于0.8啊,这相当于缩减0.8
计算的那个节点,运行PageRank算法
可以看到呢尽管这个F和G拿到的价值还是较大
但是绝不会全部的就被它俩瓜分了,F和G,也运行了这么多轮
它们的值到0.27,但是不会像刚才它们要趋向0.5的
那种情况 那么当每个节点
初始的话都为1/n的时候,这个算法每一轮完成后呢
每个节点得到的PageRank的值可以有一种概率性的解释
这里就是说啊,是随机游走
相应部署落在一个节点上的概率
在引入了同比缩减和统一补偿机制的情况下呢
对应的修改随机游走的规则,允许
在中途呢随机选择其他的节点,也会有类似的结论
那么这一周里我们讨论的问题是比较现代的 相比前几周的话题
那些个话题起源都有好几十年了,这一周的话题起源
只有十多年,我们看到信息一旦刻画成一种网络
其中的边 自然的隐含着一种推荐或者引用的关系,那么就可以用这种关系对信息的作用进行
评估,这些作用可能有不同的含义,比如影响力啊,重要性啊,权威性啊
新颖性等等,都因评估的需求而定
同时评估这种与网络结构有关的性质
先进的评估方法,无论是HITS,还是PageRank
都不仅考虑局部结构,比如一个节点的度数啊
而且还会考虑全局结构带来的影响,也就是这个节点的性质 的值在这个网络中的传播
我们学习了注明的HITS算法和Page算法的思想
一方面呢我们强调它们的思想精华
另外一方面我们也展示了当理想遇到现实的时候可能出现的问题
以及对他们进行处理的方式