当前位置:首页 > 技术 > 正文内容

PageRank 算法-Google 如何给网页排名

fengm2个月前 (12-09)技术187

公号:码农充电站pro
主页:https://codeshellme.github.io

在互联网早期,随着网络上的网页逐渐增多,如何从海量网页中检索出我们想要的页面,变得非常的重要。

当时著名的雅虎和其它互联网公司都试图解决这个问题,但都没能有一个很好的解决方案。

直到1998 年前后,两位斯坦福大学的博士生,拉里·佩奇和谢尔盖·布林一起发明了著名的 PageRank 算法,才完美的解决了网页排名的问题。也正是因为这个算法,诞生了伟大的 Google 公司。


(上图中:左为布林右为佩奇。)

1,PageRank 算法原理

PageRank 算法的核心原理是:在互联网中,如果一个网页被很多其它网页所链接,说明该网页非常的重要,那么它的排名就高

拉里·佩奇将整个互联网看成一张大的图,每个网站就像一个节点,而每个网页的链接就像一个弧。那么,互联网就可以用一个图或者矩阵来描述。

拉里·佩奇也因该算法在30 岁时当选为美国工程院院士。

假设目前有4 个网页,分别是 A,B,C,D,它们的链接关系如下:


我们规定有两种链:

  • 出链:从自身引出去的链。
  • 入链:从外部引入自身的链。

比如图中的C 网页,有两个入链,一个出链。

PageRank 的思想就是,一个网页的影响力就等于它的所有入链的影响力之和

用数学公式表示为:

其中(分值代表页面影响力):

  • PR(u) 是网页u 的分值。
  • Bu 是网页u 的入链集合。
  • 网页v 是网页u 的任意一个入链。
  • PR(v) 是网面v 的分值。
  • L(v) 是网页v 的出链数量。
  • 网页v 带给网页u 的分值就是 PR(v) / L(v)
  • 那么PR(u) 就等于所有的入链分值之和。

在上面的公式中,我们假设从一个页面v 到达它的所有的出链页面的概率是相等的

比如上图来说,页面A 有三个出链分别链接到了 B、C、D 上。那么当用户访问 A 的时候,就有跳转到 B、C 或者 D 的可能性,跳转概率均为 1/3

2,计算网页的分值

下面来看下如何计算网页的分值。

我们可以用一个表格,来表示上图中的网页的链接关系,及每个页面到其它页面的概率:

A B C D
A 0 A->A 1/2 B->A 1 C->A 0 D->A
B 1/3 A->B 0 B->B 0 C->B 1/2 D->B
C 1/3 A->C 0 B->C 0 C->C 1/2 D->C
D 1/3 A->D 1/2 B->D 0 C->D 0 D->D

根据这个表格中的数字,可以将其转换成一个矩阵M

假设 A、B、C、D 四个页面的初始影响力都是相同的,都为 1/4,即:

经过第一次分值转移之后,可以得到 W1,如下:

同理可以得到W2W3 一直到 Wn

  • W2 = M * W1
  • W3 = M * W2
  • Wn = M * Wn-1

那么什么时候计算终止呢?

佩奇和布林已经证明,不管网页的初识值选择多少(我们这假设都是1/4),最终都能保证网页的分值能够收敛到一个真实确定值。

也就是直到 Wn 不再变化为止。

这就是网页分值的计算过程,还是比较好理解的。

3,PageRank 的两个问题

我们上文中介绍到的是PageRank 的基本原理,是简化版本。在实际应用中会出现等级泄露(RankLeak)和等级沉没(Rank Sink)的问题。

如果一个网页没有出链,就会吸收其它网页的分值不释放,最终会导致其它网页的分值为0,这种现象叫做等级泄露。如下图中的网页C

相反,如果一个网页没有入链,最终会导致该网页的分值为0,这种现象叫做等级沉没。如下图中的网页C

4,PageRank 的随机浏览模型

为了解决上面的问题,拉里·佩奇提出了随机浏览模型,即用户并不都是依靠网页链接来访问网页,也有可能用其它方式访问网址,比如输入网址。

因此,提出了阻尼因子的概念,这个因子代表用户按照跳转链接来上网的概率,而 1-d 则代表用户通过其它方式访问网页的概率。

所以,将上文中的公式改进为:

其中:

  • d 为阻尼因子,通常可以取0.85
  • N 为网页总数。

5,用代码计算网页分值

如何用代码来计算网页的PR 分值呢?(为了方便查看,我把上图放在这里)

我们可以看到,该图实际上就是数据结构中的有向图,因此我们可以通过构建有向图来构建 PageRank 算法。

NetworkX 是一个Python 工具包,其中集成了常用的图结构和网络分析算法

我们可以用 NetworkX 来构建上图中的网络结构。

首先引入模块:

import networkx as nx

DiGraph 类创建有向图:

G = nx.DiGraph()

将4 个网页的链接关系,用数组表示:

edges = [
  ("A", "B"), ("A", "C"), ("A", "D"), 
  ("B", "A"), ("B", "D"), 
  ("C", "A"), 
  ("D", "B"), ("D", "C")
  ]

数组中的元素作为有向图的边,并添加到图中:

for edge in edges:    
    G.add_edge(edge[0], edge[1])

使用pagerank 方法计算PR 分值:

# alpha 为阻尼因子
PRs = nx.pagerank(G, alpha=1)
print PRs 

输出每个网页的PR 值:

{'A': 0.33333396911621094, 
 'B': 0.22222201029459634, 
 'C': 0.22222201029459634, 
 'D': 0.22222201029459634}

最终,我们计算出了每个网页的PR 值。

6,画出网络图

NetworkX 包中还提供了画出网络图的方法:

import matplotlib.pyplot as plt

# 画网络图
nx.draw_networkx(G)
plt.show()

如下:

我们还可以设置图的形状,节点的大小,边的长度等属性,具体可以点击这里查看。

更多关于 NetworkX 的内容可以参考其官方文档

7,总结

PageRank 算法给了我们一个很重要的启发,权重在很多时候是一个非常重要的指标。

  • 比如在人际交往中,个人的影响力不仅取决于你的朋友的数量,而且朋友的质量非常重要,说明了圈子的重要性。
  • 比如在自媒体时代,粉丝数并不能真正的代表你的影响力,粉丝的质量也很重要。如果你的粉丝中有很多大V,那么将大大增加你影响力。

本篇文章主要介绍了:

  • PageRank 算法的原理。
  • 简化版的PageRank 算法遇到的问题,以及解决方案:
    • 等级泄露和等级沉没。
    • 引出随机浏览模型来解决这两个问题。
  • 如何用代码模拟PageRank 算法:

(本节完。)

推荐阅读:

决策树算法-理论篇-如何计算信息纯度

决策树算法-实战篇-鸢尾花及波士顿房价预测

朴素贝叶斯分类-理论篇-如何通过概率解决分类问题

朴素贝叶斯分类-实战篇-如何进行文本分类

计算机如何理解事物的相关性-文档的相似度判断

欢迎关注作者公众号,获取更多技术干货。

扫描二维码至手机访问

扫描二维码推送至手机访问。

版权声明:本文由风芒博客新闻信息分享笔录网站发布,如需转载请注明出处。

转载请注明出处:http://fengm.top/719.html

分享给朋友:

相关文章

没有操作历史的老域名与SEO有优势吗

没有操作历史的老域名与SEO有优势吗

  身为SEO从业人员,几乎都听说过老域名这个词,资深站长们优化一个网站效果非常快除了专业技能的原因以外最重要的就是他们从来不使用新域名,而采用老域名。这里讲到的老域名可能与你听到的有所不同,下面...

vs2019报错:配置“Debug|Win32”的 Designtime 生成失败IntelliSense

vs2019报错:配置“Debug|Win32”的 Designtime 生成失败IntelliSense

  这篇文章主要介绍了vs2019报错:配置“Debug|Win32”的 Designtime 生成失败IntelliSense 可能不可用 出错内容,非常不错,具有一定的参考借鉴价值,需要的朋友...

网站有收录索引却没有排名的原因

网站有收录索引却没有排名的原因

  实际上到现在为止还有很多从事SEO的朋友们不清楚索引、收录、排名之间的相互关系,甚至有的人会提问网站索引很正常,但排名上不去是为什么,要清楚索引正常只是代表搜索引擎将你的文章放入索引库里,可能...

一口气看完45个寄存器,CPU核心技术大揭秘

一口气看完45个寄存器,CPU核心技术大揭秘

序言前段时间,我连续写了十来篇CPU底层系列技术故事文章,有不少读者私信我让我写一下CPU的寄存器。 寄存器这个太多太复杂,不适合写故事,拖了很久,总算是写完了,这篇文章就来详细聊聊x86/x64架...

实现零信任安全模型的四种方法

实现零信任安全模型的四种方法

  【IT168 评论】根据漏洞情报,漏洞数据和风险评级的全球领导者Risk Based Security的数据显示,2019年有望成为网络犯罪“有史以来最糟糕的一年”。在勒索软件、病毒、特洛伊木马和...

分享:

支付宝

微信