PageRank简介 - webdancer's Blog
PageRank简介
今天去听了一个讲座，讲的是基于机器学习方法的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$的总的页面数目。
计算
常用的两种方法就是：数值迭代和线性代数的方法。后面在好好分析一下吧！
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.