PageRank算法&TrustRank算法

PR&TR的介绍及实现

Posted by ZhY on March 10, 2017

PageRank算法

简介

PageRank算法计算每一个网页的PageRank值,然后根据这个值的大小对网页的重要性进行排序。它的思想是模拟一个悠闲的上网者,上网者首先随机选择一个网页打开,然后在这个网页上呆了几分钟后,跳转到该网页所指向的链接,这样无所事事、漫无目的地在网页上跳来跳去,PageRank就是估计这个悠闲的上网者分布在各个网页上的概率。

算法流程

现在有四个网页A、B、C、D,如果当前上网者在A网页,则他会以1/3的概率转到B、C、D网页中的某一个,M的矩阵中M[i][j]表示从网页j到i的概率 现在假设上网者在每个网页的几率相等,即1/4,于是得到了第一次转移后该上网者在各个网页的概率。若满足图时强连通图(任意网页都可到达其他任意网页),则该图符合马尔科夫模型,V会收敛到V=[3/9,2/9,2/9,2/9] 考虑到互联网中的网页不满足强连通图的特性且可能有自回路,因此需对该算法进行修正

完善

由于浏览器有地址栏,而上网者在上网的过程中有可能在地址栏输入某一网址并进行跳转,因此该上网者可能从地址栏跳入各个网站,这个概率为1/n(存在输入网址为当前网址的情况——可以将这种情况当成是刷新)。

在这种情况下,上网者进入一个网页之后想要进行的活动有两种可能:一种是查看当前网页,这种情况的概率假设为a;另一种是从地址栏进行跳转,这种情况的概率即为1-a

通过上述假设,可以得出公式 该公式也是PageRank算法的核心部分

TrustRank算法

简介

TrustRank算法是一种半自动化技术改进排名的方案,是由斯坦福大学和雅虎研究人员提出的链接分析技术。基本思想是在为网页排名时,要考虑到该页面所在站点的信任指数和权威性。

基本假设

一、好的网站很少会链接到坏的网站,反之则不成立。

二、如果能挑选出可以百分之百信任的网站,这些网站的TrustRank值评为最高,这些TrustRank最高的网站所链接到的网站信任指数稍微降低,但是也会很高。与此类似,第二层被信任的网站链接出去的第三层网站,信任度继续下降。

这样,通过TrustRank算法,就能给所有网站计算出相应的信任指数,离第一层网站越远,成为垃圾网站的可能性就越大。

算法流程

先用人工去识别高质量的页面(即“种子”页面),那么由“种子”页面指向的页面也可能是高质量页面,即其TrustRank也高,与“种子”页面的链接越远,页面的TrustRank越低。

TrustRank采用半自动的方法区分垃圾文件和高质量较文件。依靠专家去评估一系列“种子”页面的TrustRank值。一旦确定了“种子”页面,就容易区分好页面和垃圾页面,通过机器分析链接结构来确定其它页面的TrustRank值。

首先我们有如下几个网页 TrustRank的重点在于挑选种子网页,在这里使用E的逆矩阵,通过PageRank算法找到进入网页几率最大的网页 下一步挑选种子网页,通过PageRank算法迭代M次最终得到值S。 在这里我们选取α为0.85,M为20,此时可以得到评分最高 的三个网页为2,4,5。这时候将2,4,5挑选出来作为备选的种子网页 这时候人工的专家来进行种子网页识别,将图还原为原来的图,如果认为i网页是好网页,则O(i)=1,否则O(i)=0 将种子网页进行分类,然后根据S+中的数量m,上网者在每个其中的网页的概率为1/m。因此可以得出新的上网者初始访问网页的概率矩阵。 此时用新的上网者初始停留概率来计算,可得最终TrustRank值

判定因素

一些能够影响站点TrustRank值从而影响排名的因素:

域名注册期5年或5年有余

网站由专业侍服提供服务

网站加载迅速

内容是原创的

游客在每页上驻留时间超过90秒

网站被多个国际IP段引用

网站在其所处行业时权威站点

参考资料及参考链接

Combating Web Spam with TrustRank

trustrank算法

PageRank算法简介及Map-Reduce实现