专栏首页五分钟学算法啥是佩奇排名算法

啥是佩奇排名算法

佩奇排名介绍

佩奇排名是根据页面之间的链接结构计算页面的值的一种算法。下面我们通过动画来理解进行计算的具体流程。

假设一个正方形表示一个 WEB 页面,一个箭头表示一个页面之间的链接。

此图表明下面 3 页包含指向上面 1 页的链接

在佩奇排名算法中,网页指向的链接越多,页面被确定为越重要。

因此,在这里,确定首页最重要。

确定首页最重要

实际上,每个页面的重要性都是通过计算来量化的。

基本的计算方法思想

1.未链接的页面分数为 1

未链接的页面分数为 1

2.有链接的页面得分为正在链接的页面的总得分

.有链接的页面得分为正在链接的页面的总得分

3.当有多个网页的链接时,链接分数均匀分布

链接分数均匀分布

4.来自高度链接网页的链接具有很高的价值

该图中心页面有三个独立页面指向它的链接,所以它的分数是 3 。 首页有一个很大的分数,因为链接是从分数为 3 的页面指向它的。

在动画中的六个页面中,判断最上面的页面是最重要的页面----这是佩奇排名的基本思想。

基本的计算方法思想的循环问题

如果按照顺序来计算每个页面的分数时,那么就会出现问题:以这种方式计算,它将无限循环,并且在循环中的页面得分在任何地方都会很高。

循环的问题可以通过“随机游走模型”的计算方法来解决。

随机游走模型

以小猪佩奇浏览网页为例。

小猪佩奇开始访问「五分钟学算法」中有趣的页面,那么从这个左下角页面开始。

它们跟随一个链接并移动到另外的一个页面,看了一些之后,发现不敢兴趣了,这样就停止了浏览。

然后,又一天,它在小吴的推荐下,在完全不同的页面进行浏览,跟随一个链接并移动到另外的一个页面,一旦失去兴趣就停止浏览。

像这样,重复从某个页面开始浏览,移动几页后便停止的操作,如果从互联网空间一侧进行观察,就像网页浏览的人:重复移动页面几次后传送到一个完全不同的页面。

量化随机游走模型

假设 1 - α 代表选择当前页面中的一个链接的概率。

α代表该人将传送到其他页面的概率。

现在用 随机游走模型 处理上述的循环问题。

如果总页面访问次数达到1000次之后,使用百分比进行表示:那么这个值就表示“在某个时间点查看页面的概率”

更实用的计算方法

如图所示,现在来尝试计算复杂的链接网络中每个页面的分数。

现在均匀设置分数,使总分加起来为 1 。而后根据网页浏览者的移动,来计算每个页面的概率。

移动 n 次时出现在 A 中的概率表示未 PAn,移动 n 次时出现在 B 中的概率表示未 PBn

举一个例子,在移动 1 次之后求在 A 的概率 PA 1

在 C 选择移动的概率是 1-α

其中,移动到 A 的一种场景是,C 中的佩奇选择了移动而不是传送。另外,这里选择了 A 而不是 B 作为目的地。 并且,根据上面的 当有多个网页的链接时,链接分数均匀分布 这条规则,从 A 或 B 选择 A 的概率是 0.5 。

因此,从 C 移动到 A 的概率是 PC0 ✖️ (1-α) ✖️ 0.5

A 被选为传送目标的概率是 0.25

A 被选为传送目标的概率是 0.25 ,根据前面的理论:在 A、B、C、D 中小佩奇选择传送的概率为 α。因此,通过传送移动到 A 的概率为 α ✖️ 0.25。 所以,移动一次后在 A 的概率为 PA1 = PC0 ✖️ ( 1 - α ) ✖️ 0.5 + α ✖️ 0.25

其中 PC0 = 0.25α = 0.15,代入计算后 PA1 = 0.14375

这样,通过计算后 B 、 C 、D 页的概率也更新了。

B 、 C 、D 页的概率也更新了

上面在移动 1 次之后这四个页面的概率更新情况,根据上述相同的方法计算 2 次后小佩奇浏览在每个页面的概率。

移动 2 次后

同样的,经过大量的移动,在每个页面上的概率逐渐趋于固定值。当数值固定是,计算也就完成了。

End

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员小吴

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 超全面!如何用 GitHub 从零开始搭建一个博客 ?

    之前小吴写过一篇如何使用 GitHub 搭建个人博客的文章:【新手向】从零开始搭建一个酷炫免费的个人博客

    五分钟学算法
  • 我搞 CRUD 的,你跟我说算法有用?

    很多Java开发同学经常有一个疑惑,搞Java开发也需要懂算法吗?本文咱们就来谈谈这个问题。

    五分钟学算法
  • 10% + 10% = 0.11 ?是 bug 还是 feature ?微软开源的计算器项目告诉你答案!

    近日,关于手机计算器10%+10%=0.11的事情火热,多个品牌的手机未能幸免,基本“阵亡”,同时还包括了windows10的自带标准计算器。你的手机阵亡了吗?

    五分钟学算法
  • 你知道“啥是佩奇”,却不一定了解佩奇排名算法

    佩奇排名是根据页面之间的链接结构计算页面的值的一种算法。下面我们通过动画来理解进行计算的具体流程。

    AI科技大本营
  • 我的CMS开发记-4 介绍一下DotNetNuke的系统执行流程

           有朋友说应该写个大致结构出来。想想也有道理,那么我就来介绍一下Dotnetnuke的执行流程。基本上我这个就是照搬他的 基本思路     一个站点...

    用户1687945
  • 前端程序员必知:单页面应用的核心

    这几年里,单页面应用的框架令人应接不暇,各种新的概念也层出不穷。从过去的 jQuery Mobie、Backbone 到今天的 Angular 2、React、...

    Phodal
  • 浅谈移动端页面无刷新跳转问题的解决方案

    祈澈菇凉
  • 外链建设:认识PageRank

    谷歌核心是页面排名(PageRank),基于网站每个页面的分数,网站链接的流行度与指向页面链接的数量和质量有关,并被谷歌用作页面排名和搜索结果排名的标准之一。

    林雍岷
  • 移动端复杂运营页解决方案的探索和实践

    摘要 如何成为一名优秀的切图工程师?百度资深研发工程师潘征与大家分享自己的工作心得。 ? ROLE移动端酷炫运营页 2014年开始,我在我们部门负责移动端酷炫运...

    IT大咖说
  • 为什么PostgreSQL抛弃了LRU算法而使用时钟扫描?

    我们知道LRU(Least Recently Used)最近最少使用算法被广泛运用于操作系统及数据库的内存淘汰机制上,比如mysql的缓冲区页面置换算法就是使用...

    数据库架构之美

扫码关注云+社区

领取腾讯云代金券