Return to site

谷歌的PageRank算法,解释

· seo优化

今天早些时候,来自Majestic的Dixon Jones 在Twitter上分享了 一个关于PageRank实际工作原理的全面,易懂的解释。

我自己给了它一块手表,并认为这是一个重温这个过去20年来对世界产生了很大影响的数学的好时机。

作为旁注,我们知道截至2017年,当PageRank在2016年从工具栏中删除时,它仍然是整体排名算法的重要组成部分, 因此值得理解。

琼斯从简单的 - 或者至少是直接的 - 公式开始。

对于那些不喜欢数学的人,或者自从上一个微积分课以来可能忘记了一些技术术语的人,这个公式会像这样大声朗读:

“此迭代中页面的PageRank等于1减去阻尼因子,加上对于页面中的每个链接(除了链接到自身),添加该页面的页面排名除以页面上的出站链接数量和减阻因子减少了。“

回到最初的Google论文
在这一点上,琼斯在视频中向前推进了一个更简单,更有用的计算版本。他推出了excel,一个简单的5节点视觉效果,并在15次迭代中绘制出排名算法。好东西。

就个人而言,我想要更多的数学,所以我回过头来阅读“ 大型超文本网络搜索引擎剖析 ”的完整版本(自然的第一步)。这是Larry Page和Sergey Brin在1997年撰写的论文.Aka是他们在斯坦福大学计算机科学系出版的Google的论文。(是的,它很长,今晚我会工作一点。一切都很有趣!)

这是一个开场白:“ 在本文中,我们向Google展示了一个大型搜索引擎的原型,它大量使用了超文本中存在的结构。”

休闲,按照他们的整体,持续的风格。

作为一个额外的有趣事实,我们自己的搜索引擎手表被引用在Google首张论文中!除了佩奇和布林本人之外,截至1997年11月已经有1亿个网络文件。

无论如何,回去工作。

以下是最初定义PageRank计算的方法:
“学术引文文献已应用于网络,主要是通过计算给定页面的引用或反向链接。这给出了页面重要性或质量的一些近似值。PageRank通过不平等地计算来自所有页面的链接以及通过页面上的链接数量进行标准化来扩展这一想法。PageRank定义如下:

我们假设页面A具有指向它的页面T1 ... Tn(即,引用)。参数d是阻尼系数,可以设置在0和1之间。我们通常将d设置为0.85。关于d的更多细节将在下一节中介绍。此外,C(A)被定义为从页面A出来的链接数。页面A的PageRank如下:

PR(A)=(1-d)+ d(PR(T1)/ C(T1)+ ... + PR(Tn)/ C(Tn))

请注意,PageRanks在网页上形成概率分布,因此所有网页的PageRanks总和为1。

PageRank或 PR(A) 可以使用简单的迭代算法计算,并且对应于web的规范化链接矩阵的主特征向量。此外,在中型工作站上,可以在几个小时内计算出2600万个网页的PageRank。还有许多其他细节超出了本文的范围。“

那是什么意思?
和我们一起承担!这是我们的公式:

PR(A)=(1-d)+ d(PR(T1)/ C(T1)+ ... + PR(Tn)/ C(Tn))

请注意,这与上图相同,不同之处在于照片通过替换大写sigma(Σ)来“简化”等式的第二部分,这是一个数学求和的符号,即对所有页面执行此公式1通过n然后将它们加起来。

因此,为了计算给定页面A的PageRank,我们首先取1减去阻尼因子(d)。D通常设置为.85,如其原始论文中所示。

然后,我们获取指向和来自页面A的所有页面的PageRank,将它们相加,然后乘以阻尼因子0.85。

没那么糟,对吧?说起来容易做起来难。

PageRank是一种迭代算法
也许你的眼睛盯着这部分,但布林和谢尔文实际上在他们的定义中使用了“特征向量”这个词。我不得不查一查。

显然,特征向量在微分方程中起着重要作用。前缀“eigen”来自德语的“正确”或“特征”。还存在特征值和特征。

正如罗杰斯 在他关于PageRank的经典论文中指出的那样,关于特征向量片的最大特色是它是一种数学类型,让你可以使用多个运动部件。“我们可以继续计算页面的PageRank 而不知道其他页面PR的最终值。这似乎很奇怪,但基本上,每次我们运行计算时,我们都会对最终值进行更接近的估计。所以我们需要做的就是记住我们计算的每个值,并重复计算很多次,直到数字停止变化很多。“

或者换句话说,特征向量的重要性在于PageRank是一种迭代算法。重复计算的次数越多,越接近最准确的数字。

PageRank在Excel中可视化
在他的视频中,琼斯非常直接地参与了有趣的部分,这就是为什么它在短短18分钟内如此有效。他演示了如何通过5个相互链接的网站的例子来计算PageRank。

然后他将它带回到excel的计算中:

并演示如何通过在底部取数字行并重复计算来迭代。

这样做后,数字最终会开始趋于平稳(这只是在15次迭代之后):

或者正如有些人可能会将这张照片标题为“野外的特征向量”。

琼斯提出的其他有趣观察:
链接计数(只是总数)是一个糟糕的指标。我们需要更多地关注每个页面的排名。
这是页面级别的排名,而不是域名权限。PageRank只查看过各个页面。
大多数页面根本没有任何排名。在他的例子中,前10名中的前3名占总排名的75-80%。

All Posts
×

Almost done…

We just sent you an email. Please click the link in the email to confirm your subscription!

OKSubscriptions powered by Strikingly