PageRank简介 - webdancer's Blog

PageRank简介

webdancer posted @ 2012年5月23日 23:23 in 搜索引擎 with tags 搜索 , 1964 阅读

今天去听了一个讲座,讲的是基于机器学习方法的rank算法,讲到了PageRank(google.com)和HITS(ask.com)算法,本来就像看看PageRank是怎么回事,刚好借此机会学习一下。

 
概念
 
PageRank是以google创始人Larry Page命名的一种链接分析算法,它根据网页的相关性和重要性来给网页赋予一个权重值。一个网页p的权重值通常被p的PageRank,记作: PageRank(p)。
 
原理
 
一个页面的“得票数”由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投票。一个页面的PageRank是由所有链向它的页面(“链入页面”)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。简言之,“被越多优质的网页所指的网页,它是优质的概率就越大”。
 
看下面一个简单的例子,我们假设我们要处理的系统中含有四个页面(当然,实际的www有的页面数目要远远的大于这个数目),如下图所示。其中A,B,C,D四个节点代表了四个页面,其中B链接到了A,C,C链接到了A,D链接到了A,B,C。
 

 

现在我们来考虑一下PageRank的意思,假定我们有一个随机浏览者(random surfer),他在网上随机的浏览网页,现在他处于页面D,他有相同的概率去访问D链接到的页面,即概率为:$frac{1}{3}$,当他在页面上这样随机访问的时候,一些网页会比另外一些网页更经常的访问到。直觉上看,那些有更多链接指向他的页面要更容易被访问到。这也就是PageRank背后的思想:更经常访问的网站更重要。
 
下面计算A点的PageRank值。我们假设一个页面不能投票2次,所以B给每个页面半票,以同样的逻辑,D投出的票只有三分之一算到A的PageRank上。那么:
 
$PR(A) = \frac{PR(B)}{2} + PR(C) + \frac{PR(D)}{3}$
 
设L(p)为从页面p链接到的页面数目,则上面的式子可以写为:
 
$PR(A) = \frac{PR(B)}{L(B)} + \frac{PR(C)}{L(C)} + \frac{PR(D)}{L(D)}$
 
我们可以得到一般情况下,任意页面p的PageRank式子:
 
$PR(p_i) = \sum_{p_j \in M(p_i)} \frac{PR(p_j)}{L(p_j)}$
 
一个页面不能投票两次比较很理解,例如在上面的例子中,如果B,C页面的PR值不平均开,那么A链接的PR值肯定会超过B,C,如果A是一个新网站,而B,C都是经典网站,显然这种情况就有问题,而且平均开更符合我们的直觉:如果从B页面上随机的点击的话,那么B页面上每个链接的概率都是一样的,它的PR值也应该是平均开的。
 
对于那些没有链出的页面,比如例子中的A节点,没有链出,我们引入阻尼系数d(damping factor )的概念后,原来可能被分割的网络就变得连通起来,今天听那个老师讲这样最后的PageRank值最后就会收敛,从而用来进行排序。这样计算的公式变为:
 
$PR(p_i) = \frac{d}{N}+ d (\sum_{p_j \in M(p_i)} \frac{PR(p_j)}{L(p_j)})$
 
其中,N为链接到$p_i$的总的页面数目。
 
计算
常用的两种方法就是:数值迭代和线性代数的方法。后面在好好分析一下吧!

 

TNDGE Question Paper 说:
2022年8月19日 22:25

Tamilnadu Board Model Paper 2023 Class 7 Pdf Download with Answers for Tamil Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. TNDGE Question Paper Class 7 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee