pagerank算法原理(PageRank算法优缺点分析)

佩奇排名(PageRank),又称网页排名、谷歌左侧排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

数据挖掘领域十大经典算法:PageRank算法

简介

佩奇排名(PageRank),又称网页排名、谷歌左侧排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。

PageRank通过网络浩瀚的超链接关系来确定一个页面的等级。Google把从A页面到B页面的链接解释为A页面给B页面投票,Google根据投票来源(甚至来源的来源,即链接到A页面的页面)和投票目标的等级来决定新的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级提升。


基本思想

假设网页T存在一个指向网页A的连接,则表明T的全部者觉得A比較重要,从而把T的一部分重要性得分赋予A。这个重要性得分值为:PR(T)/L(T)

当中PR(T)为T的PageRank值,L(T)为T的出链数

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

即一个页面的得票数由全部链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由全部链向它的页面(链入页面)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反假设一个页面没有不论什么链入页面,那么它没有等级。

数据挖掘领域十大经典算法:PageRank算法

算法原理

1 )普遍情况

首先,PageRank算法预先给每个网页一个PR值(PR值指代PageRank值),PR值在物理意义上为一个网页被访问的概率,所以一般是1/N,其中N为网页总数。

另外,所有网页的PR值的和一般为1。(如果实在不为1也不是不行,最后算出来的不同网页之间PR值的大小关系仍然是正确的,只是这个数值不能直接地反映概率罢了。)

接着,运用下面的算法不断迭代计算,直至达到平稳分布为止。

迭代算法到底是如何进行的呢?下面我们给出一个具体的例子:

互联网中的众多网页可以看成一个有向图,箭头的指向即为链接的链入,如下图所示有4个网页:

数据挖掘领域十大经典算法:PageRank算法

根据上图,我们可以得到A的PR值为:

数据挖掘领域十大经典算法:PageRank算法

但是从图中可以看出,除了C只有A这一个出口外,B和D都不止一个出口,所以上面的那个公式并不是非常正确。举个实际的例子,一个用户正在浏览网页B,那么接下来他去往网页A和网页D的概率在统计学上应该是一样的,所以A的PR值应该表示为:

数据挖掘领域十大经典算法:PageRank算法

2) 特殊情况(没有出链)

网络中不乏一些没有出链的网页,如下图:

数据挖掘领域十大经典算法:PageRank算法

其中,网页C没有出链,也就是说网页C对其他网页没有PR值的贡献,我们不喜欢这种“自私”的网页(其实是为了满足 Markov 链的收敛性),于是设定其对所有网页(包括它自己)都有出链,则此图中A的PR值表示为:

数据挖掘领域十大经典算法:PageRank算法

3) 特殊情况(出链循环圈)

网络中还存在这样的网页:只对自己有出链,或者几个网页的出链形成一个循环圈。那么在不断迭代的过程中,这一个或几个网页的PR值将只增不减,这显然是不合理的。

如下图中的C就只对自己有出链:

数据挖掘领域十大经典算法:PageRank算法

那么如何解决这个问题呢?我们假设某人正在浏览网页C,显然他不会一直停留在网页C,他可能会随机地输入一个网址从而去往另一个网页,并且其跳转到每个网页的概率是一样的。

于是此图中A的PR值表示为:

数据挖掘领域十大经典算法:PageRank算法

综上,一般情况下,一个网页的PR值计算公式如下:

数据挖掘领域十大经典算法:PageRank算法

其中,Mpi是所有对pi网页有出链的网页集合,L(pj)是网页pj的出链数目,N是网页总数,α一般取0.85。

根据上面的公式,我们就可以计算出每个网页的PR值,在不断迭代并趋于平稳的时候,即为最终结果。


PageRank算法优缺点

长处:

是一个与查询无关的静态算法,全部网页的PageRank值通过离线计算获得;有效降低在线查询时的计算量,极大降低了查询响应时间。

缺点:

1)人们的查询具有主题特征,PageRank忽略了主题相关性,导致结果的相关性和主题性减少

2)旧的页面等级会比新页面高。由于即使是非常好的新页面也不会有非常多上游链接,除非它是某个网站的子网站。

        

版权声明:本文内容来源于互联网和用户投稿,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 taijiseo@qq.com 举报,一经查实,本站将立刻删除。

   

给TA买糖
共{{data.count}}人
人已赞赏
投稿

什么是新闻营销?新闻营销的优势有哪些?

2021-9-1 14:23:27

投稿

emule服务器怎么连接(eMule连接服务器教程)

2021-9-1 15:57:10

个人中心
今日签到
有新私信 私信列表
搜索