Skip to content

四火的唠叨

一个纯正程序员的啰嗦

Menu
  • 所有文章
  • About Me
  • 关于四火
  • 旅行映像
  • 独立游戏
  • 资源链接
Menu

Google 矩阵

Posted on 04/03/201306/23/2019 by 四火

google matrix 使用一款搜索引擎,我们希望搜索结果能够拥有最佳的排序,Google 为它最核心的排序算法 PageRank 申请了专利。在 PageRank 以前,排序大多依靠对搜索关键字和目标页的匹配度来进行的,这种排序方式弊端明显,尤其对于善于堆砌关键字舞弊的页面,很容易就跳到了搜索结果的首页。Larry Page 和 Sergey Brin 开始着手解决这个问题,Google 排序的继承来自于互联网上网页之间的链接关系。一张网页被其它网页引用的次数越多,可以简单地认为这样的网页越受欢迎,当然在结果列表中应该越靠前。

前面提到了目标网页被引用网页的“ 数量”,另一条重要的判定 PageRank 级别的依据则是“ 质量”。换言之,质量高的网页所引用的网页,质量往往也比较高,所以质量高的网页投票所占权重理应更高。

在用户访问某一张网页时,假设他有 q 的概率去点击网页上的链接,并且点击该网页每条链接的概率都是相等的。如果该网页有 n 条链接的话,那么点击每条链接的概率就是 1/n。

在表现网页之间链接关系时,Google 使用了矩阵。假设互联网上共有 N 个页面,那么我们可以写出一个 N×N 的矩阵,其中的元素 pij,如果存在从页 i 被页 j 指向的链接(为什么使用“ 被指向” 而非“ 指向”,前文已经解释了),那么 pij 就大于 0,反之就等于 0。同时,每一列元素的取值都除以链接数 n(前文提到了),使得各列矢量总和成为 1,行矢量则表示了各个状态之间的迁移概率,这个最大特征值为 1 的矩阵就成为了 PageRank 矩阵。

现在给出 N 为 4 的一个例子(共有 A、B、C、D 四张网页)帮助说明这个矩阵(这个例子来自于这篇文章):

 small-web

可以看到矩阵 L 的几个非零元素的取值:

  • p31=1; 表示被 A 指向的只有 C
  • p12=1; 表示被 B 指向的只有 A
  • p13=p43=1/2; 表示被 C 指向的有 A 和 D
  • p14=p24=p34=1/3; 表示被 D 指向的有 A、B、C

于是,对于 A 来说,它的 PageRank 取值就可以表示为:

PR(A) = PR(B)/1 + PR(C)/2 + PR(D)/3

但这是在用户百分之百点击网页链接的情况下发生的,实际上,只有 p 概率的用户会点击网页链接,剩下 (1-p) 概率的用户会跳到无关的页面上去,而访问的页面恰好是 4 这个页面中 A 的概率只有 (1-p)/4(p 正是前文提到的“ 阻尼系数”(damping factor),Google 取 p 等于 0.85),所以:

PR(A) = (1-p)/4 + p(PR(B)/1 + PR(C)/2 + PR(D)/3)

推广到一般公式(pi 表示第 i 张网页,L(pj) 表示从 pi 链出网页的数量):

image

如果仅仅依赖这个公式,可以看得到每一个页面的 PageRank(pi) 的值都和其他页面有关系,这样一来,就没有办法直接解出这个 PageRank(pi) 的值来了。

不过,佩奇和布林想到了一个办法,有了 PageRank(pi) 的概念以后,PageRank 矩阵就可以用一个特征向量来表示:

image

由上述两个公式,可以得到(其中 l(pi,pj) 就是前文提到过的 pij):

image

接着给所有网页一个统一的初始权值,每次都用上面提到的 R 矩阵去乘以原始的 N×N 的矩阵,把结果这个新的矩阵继续去乘以那个 N×N 的原始矩阵,反复进行,相乘行为引起的矩阵变化越来越小,直到收敛到一个给定的值以内,停止。

这时的矩阵就包含了每个网页的 PageRank 特征向量,对于每个向量来说,它的每一个维度值去乘以该维度下的权值并累加,最终都可以转化为一个具体的 PageRank 的数字。

这就是 PageRank 计算最最基本的部分,Google 对于这种超大型矩阵相乘有自己的保密技术。截止到 2010 年,Google 索引的网页总数已经超过 5000 亿,也就是说,Google 必须解这个阶数的矩阵相乘问题,这是不是真的就是 MapReduce 之类的由来呢?

以上未特殊注明的公式截图来自于维基百科。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

×Scan to share with WeChat

你可能也喜欢看:

  1. 关于 Jeff Dean 的几个搞笑传言
  2. 从“Google 地图八位版” 看国内的抄袭
  3. 写在 Gmail 被墙后
  4. 为什么云计算服务是亚马逊先做出来?
  5. A page widgetization practice

