使用一款搜索引擎,我们希望搜索结果能够拥有最佳的排序,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四张网页)帮助说明这个矩阵(这个例子来自于这篇文章):
可以看到矩阵L的几个非零元素的取值:
- p13=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链出网页的数量):
有了PageRank(pi)的概念以后,PageRank矩阵就可以用一个特征向量来表示:
由上述两个公式,可以得到(其中l(pi,pj)就是前文提到过的pij):
以上未特殊注明的公式截图来自于维基百科。
截止到2010年,Google索引的网页总数已经超过5000亿,也就是说,Google必须解这个阶数的特征向量,这个过程我不得而知,但这是不是真的就是MapReduce之类的由来呢?
文章系本人原创,转载请保持完整性并注明出自《四火的唠叨》
相关推荐
三种方法对web-Google.txt进行pagerank计算,1.python以稀疏矩阵方法实现单机计算谷歌网页数据计算pageRank值2.调用networkx库3.调用networkx库,其中pagerank自己实现。
用于Elixir的谷歌距离矩阵API库_Elixir_下载.zip
Google距离矩阵API的Ruby客户端。_Ruby_下载.zip
http://confluence.public.thoughtworks.org/display/CC/CI+Feature+Matrix 上面的链接是矩阵图的英文版,根据谷歌翻译结合自己的理解翻译的(持续集成工具矩阵图),有不对地方请通知我,谢谢。
谷歌提供的网页数据,并计算其pagerank值 谷歌数据连接http://snap.stanford.edu/data/web-Google.txt.gz
Java独立程序,该程序读取TSV文件,然后调用矩阵距离Web服务(Google Maps API)并返回具有距离的新TSV文件。 输入和输出文件格式适合我的博士要求。 请参阅的矩阵距离Web服务。 用法 不带参数的执行。 必须在代码...
Google出来的Best Matrix Library; NewMat11源代码; 已经做了修改,在VS2008下运行通过; 不会编译DLL的,请直接加载到工程里; C++类库; 该类库中Matrix索引从1开始
她想使用保存矩阵算法进行调度工作,但在基于Google Maps距离在某些地点之间创建距离矩阵时发现了一个问题。 我不是手动执行此操作,而是使用Google Maps Distance Matrix API从提供的位置经度和纬度创建此Maps距离...
experimental-mf, 缓存友好的多线程矩阵分解 基于的快速矩阵分解特性缓存友好的多线程矩阵分解。矩阵分解的快速多线程随机梯度动力学( SGLD ) 。快速多线程差分 private 矩阵分解。...数据我们支持google的Protobu
Google 距离矩阵 API 周围的 angular.js 包装器,灵感来自 鲍尔 此模块可作为 bower 包使用,使用以下命令安装: bower install angular-google-distance 或者 bower install git://github....
配对矩阵 使用 Google App Scripts 实现 Google Sheets 的配对矩阵
网页中矩阵动画的代码我不是自己做的,我是在谷歌上找到的,所以我不知道代码的真正作者很酷,可以用作网页的背景。 启动 docker 演示签出此 repo 并运行以下命令 docker-compose up 然后在浏览器中访问
node-google-distance, 轻松获取位置之间的距离数据 用于 Node.js的Google距离矩阵 API 轻松获得旅行距离和持续时间数据与谷歌距离矩阵安装npm install google-distance用法var distance = require
google-maps-services-go, 谷歌地图 API Web服务的客户端库 访问 谷歌... 也许是矩阵的方向。? 这个库将 谷歌地图 API Web服务 插件引入到你的go应用程序中。 谷歌地图 客户端的go客户机是以下 谷歌地图 api的go客户机
这是Google环聊的矩阵桥。 它以矩阵用户和环聊用户身份登录(又称“木偶”)以建立网桥。 有关更多信息,请参见: : 为了与Google hangouts服务器进行交互,该桥使用了一个称为hangups的python hangouts客户端库...
此代码演示了论文中的矢量化概念 Immanuel Anjam,Jan ... 可以在位于http://sites.google.com/site/janvaldman/publications的作者网页上找到该论文的链接如果您发现代码有用,请引用论文。 要比较组装时间,请调用
Fare Calculator App - 使用 Google Places 和距离矩阵 API 计算两个地址之间的出租车费用的应用程序。 地址是使用 Google Places AutoComplete API 输入的。 一个 Http 请求被发送到谷歌服务器,它以 JSON 格式...
“ routesRandomiser.R”:使用Google的距离矩阵API在给定的shapefile中查找并保存随机道路网络路线。 根据Google的说法,它将输出一个CSV,其中包含起点/终点的详细信息,它们之间的道路网络距离以及旅行所需的...
为了可视化矩阵,人们可能希望首先转换NaN 中的零,使用 C(C==0) = nan,然后使用 pcolor(C) 输入cs : 社区从属向量 <1> 输出C : 社区矩阵 <N> 参考: [1] 脑连接工具箱: https : //sites.google.com/site/bctnet/
矩阵乘法优化方法 这是几种矩阵乘法算法的玩具基准实验。 要求 谷歌测试 谷歌/基准 的openmp CUDA 演算法 天真:计算C = A * B的纯方法,时间复杂度为O(N^3) for(int i = 0; i < A.rows; ++i) { for(int j = 0...