大数据 | Spark中实现基础的PageRank

吴军博士在《数学之美》中深入浅出地介绍了由Google的佩奇与布林提出的PageRank算法,这是一种民主表决式网页排名技术。书中提到PageRank的核心思想为:

在互联网上,如果一个网页被很多其他网页所链接,说明它受到普遍的承认和信赖,那么它的排名就高。

同时,该算法还要对来自不同网页的链接区别对待,排名越高的网页,则其权重会更高,即所谓网站贡献的链接权更大。

例如网页Y被X1,X2,X3,X4四个网页所链接,且这四个网页的权重分别为0.001,0.01,0.02,0.04,则网页Y的Rank值=0.01+0.02+0.03+0.04=0.071。但问题是,如何获得X1,X2,X3,X4这些网页的权重呢?答案是权重等于这些网页自身的Rank。然而,这些网页的Rank又是通过链接它的网页的权重计算而来,于是就陷入了“鸡与蛋”的怪圈。解决办法是为所有网页设定一个相同的Rank初始值,然后利用迭代的方式来逐步求解。

在《数学之美》第10章的延伸阅读中,有更详细的算法计算,有兴趣的同学可以自行翻阅。下面是PageRank的简单执行步骤:

  • 首先假定所有网页的初始Rank值为1/N,N为所有网页的数量。
  • 开始迭代。每次迭代,则页面p会将r/n的值发送给所有链接了p页面的邻居页面。其中,r为当前页面的rank值,n为链接了当前页面的邻居页面数。该值实则就是当前页面p这次迭代的贡献者(contribution)。
  • 每次迭代结束时,都对最终获得的contributions进行求和。假设每个contribution为c(i),则可以通过公式α/N + (1-α)∑c(i)获得每个页面的rank值。其中,α是一个常数值,可以认为是一个调优参数(tuning parameter),N为所有页面的数量。

究竟应该迭代多少次呢?由于PageRank实则是线性代数中的矩阵计算,佩奇和拉里已经证明了这个算法是收敛的。当两次迭代获得结果差异非常小,接近于0时,就可以停止迭代计算。《数学之美》中提到:“一般来讲,只要10次左右的迭代基本上就收敛了。”

原文发布于微信公众号 - 逸言(YiYan_OneWord)

原文发表时间:2015-02-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏吉浦迅科技

【讲座】在NVIDIA Jetson上从Tensorflow到TensorRT

NVIDIA在太平洋时间3月8日上午11:00-12:00(北京时间3月9日凌晨3:00-4:00)举办了主题为“AI at the Edge: TensorF...

4396
来自专栏企鹅号快讯

基于Python的文本情感分类

前言 在上一期《【干货】--手把手教你完成文本情感分类》中我们使用了R语言对酒店评论数据做了情感分类,基于网友的需求,这里再使用Python做一下复现。关于步骤...

1855
来自专栏专知

【干货】如何为论文设计精致的插图

【导读】论文是经过数月或数年实验得到的数据的积淀。 但是,原始数据或描述本身并不能成为好的期刊文章。 数据可视化工具和免费绘图软件能帮助科学家阐述他们的工作。 ...

1323
来自专栏深度学习之tensorflow实战篇

R包—iGraph

这几天收到师兄的任务,熟悉iGRaph包的使用,通过查资料,外加自己的实践,在此做个简单的学习笔记。 以下例子均是在R 3.0.1版本下测试的。 1.用igr...

2615
来自专栏数说工作室

logistic回归建模指南

昨天的logistic回归:从生产到使用【上:使用篇】(在微信公众号“数说工作室”中回复“logit1”查看),有不少数说网友们建议把最后的建模指南图单独发一下...

3218
来自专栏草根专栏

Python数据分析(二): Pandas技巧 (2)

Pandas的第一部分: http://www.cnblogs.com/cgzl/p/7681974.html github地址: https://github...

2696
来自专栏生信技能树

Python 3 reference/cheat sheet

虽然我本人是perl党,但我还是推荐新手学习python: 本次我们讲师团队讲解了: 对FASTQ的操作 5,3段截掉几个碱基 序列长度分布统计 FASTQ 转...

3667
来自专栏IT派

python代码实现图片噪声去除

今天来给大家分享下怎么做图片的噪声去除。平时其实大家上网都能遇到这样的场景,就是输入讨厌验证码,怎么都输不对。验证码现在可以说是千奇百怪、分外妖娆,为啥要做成这...

763
来自专栏CVer

TensorFlow.js人脸识别—玩转吃豆豆小游戏

谷歌TenosrFlow开发者峰会2018上,发布了面向JavaScript开发者的全新机器学习框架 TensorFlow.js。这里介绍一个TensorFlo...

39612
来自专栏软件

可视化你的BLAST结果

人类已经使用数据可视化技术很长一段时间了,图像和图表已被证明是一种有效的方法来进行新信息的传达与教学。有研究表明,80%的人还记得他们所看到的,但只有20%的人...

19710

扫描关注云+社区