2020-09-16 16:13发布
Google并不是第一家搜索引擎公司，但后来却成为龙头行业，这其中PageRank算法发挥着重要的作用。PageRank是Google创始人之一Larry Page发明的，今天我们就来一起瞻仰下大神的创作。
互联网上的每一个网页都可以看作一个顶点，每一个顶点都有出度和入度。出度是指从这个网页能链接到的其他网页的数目，入度是指能链接到这个网页的其他网页的数目。
这样整个互联网中的所有网页的链接关系可以看成具有大量网页结点的有向图。一个网页很重要最直观的感受就是有许多的网页链接到它，即它的入度大，并且重要性越高的网页链接它更能说明它越重要。
基于以上思想，我们首先量化网页的重要性，用PR值表示重要性，一个网页的PR值越大表明这个网页越重要。
PageRank的简化模型
一个网页的PR值在一定程序上取决于它的入度，也和链接到它的网页本身的PR值有关，基于这个思想，计算任意一个网页的PR值的公式如下。
其中Bu是所有链接到u网页的网页集合，网页v属于集合Bu，L(v)是网页v的出度。下面我们就用下图的网页链接关系举例。
假定A、B、C、D网页的初始PR值都为0.25，根据上面的计算公式，我们有如下的计算过程。
经过多次的迭代计算后，PR值逐渐稳定，即可认为PR值收敛。从计算结果看出，B、D的PR值较高，这表明B、D的重要程度高，这也符合我们对图的直观感受。
但真实的网页链接关系复杂，这种简化的模型会面临以下两个问题。
1.排名泄漏
如果有向图中有一个顶点的出度为0，即这个网页没有链接到其他的网页，则会出现排名泄漏问题。以下图为例，A顶点的出度为0。
以此图的迭代计算过程如下。
出现这种问题的原因可以理解为A网页对整个网页没有PR值的贡献，因为它的出度为0，相反它还吸收其它网页对它PR值的贡献，导致整个网页的PR值越来越小。
2.排名下沉
如果有向图中有一个顶点的入度为0，即没有其他网页链接到这个网页，则会出现排名下沉问题。以下图为例，A顶点的入度为0。
因为A的入度为0，则在第一次迭代的时候A的PR值就为0，以后都为0。
为了解决简化模型出现的以上两个问题，PageRank的随机浏览模型应运而生。
PageRank的随机浏览模型
随机浏览模型是符合用户上网行为的一种模型。用户随机打开一个网页后，要么点击这个网页上的链接继续网页的浏览，要么随机转到另外的一个网页重新开始新一轮的浏览。
为此随机浏览模型引入了一个阻尼系数d来表示用户点击此网页上的链接继续浏览的概率，则1-d就是用户重新进行新一轮的浏览的概率。引入阻尼系数d的计算公式如下。
其中N为整个网页的数目。
引入阻尼系数的效果为：在原有的有向图中添加了一个全链接的浏览关系，这样就完全解决了简化模型中出现的排名泄漏和排名下沉的问题。如下图所示。
其中虚线就是随机浏览模型添加的全链接关系。
以上就是Google开创的PageRank算法，是不是觉得原理很简单，但就是这样一个原理简单的算法使Google成为搜索领域的霸主。
创建test文件夹hadoop fs -mkdir /test
Hadoop的三大核心组件分别是：1、HDFS(Hadoop Distribute File System)：hadoop的数据存储工具。2、YARN(Yet Another Resource Negotiator,另一种资源协调者)：Hadoop 的资源管理器。3、Hadoop MapReduce:分布式计算框架。HDFS是一个高度容错性的系统，适合部...
hbase依靠HDFS来存储底层数据。Hadoop分布式文件系统(HDFS)为HBase提供了高可靠性的底层存储支持，HBase中的所有数据文件都存储在Hadoop HDFS文件系统上。
HBase分布式数据库具有如下的显著特点：容量大：HBase分布式数据库中的表可以存储成千上万的行和列组成的数据。面向列：HBase是面向列的存储和权限控制，并支持独立检索。列存储，其数据在表中是按照某列存储的，根据数据动态的增加列，并且可以单独对列进行...
解决问题的层面不一样首先，Hadoop和Apache Spark两者都是大数据框架，但是各自存在的目的不尽相同。Hadoop实质上更多是一个分布式数据基础设施: 它将巨大的数据集分派到一个由普通计算机组成的集群中的多个节点进行存储，意味着您不需要购买和维护昂贵的服务...
1、HBase写快读慢，HBase的读取时长通常是几毫秒，而Redis的读取时长通常是几十微秒。性能相差非常大。2、HBase和Redis都支持KV类型。但是Redis支持List、Set等更丰富的类型。3、Redis支持的数据量通常受内存限制，而HBase没有这个限制，可以存储远超内存大小...
列式存储格式是指以列为单位存储数据的数据存储格式，相比于传统的行式存储格式，它具有压缩比高、读I/O少(此处指可避免无意义的读I/O)等优点，目前被广泛应用于各种存储引擎中。对于HBase而言，它并不是一个列式存储引擎，而是列簇式存储引擎，即同一列簇中...
一、简单理解Hadoop是一个大象：一个hadoop集群主要包含三个主要的模块：Mapreduce,hdfs,yarn。mapreduce是一个分离在合并的计算框架，注意他不是一个集群，而是一个编程框架。hdfs是一个分布式文件系统，是一个分布式集群，用于存放数据。yarn集群是负责集群...
01 网络公开数据集02 数据报采集03 网络爬虫04 日志收集05 社会调查06 业务数据集07 埋点采集08 传感器采集09 数据交易平台10 个人数据收集
1 Hadoop 各个目录的解释bin：Hadoop管理脚本和使用脚本所在目录， sbin目录下的脚本都是使用此目录下的脚本实现的。etc：Hadoop的所有配置文件所在的目录，所有hadoop的配置在etc/hadoop目录下include:对外提供的库的头文件lib ：对外提供的动态编程库和静态...
HDFS存储机制，包括HDFS的写入过程和读取过程两个部分： 1、写入过程： 1）客户端向namenode请求上传文件，namenode检查目标文件是否已存在，父目录是否存在。2）namenode返回是否可以上传。3）客户端请求第一个 block上传到哪几个datanode服务器上。4）nam...
adoop核心：MapReduce原理。 MR的核心是shuffle，被称为奇迹发生的地方。 shuffle，弄乱，洗牌的意思。partition 分区，sort 排序，spill溢出，disk 磁盘下面是官方对shuffle的配图： phase 阶段，fetch 最终，merge 合并...
Shuffle阶段分为两部分:Map端和Reduce端。一 map端shuffle过程；1-内存预排序：默认每个map有100M内存进行预排序（为了效率），超过阈值，会把内容写到磁盘； 此过程使用快速排序算法；2-根据key和reducer的数量进行分区和排序；首先根据数据所属的Parti...
大数据时代需要1存储大量数据2快速的处理大量数据3从大量数据中进行分析
hadoop的四种模式。1、本地模式：本地模式就是解压源码包，不需要做任何的配置。通常用于开发调试，或者感受hadoop。2、伪分布模式：在学习当中一般都是使用这种模式，伪分布模式就是在一台机器的多个进程运行多个模块。虽然每一个模块都有相应的进程，但是却...
进入和退出安全模式 [root@localhost bin]# ./hdfs dfsadmin -safemode enter15/08/03 07:26:24 WARN util.NativeCodeLoader: Unable to load native-hadoop library for your platform... using builtin-java classes where ......
最多设置5个标签!
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','/static/images/logo.png', '推荐 宝藏秦公子 的问题《谷歌网页排名的算法是怎样的》','http://www.shouhuola.com/q-29391.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
Google并不是第一家搜索引擎公司，但后来却成为龙头行业，这其中PageRank算法发挥着重要的作用。PageRank是Google创始人之一Larry Page发明的，今天我们就来一起瞻仰下大神的创作。
互联网上的每一个网页都可以看作一个顶点，每一个顶点都有出度和入度。出度是指从这个网页能链接到的其他网页的数目，入度是指能链接到这个网页的其他网页的数目。
这样整个互联网中的所有网页的链接关系可以看成具有大量网页结点的有向图。一个网页很重要最直观的感受就是有许多的网页链接到它，即它的入度大，并且重要性越高的网页链接它更能说明它越重要。
基于以上思想，我们首先量化网页的重要性，用PR值表示重要性，一个网页的PR值越大表明这个网页越重要。
PageRank的简化模型
一个网页的PR值在一定程序上取决于它的入度，也和链接到它的网页本身的PR值有关，基于这个思想，计算任意一个网页的PR值的公式如下。
其中Bu是所有链接到u网页的网页集合，网页v属于集合Bu，L(v)是网页v的出度。下面我们就用下图的网页链接关系举例。
假定A、B、C、D网页的初始PR值都为0.25，根据上面的计算公式，我们有如下的计算过程。
经过多次的迭代计算后，PR值逐渐稳定，即可认为PR值收敛。从计算结果看出，B、D的PR值较高，这表明B、D的重要程度高，这也符合我们对图的直观感受。
但真实的网页链接关系复杂，这种简化的模型会面临以下两个问题。
1.排名泄漏
如果有向图中有一个顶点的出度为0，即这个网页没有链接到其他的网页，则会出现排名泄漏问题。以下图为例，A顶点的出度为0。
以此图的迭代计算过程如下。
出现这种问题的原因可以理解为A网页对整个网页没有PR值的贡献，因为它的出度为0，相反它还吸收其它网页对它PR值的贡献，导致整个网页的PR值越来越小。
2.排名下沉
如果有向图中有一个顶点的入度为0，即没有其他网页链接到这个网页，则会出现排名下沉问题。以下图为例，A顶点的入度为0。
因为A的入度为0，则在第一次迭代的时候A的PR值就为0，以后都为0。
为了解决简化模型出现的以上两个问题，PageRank的随机浏览模型应运而生。
PageRank的随机浏览模型
随机浏览模型是符合用户上网行为的一种模型。用户随机打开一个网页后，要么点击这个网页上的链接继续网页的浏览，要么随机转到另外的一个网页重新开始新一轮的浏览。
为此随机浏览模型引入了一个阻尼系数d来表示用户点击此网页上的链接继续浏览的概率，则1-d就是用户重新进行新一轮的浏览的概率。引入阻尼系数d的计算公式如下。
其中N为整个网页的数目。
引入阻尼系数的效果为：在原有的有向图中添加了一个全链接的浏览关系，这样就完全解决了简化模型中出现的排名泄漏和排名下沉的问题。如下图所示。
其中虚线就是随机浏览模型添加的全链接关系。
以上就是Google开创的PageRank算法，是不是觉得原理很简单，但就是这样一个原理简单的算法使Google成为搜索领域的霸主。
相关问题推荐
创建test文件夹hadoop fs -mkdir /test
Hadoop的三大核心组件分别是：1、HDFS(Hadoop Distribute File System)：hadoop的数据存储工具。2、YARN(Yet Another Resource Negotiator,另一种资源协调者)：Hadoop 的资源管理器。3、Hadoop MapReduce:分布式计算框架。HDFS是一个高度容错性的系统，适合部...
hbase依靠HDFS来存储底层数据。Hadoop分布式文件系统(HDFS)为HBase提供了高可靠性的底层存储支持，HBase中的所有数据文件都存储在Hadoop HDFS文件系统上。
HBase分布式数据库具有如下的显著特点：容量大：HBase分布式数据库中的表可以存储成千上万的行和列组成的数据。面向列：HBase是面向列的存储和权限控制，并支持独立检索。列存储，其数据在表中是按照某列存储的，根据数据动态的增加列，并且可以单独对列进行...
解决问题的层面不一样首先，Hadoop和Apache Spark两者都是大数据框架，但是各自存在的目的不尽相同。Hadoop实质上更多是一个分布式数据基础设施: 它将巨大的数据集分派到一个由普通计算机组成的集群中的多个节点进行存储，意味着您不需要购买和维护昂贵的服务...
1、HBase写快读慢，HBase的读取时长通常是几毫秒，而Redis的读取时长通常是几十微秒。性能相差非常大。2、HBase和Redis都支持KV类型。但是Redis支持List、Set等更丰富的类型。3、Redis支持的数据量通常受内存限制，而HBase没有这个限制，可以存储远超内存大小...
列式存储格式是指以列为单位存储数据的数据存储格式，相比于传统的行式存储格式，它具有压缩比高、读I/O少(此处指可避免无意义的读I/O)等优点，目前被广泛应用于各种存储引擎中。对于HBase而言，它并不是一个列式存储引擎，而是列簇式存储引擎，即同一列簇中...
一、简单理解Hadoop是一个大象：一个hadoop集群主要包含三个主要的模块：Mapreduce,hdfs,yarn。mapreduce是一个分离在合并的计算框架，注意他不是一个集群，而是一个编程框架。hdfs是一个分布式文件系统，是一个分布式集群，用于存放数据。yarn集群是负责集群...
01 网络公开数据集02 数据报采集03 网络爬虫04 日志收集05 社会调查06 业务数据集07 埋点采集08 传感器采集09 数据交易平台10 个人数据收集
1 Hadoop 各个目录的解释bin：Hadoop管理脚本和使用脚本所在目录， sbin目录下的脚本都是使用此目录下的脚本实现的。etc：Hadoop的所有配置文件所在的目录，所有hadoop的配置在etc/hadoop目录下include:对外提供的库的头文件lib ：对外提供的动态编程库和静态...
HDFS存储机制，包括HDFS的写入过程和读取过程两个部分： 1、写入过程： 1）客户端向namenode请求上传文件，namenode检查目标文件是否已存在，父目录是否存在。2）namenode返回是否可以上传。3）客户端请求第一个 block上传到哪几个datanode服务器上。4）nam...
adoop核心：MapReduce原理。 MR的核心是shuffle，被称为奇迹发生的地方。 shuffle，弄乱，洗牌的意思。partition 分区，sort 排序，spill溢出，disk 磁盘下面是官方对shuffle的配图： phase 阶段，fetch 最终，merge 合并...
Shuffle阶段分为两部分:Map端和Reduce端。一 map端shuffle过程；1-内存预排序：默认每个map有100M内存进行预排序（为了效率），超过阈值，会把内容写到磁盘； 此过程使用快速排序算法；2-根据key和reducer的数量进行分区和排序；首先根据数据所属的Parti...
大数据时代需要1存储大量数据2快速的处理大量数据3从大量数据中进行分析
hadoop的四种模式。1、本地模式：本地模式就是解压源码包，不需要做任何的配置。通常用于开发调试，或者感受hadoop。2、伪分布模式：在学习当中一般都是使用这种模式，伪分布模式就是在一台机器的多个进程运行多个模块。虽然每一个模块都有相应的进程，但是却...
进入和退出安全模式 [root@localhost bin]# ./hdfs dfsadmin -safemode enter15/08/03 07:26:24 WARN util.NativeCodeLoader: Unable to load native-hadoop library for your platform... using builtin-java classes where ......