PageRank算法浅析

2024-08-25 22:58
文章标签 算法 浅析 pagerank

本文主要是介绍PageRank算法浅析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

转载请注明出处!!!http://blog.csdn.net/zhonghuan1992

本文是根据 Topic-Sensitive PageRank 

Google’s PageRank:The Math Behind the Search Engine  

http://blog.csdn.net/hguisu/article/details/7996185

http://blog.codinglabs.org/articles/intro-to-pagerank.html

前两篇是关于pagerank的两篇超赞的论文和后两个博客的关于pagerank的理解,然后我总结了一下,再加上一些自己的理解。真诚感谢上面的作者。

1. PageRank提出背景

      PageRank,即网页排名,又称网页级别、Google左侧排名或佩奇排名。

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。Google的创始人拉里·佩奇和谢尔盖·布林于1998年在斯坦福大学发明了这项技术。(摘自维基百科)

先说一下PageRank提出的背景吧,一开始搜索引擎出来的时候,可不是像现在我们看到的这样神奇,大部分的搜索,我们都可以在前几页找到我们想要的网页。不过等一下,不要我说到这里,大家就觉得PageRank如此神奇,就是它帮助我们搜到自己想要的东西的,回答是,当然不完全是,如今的搜索结果是经过很多加权得来的,pageRank肯定是起到作用的,究竟多少,这就不得而知了。pageRank当时提出来,一是为了提高搜索结果的正确性(这是大头),而是可以应对那个时候网站为了提高自己在某些关键词的排名而做出的一些不好的举措。在pageRank出来前,网络上的排名很大程度上依靠关键词的出现的次数,这就导致了一些问题,你懂得。只要网页关键词多点,那么就。。。当然,pageRank并非万能,但是却是结果优化了很多。

google的两个创世人,就想如何能够将重要的网址,人们想要的网址排在前面。他们从论文索引次数得到了启发,好的论文,引用次数肯定是高的。就这样,pageRank就被创建了。当然正如很多注明历史一样,我们说得轻巧,其实过程是不容易的。

2. PageRank算法

pageRank算法上面已经介绍了是从论文引用次数得到启发,那么具体是怎么样呢?其实聪明的你应该能够有所思考这样的方式了(maybe you are next page)一个网页,大都在页面上有转向其它页面的链接,就想本文开头就有四个链接一样,大多数页面也是有转进来的。其实,就可以将网页之间的关系,转向成为一个有向图,有向图的基本概念是阅读下文的前提,如果你还没有接触过,那么请自行了解。

- ---- 图 1

1是一个有向图,你也可以看成是网页之间的关系。如果网页A有指向网页B的链接,那么A就有一条指向B的有向边。从图中可以看出,网页A分别有指向B,C,D的边,D会自己指向自己的链接,其它的就不多说啦。

好滴,模型转化完毕,接下来就是如何得到我们的结果,pageRank算法,将每一个网页根据链接关系来进行分级,越重要的网页,越多网页会链接到它,那么他的评分必定更高,可是pageRank是如何来利用有向图的拓扑结构计算网页的重要分数的呢?

从图1可以看出,c的概率等于1/3A+1/2 B,(由指向它的边决定)

那么我们的每个页面的概率,就可以用上面指向它的边的概率进行推导得出了。

令Wi表示第i个页面,Ni表示Wi页面上的对外连接数,然后我们需要进行推算了,怎么推,其实求网页的重要性的过程就好像一个马尔科夫的过程,我们的重要性,其实可以用用户需要访问Wi的概率进行描述,然后,有两个假设,一:开始所有页面的概率都是相同的;二:用户当前在Wi页面,那么用户访问Wi页面上的外连接网页的概率都是1/Ni。然后概率的转移方式就是这样的:

表示第n次迭代的时候,第i个网页的被访问概率;表示第j个网页是否有转向第i个网页的链接,有为1,没有为0;

上面的公式,如果转化为矩阵运算,会更简单,令H为矩阵,。上面的递推公式转化为:


所以只要给个P(0)就可以算出Pn了,那么P0,根据假设一,是1/(所有网页数),假设所有网页开始的概率相同嘛。然后开始计算,当P趋于稳定时,我们的任务便完成了。

说到这里可能读者会觉得有点模糊。想一下,怎么衡量网页符合用户的需求,自然会想到他访问该网页的概率,概率如何进行好的计算,我们可以用有向图上的关系来进行递推,概率转化关系就是这样进行的。

不过到这里,我们的转移方式还是不完美,为什么呢,因为最后面有一些网页的没有入边,没有出边,还有一些其他问题,比如两个网页,互相连接,那么两个网页的概率不会趋于稳定,反倒是(1,0)-->(0,1)-->(1,0)-->(0,1)这样反复震荡。为了克服这些个问题。引入了修正因子,其实我也并不太了解的数学性质,它存在的意义可以理解为概率。了解更多,可以看这里,原公式就变为了这样了:


G是替代H的新的转移矩阵,这里的a表示网页i是否是孤立的节点(可怜的没有人链接)的,如果i是则ai=1,否则为0;

可以从概率的角度上说,用户有的概率通过网页上的链接访问新的网页,或者的概率通过输入新的网址(而不是点击链接)访问网页。


新的转移方式,可以确保能够得到收敛。

就这样了,如果您发现文章有问题,请留言告诉我





这篇关于PageRank算法浅析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1106885

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

浅析CSS 中z - index属性的作用及在什么情况下会失效

《浅析CSS中z-index属性的作用及在什么情况下会失效》z-index属性用于控制元素的堆叠顺序,值越大,元素越显示在上层,它需要元素具有定位属性(如relative、absolute、fi... 目录1. z-index 属性的作用2. z-index 失效的情况2.1 元素没有定位属性2.2 元素处

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

浅析Python中的绝对导入与相对导入

《浅析Python中的绝对导入与相对导入》这篇文章主要为大家详细介绍了Python中的绝对导入与相对导入的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1 Imports快速介绍2 import语句的语法2.1 基本使用2.2 导入声明的样式3 绝对import和相对i

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

浅析如何使用Swagger生成带权限控制的API文档

《浅析如何使用Swagger生成带权限控制的API文档》当涉及到权限控制时,如何生成既安全又详细的API文档就成了一个关键问题,所以这篇文章小编就来和大家好好聊聊如何用Swagger来生成带有... 目录准备工作配置 Swagger权限控制给 API 加上权限注解查看文档注意事项在咱们的开发工作里,API

浅析Rust多线程中如何安全的使用变量

《浅析Rust多线程中如何安全的使用变量》这篇文章主要为大家详细介绍了Rust如何在线程的闭包中安全的使用变量,包括共享变量和修改变量,文中的示例代码讲解详细,有需要的小伙伴可以参考下... 目录1. 向线程传递变量2. 多线程共享变量引用3. 多线程中修改变量4. 总结在Rust语言中,一个既引人入胜又可

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1