4 thoughts on “Google 矩阵”

  1. Anonymous says:
    04/03/2013 at 9:58 AM

    p13=1; 表示被 A 指向的只有 C
    楼主笔误,
    p31=1; 表示被 A 指向的只有 C
    感谢楼主分享好文~~~

    Reply
    1. 四火 says:
      04/03/2013 at 10:10 AM

      是的。已经修正。谢谢。

      Reply
  2. lovelucy says:
    04/03/2013 at 9:55 AM

    不必解。更何况互联网的节点是快速动态变化的。
    有种算法叫 random walk,无限逼近真实值

    Reply
  3. Anonymous says:
    04/03/2013 at 9:03 AM

    好文。只是矩阵 L 的下标有点儿问题

    Reply

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

订阅·联系

四火,啰嗦的程序员一枚,现居西雅图

Amazon Google Groovy Hadoop Haskell Java JavaScript LeetCode Oracle Python Spark 互联网 前端 华为 历史 同步 团队 图解笔记 基础设施 工作 工作流 工具 工程师 应用系统 异步 微博 思考 技术 数据库 曼联 测试 生活 程序员 管理 系统设计 缓存 编码 编程范型 英语 西雅图 设计 评审 问题 面试 项目

分类

  • Algorithm and Data Structure (30)
  • Concurrency and Asynchronization (6)
  • System Architecture and Design (43)
  • Distributed System (18)
  • Tools Frameworks and Libs (13)
  • Storage and Data Access (8)
  • Front-end Development (33)
  • Programming Languages and Paradigms (55)
  • Testing and Quality Assurance (4)
  • Network and Communication (6)
  • Authentication and Authorization (6)
  • Automation and Operation Excellence (13)
  • Big Data and Machine Learning (5)
  • Product Design (7)
  • Hiring and Interviews (14)
  • Project and Team Management (14)
  • Engineering Culture (17)
  • Critical Thinking (25)
  • Career Growth (57)
  • Life Experience and Thoughts (45)

推荐文章

  • 谈谈分布式锁
  • 常见分布式系统设计图解(汇总)
  • 系统设计中的快速估算技巧
  • 从链表存在环的问题说起
  • 技术面试中,什么样的问题才是好问题?
  • 从物理时钟到逻辑时钟
  • 近期面试观摩的一些思考
  • RSA 背后的算法
  • 谈谈 Ops(汇总 + 最终篇):工具和实践
  • 不要让业务牵着鼻子走
  • 倔强的程序员
  • 谈谈微信的信息流
  • 评审的艺术——谈谈现实中的代码评审
  • Blog 安全问题小记
  • 求第 K 个数的问题
  • 一些前端框架的比较(下)——Ember.js 和 React
  • 一些前端框架的比较(上)——GWT、AngularJS 和 Backbone.js
  • 工作流系统的设计
  • Spark 的性能调优
  • “残酷” 的事实
  • 七年工作,几个故事
  • 从 Java 和 JavaScript 来学习 Haskell 和 Groovy(汇总)
  • 一道随机数题目的求解
  • 层次
  • Dynamo 的实现技术和去中心化
  • 也谈谈全栈工程师
  • 多重继承的演变
  • 编程范型:工具的选择
  • GWT 初体验
  • java.util.concurrent 并发包诸类概览
  • 从 DCL 的对象安全发布谈起
  • 不同团队的困惑
  • 不适合 Hadoop 解决的问题
  • 留心那些潜在的系统设计问题
  • 再谈大楼扔鸡蛋的问题
  • 几种华丽无比的开发方式
  • 我眼中的工程师文化
  • 观点的碰撞
  • 谈谈盗版软件问题
  • 对几个软件开发传统观点的质疑和反驳
  • MVC 框架的映射和解耦
  • 编程的未来
  • DAO 的演进
  • 致那些自嘲码农的苦逼程序员
  • Java 多线程发展简史
  • 珍爱生命,远离微博
  • 网站性能优化的三重境界
  • OSCache 框架源码解析
  • “ 你不适合做程序员”
  • 画圆画方的故事

近期评论

  • + 1.943624 BTC.NEXT - https://graph.org/Ticket--58146-05-02?hs=9a9c6f8dfe3cdbe0074006e3e640b19b& on 所有文章
  • Anonymous on 闲聊投资:亲自体验和护城河
  • 四火 on 关于近期求职的近况和思考
  • YC on 关于近期求职的近况和思考
  • mafulong on 常见分布式基础设施系统设计图解(四):分布式工作流系统
  • 四火 on 常见分布式基础设施系统设计图解(八):分布式键值存储系统
  • Anonymous on 我裸辞了
  • https://umlcn.com on 资源链接
  • Anonymous on 我裸辞了
  • Dylan on 我裸辞了
© 2025 四火的唠叨 | Powered by Minimalist Blog WordPress Theme